Оптимизация показателей

Для вирішення задачі лінейного програмування, потрібно записати вихідну задачу в формі задачі лінейного програмування, а потім застосовувати симплекс-метод . Основною задачею лінійного програмування – задача для якої:

  1. потрібно визначити максимальне значення ф-ції

  2. всі обмеження записані в вигляді рівностей

  3. для всіх змінних виконується умова невідємності

Якщо обмеження має вид нерівності зі знаком >=, то шляхом множення його на (-1) переходять до нерівності зі знаком <=.

Від обмежень нерівностей необхідно перейти до обмежень рівностей. Такий перехід виконується шляхом введення в ліву частину кожної нерівності додаткових незалежних невідємних змінних. При цьому знак нерівності міняють на знак рівності.

Вихідне завдання:

F = 5х1 +6х2 max

-10x1 - 6x2 -60

-4x1 + 9x2 36

4x1 - 2x2 8

x1,x20 x1,x2-цілі числа


Основна задача:

F = 5х1 +6х2 max


10x1 + 6x2 + х3 =60

-4x1 + 9x24= 36

4x1 - 2x25 = 8


x1,x2,x3,x4,x5 0 x1,x2-цілі числа

Кожній змінній в системі відповідає свій вектор – стовпець. Вектор – стовпець Ро складається із значень правих частин рівнянь і називається вектором вільних членів.

Виходячи з основного завдання, складаєм симплекс-таблицю.

№ рядка Базис

Сб

Р0

Р1

Р2

Р3

Р4

Р5

1

Р3

0 60 10

6

1 0 0
2

Р4

0 36 -4 9 0 1 0
3

Р5

0 8 4 -2 0 0 1
4 F
0 -5 -6 0 0 0
Таблиця № 1 – Вихідна симплекс-таблиця


Знаходження оптимального розвязку ЗЛП за допмогою с-м включає слідуючі етапи:

  1. За вихідною с-т знаходять опорне рішення

Кожній с-т відповідає своє опорне рішення. Воно може бути представлене у вигляди вектора Х Розмірніст вектора дорівнює кількості змінних в основній задачі.

Кожній змінній в симплекс таблиці відповідає свій вектор. Змінній x1—вектор Р1 і т.д.

Вектор Р0 складений із вільних членів рівнянь. Кожний рядок симплекс-таблиці – рівняння відповідно. Четвертий рядок—рядок оцінок в ньому записують коефіцієнти при змінних в цільовій ф-ції з протилежним знаком і визначається розв’язуємий стовпець, беруться модулі від’ємних чисел з цієї строки. В векторі Х кожній змінній відповідає певна компонента. Змінній х1 перша компонента змінній х2—друга. Значення компонент визначають слідуючим чином, якщо вектор базисний, то компонента дорівнює значенню компоненти вектора стовпця Р0 з того рідка де в базисі стоїть 1.

У вихідній таблиці вектори Р1, Р2 – не базісні, тобто в Х – перша и друга компоненти = 0

Х=(0;0;60;36;8)

  1. Зясовують, мається хочаб одне відємне значення врядку оцінок ( рядок 4) Якщо нема – то план оптимальний, якщо є – треба переходити до новій с-т.

Рядок оцінок має (-5) та (-6), отже данний опорний план – не оптимальний.

  1. Знаходять визначальний стовпець. Стовпець називають визначальним, якщо в рядку оцінок у нього найбільше за модулем значення. Маємо стовпець Р2 |-6|>|-5|

  2. Знаходимо визначальний рядок. Визанчальним назівається такий рядок, який відповідає найменшому з відношень компонентів стовпця Ро до додатніх компонентів визначального стовпця. (Рядок оцінок до уваги не приймається)

Min = ( 60/6; 36/9) = 4 – рядок 2.

  1. Будують наступну с-т .

Для цього кожний елемент таблиці перераховуємо за формулою

aij=aij- (аіk* аnj)/ank де k-номер розв’язувального стовпця, а n- номер розв’язувального рядка

aij—елемент строки- і, стовпця- j нової сиплекс таблиці

aij—елемент строки- і, стовпця-j попередньої симплекс-таблиці

аіk-- елемент що знаходиться у визначальному стовпці попер. с-т.

аnj-- елемент що знаходиться у визначальному рядку попер с-т.

ank – элемент що стоїть на перехресті визн рядка и строки у попер сим-т.


a10= 60 – (36*6)/9 = 36

a11= 10 +(6*4)/9 = 38/3

