3. для всіх змінних виконується умова невідємності
Якщо обмеження має вид нерівності зі знаком >=, то шляхом множення його на (-1) переходять до нерівності зі знаком <=.
Від обмежень нерівностей необхідно перейти до обмежень рівностей. Такий перехід виконується шляхом введення в ліву частину кожної нерівності додаткових незалежних невідємних змінних. При цьому знак нерівності міняють на знак рівності.
Вихідне завдання:
F = 5х1
+6х2
max
-10x1
- 6x2
³-60
-4x1
+ 9x2
£ 36
4x1
- 2x2
£ 8
x1
,x2
³0 x1
,x2
-цілі числа
Основна задача:
F = 5х1
+6х2
max
10x1
+ 6x2
+ х3
=60
-4x1
+ 9x2
+х4
= 36
4x1
- 2x2
+х5
= 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)
2. Зясовують, мається хочаб одне відємне значення врядку оцінок ( рядок 4) Якщо нема – то план оптимальний, якщо є – треба переходити до новій с-т.
Рядок оцінок має (-5) та (-6), отже данний опорний план – не оптимальний.
3. Знаходять визначальний стовпець. Стовпець називають визначальним, якщо в рядку оцінок у нього найбільше за модулем значення. Маємо стовпець Р2
|-6|>|-5|
4. Знаходимо визначальний рядок. Визанчальним назівається такий рядок, який відповідає найменшому з відношень компонентів стовпця Ро
до додатніх компонентів визначального стовпця. (Рядок оцінок до уваги не приймається)
Min = ( 60/6; 36/9) = 4 – рядок 2.
5. Будують наступну с-т .
Для цього кожний елемент таблиці перераховуємо за формулою
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
В рядку оцінок нема відємних значень, тому даний опорний план є оптимальним. Але не виконується умова цілочисельності, тому слід застосувати відсічення по методу Гоморі.
2. Застосування і побудова відсічення по методу Гоморі
х1
=54/19, х2
=100/19
До системи обмежень основного завдання добавляємо ще одну нерівність виду: F(a*ij
)*xij
>= F(b*ij
), де a*ij
і b*ij
дробови частини чисел.
Під дробовою частиною числа а розуміють найменше невідємне число в і таке, що а – в є цілим числом.Якщо в оптимальному плані вихідного завдання дробового значення приймають декілька змінних, то додаткова нерівність будується для змінної, в якої найбільша дробова частина.
Геометирчна интерпретація процесу розвязку дозволяє наглядно проілюстровати процесс знаходження оптимального плану.
1) Будують прямі, рівняння яких отримують в результаті заміни в обмеженнях знаків нерівностей на знаки =.
10x1
+ 6x2
=60 (1)
-4x1
+ 9x2
= 36 (2)
4x1
- 2x2
= 8 (3)
x1
=0, (4)
x2
=0 (5)
Графіком рівняння x1
= 0 є вісь ординат, x2
=0 – вісь абсцисс.
Графіки решти рівнянь будують так. Оскільки графіки – це прями, то достатньо для кожного рівняння знайти дві точки, задовільнюючі йому, і через них провести пряумю.
2) Визначають область допустимих значень.
Область допустимих значень знаходиться в перший чверті координат, т.к. x1
,x2
³0 x1
,x2
-цілі числа
На коорд. Площині вибирають довільну точку і перевіряють виконання тотожністів рівняннях-обмеженнях. Якщо тотожність вірна, то дана нпівплощина – площина напівплощина допустимих рішень.
3) Будують радіус-вектор.
10
М
4
(2)
6
-9
(3)
(1)
-4
10
В М
4
( I )
-38/3
(2)
6
-9
(3)
(1)
-4
В точці В, що є оптимальною за даних умов, перетикаються (I) відсічення та (1) обмеження. Знайдемо координати т.В