№ рядка Базис

Сб

Р0

Р1

Р2

Р3

Р4

Р5

1

Р3

0 36
0 0 -1 1/5

0

2

Р2

6 4 -4/9 1 1 1/5 0
3

Р5

0 16 28/9 0 0 3/5 1
4 F
24

-23/3

0 0 1 1/5 0
Таблиця № 2


Х1=(0;4;36;0;16) F(X1) = 24

В рядку оцінок є одне відємне число. Тому Р1 – визначальний стовпець

Min = ( 36/38*3;16/4;9) = 54/19 – визначальний рядок Р3


Таблиця № 3


№ рядка Базис

Сб

Р0

Р1

Р2

Р3

Р4

Р5

1

Р1

5 54/19 1 0 3/38 -1/19 0
2

Р2

6 100/19 0 1 2/57 5/57 0
3

Р5

0 136/19 0 0 -14/57 22/57 1
4 F
870/19 0 0 21/38 5/19 0
X3= ( 54/19;100/19;0;0;136/19) F3(X3) = 45 15/19

В рядку оцінок нема відємних значень, тому даний опорний план є оптимальним. Але не виконується умова цілочисельності, тому слід застосувати відсічення по методу Гоморі.

2. Застосування і побудова відсічення по методу Гоморі

х1=54/19, х2=100/19

До системи обмежень основного завдання добавляємо ще одну нерівність виду: F(a*ij)*xij>= F(b*ij), де a*ij і b*ij дробови частини чисел.

Під дробовою частиною числа а розуміють найменше невідємне число в і таке, що а – в є цілим числом.Якщо в оптимальному плані вихідного завдання дробового значення приймають декілька змінних, то додаткова нерівність будується для змінної, в якої найбільша дробова частина.

F(x1)>F(x2) (16/19 >5/19)

-3/38х3-18/19х4 + х6 = -16/19

таблиця № 4

№ рядка Базис

Сб

Р0

Р1

Р2

Р3

Р4

Р5

Р6

1

Р1

5 54/19 1 0 3/38 -1/19 0 0
2

Р2

6 100/19 0 1 2/57 5/57 0 0
3

Р5

0 136/19 0 0 -14/57 22/19 1 0
4

Р6

0 -16/19 0 0 -3/38

-18/19

0

1

5 F
870/19 0 0 23/38 5/19 0 0


Х4 = ( 54/19;100/19;0;0;135/19;-16/19) F(X4) = 45 15/19

Т.к. опорний план містить відємну змінну то треба застосувати подвійний

с. м.

3.

Відшукання розвязку ЗЛП подвійним с-м включає слідуючі етапи:

  1. Знахдять опорне рішення

Х4 = ( 54/19;100/19;0;0;135/19;-16/19) F(X4) = 45 15/19

  1. Перевіряють знайдений опорний розвязок на оптимальність.

Розвязок не оптимальний, тому слід перейти до нового опорного рішення.

  1. Вибираемо визначальний рядок. Визначальним називається той, який відповідає найбільшому за модулем відємному значенню в стовпцю Ро

Рядок № 4

  1. Вибираємо визначальний стовпчик. Той, який відповідає найменшему відношенню рядка оцінок до ньгого. (по модулю)

Min = (23/38*38/3;5/19*19/18) = 5/18 стовпець Р4


Таблиця № 5

№ рядка Базис

Сб

Р0

Р1

Р2

Р3

Р4

Р5

Р6

1

Р1

5 26/9 1 0 1/12 0 0 -1/18
2

Р2

6 140/27 0 1 1/36 0 0 5/54
3

Р5

0 1048/171 0 0 -13/38 0 1 11/9
4

Р4

0 8/9 0 0 1/12 1 0 -19/18
5 F
410/9 0 0 7/12 0 0 5/18

Х5= (26/9;140/27;0;0;8/9;1048/171) F5 = 45 5/9

F(x1) = f ( 2 8/9) = 8/9

F (x2) = f ( 5 5/27) = 5/27


-1/12х3 – 17/18х6 + х7 = -8/9


таблица № 6

№ рядка Базис

Сб

Р0

Р1

Р2

Р3

Р4

Р5

Р6

Р7

1

Р1

5 26/9 1 0 1/12 0 0 -1/18 0
2

Р2

6 140/27 0 1 1/36 0 0 5/54 0
3

Р5

0 1048/171 0 0 -13/38 0 1 11/9 0
4

Р4

0 8/9 0 0 1/12 1 0 -19/18 0
5

Р7

0 -8/9 0 0 -1/12 0 0

-17/18

1

6 F
410/9 0 0 7/12 0 0

5/18

0

Таблица № 7

№ рядка Базис

Сб

Р0

Р1

Р2

Р3

Р4

Р5

Р6

Р7

1

Р1

5 50/17 1 0 3/34 0 0 0 -1/17
2

Р2

6 260/51 0 1 1/57 0 0 0 5/57
3

Р5

0 1608/323 0 0 -436/969 0 1 0 11/17
4

Р4

0 32/17 0 0 3/17 1 0 0 -19/17
5

Р6

0 16/17 0 0 3/34 0 0 1 -18/17
6 F
770/17 0 0 19/34 0 0 0 5/17

Х6= ( 50/17;260/51;0;32/17;1608/323;16/17) F6 = 45 5/17

Будуємо нове відсічення:

F(x1) = f(2 16/17) = f(16/17) = 16/17

F(x2) = f (5 5/51) = f(5/51) = 5/51

F(x1)> F(x2)


-3/34x3 – 16/17x7 + x8 = -16/17


таблица №8

№ рядка Базис

Сб

Р0

Р1

Р2

Р3

Р4

Р5

Р6

Р7

Р8

1

Р1

5 50/17 1 0 3/34 0 0 0 -1/17 0
2

Р2

6 260/51 0 1 1/57 0 0 0 5/57 0
3

Р5

0 1608/323 0 0 -436/969 0 1 0 22/17 0
4

Р4

0 32/17 0 0 3/17 1 0 0 -19/17 0
5

Р6

6 16/17 0 0 3/34 0 0 1 -18/17 0
6

Р8

0 -16/17 0 0 -3/34 0 0 0

-16/17

1
7 F
770/17 0 0 19/34 0 0 0 5/17 0

Таблица №9

№ рядка Базис

Сб

Р0

Р1

Р2

Р3

Р4

Р5

Р6

Р7

Р8

1

Р1

5 3 1 0 3/32 0 0 0 0 0
2

Р2

6 5 0 1 1/96 0 0 0 0 0
3

Р5

0 70/19 0 0 -521/912 0 1 0 0 0
4

Р4

0 3 0 0 9/32 1 0 0 0 0
5

Р6

0 2 0 0 3/16 0 0 1 0 0
6

Р7

0 1 0 0 3/32 0 0 0 1 1
7 F
45 0 0 17/32 0 0 0 0 0

Х*=(3; 5) F*=45


4. Геометирчна интерпретація процесу розвязку.

Геометирчна интерпретація процесу розвязку дозволяє наглядно проілюстровати процесс знаходження оптимального плану.

  1. Будують прямі, рівняння яких отримують в результаті заміни в обмеженнях знаків нерівностей на знаки =.

10x1 + 6x2 =60 (1)

-4x1 + 9x2 = 36 (2)

4x1 - 2x2 = 8 (3)

x1=0, (4)

x2=0 (5)

Графіком рівняння x1 = 0 є вісь ординат, x2 =0 – вісь абсцисс.

Графіки решти рівнянь будують так. Оскільки графіки – це прями, то достатньо для кожного рівняння знайти дві точки, задовільнюючі йому, і через них провести пряумю.

  1. Визначають область допустимих значень.

Область допустимих значень знаходиться в перший чверті координат, т.к. x1,x20 x1,x2-цілі числа

На коорд. Площині вибирають довільну точку і перевіряють виконання тотожністів рівняннях-обмеженнях. Якщо тотожність вірна, то дана нпівплощина – площина напівплощина допустимих рішень.

  1. Будують радіус-вектор.




10




М



4



(2)

6


-9


(3)


(1)


-4




10




В М



4

( I )

-38/3



(2)

6

-9


(3)


(1)


-4


В точці В, що є оптимальною за даних умов, перетикаються (I) відсічення та (1) обмеження. Знайдемо координати т.В


-3х1 + 9х2 = 38 х1=26/9

т.В (26/9; 140/27)

10х1+ 6х2 = 60 х2=140/27 F ( B) = 45 5/9


-1/12х3 – 17/18х6 = -8/9 – второе отсечение.

-1/12х3*(60 – 10х1- 6х2) – 17/18*(38 + 3х1 – 9х2) = -8/9

-2х1 + 9х2 = 40 – уравнение 2-го отсечения.

Х7= 40 + 2х1 - 92




10




В М

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

Похожие рефераты: