p> При обмеженності:
В
Оскількі, у прямій задачі лінійного програмування звітність, найти мінімум Функції, то пріведемо першопочатково умову до вигляд
В
Для Досягнення відповідного вигляд помножімо 3-ю нерівність на -1
0х1-11х2 ≥ -11
У результаті отрімаємо наступні матріці:
В В В
Для складання двоїстої задачі лінійного програмування Знайдемо матріці А, В, СТ.
В В В
Відповідно, двоїста задача лінійного програмування матіме вигляд:
F (Y) = 14Y1 +27 Y2-11Y3 (Max)
Обмеження:
8Y1 +3 Y2 +0 Y3 ≤ 5
-14Y1 +2 Y2-11Y3 ≤ 3
Y1 ≥ 0
Y2 ≥ 0
Y3 ≥ 0
Розв'яжемо задачу лінійного програмування симплексним методом. p> Візначімо мінімальне Значення цільової Функції F (X) = 5x1 +3 x2 при Наступний Умова-обмежень.
8x1-14x2 ≥ 14
3x1 +2 x2 ≥ 27
x2 ≤ 11
Для побудова Першого опорного плану систему нерівностей пріведемо до системи рівнянь Шляхом Введення Додатковий змінніх.
Оскількі маємо змішані умови-обмеження, то введемо штучні змінні x.
8x1-14x2-1x3 + 0x4 + 0x5 + 1x6 + 0x7 = 14
3x1 + 2x2 + 0x3-1x4 + 0x5 + 0x6 + 1x7 = 27
0x1 + 1x2 + 0x3 + 0x4 + 1x5 + 0x6 + 0x7 = 11
Для постановки задачі на мінімум цільову функцію запішемо так:
F (X) = 5 x1 +3 x2 + M x6 + M x7 => min
! Зміни до основного алгоритму симплекс-методу.
План
Базис
В
x1
x2
x3
x4
x5
x6
x7
min
1
x6
14
8
-14
-1
0
0
1
0
1.75
x7
27
3
2
0
-1
0
0
1
9
x5
11
0
1
0
0
1
0
0
0
Індексний рядок
F (X1)
4100000
1099995
-1200003
-100000
-100000
0
0
0
0
Оскількі, в індексному рядку знаходяться Позитивні КОЕФІЦІЄНТИ, поточний опорний план неоптимальна, тому будуємо новий план. У якості ведучого віберемо елемент у стовбці х1, оскількі Значення коефіцієнта за модулем найбільше.
математичний модель симплексному лінійній
План
Базис
В
x1
x2
x3
x4
x5
x6
x7
min
2
x1
1.75
1
-1.75
-0.13
0
0
0.13
0
0
x7
21.75
0
7.25
0.38
-1
0
-0.38
1
3
x5
11
0
1
0
0
1
0
0
11
Індексний рядок
F (X2)
2175008.75
0
724988.25
37499.38
-100000
0
-137499.38
0
0
Даній план, такоже не оптимальні, тому будуємо вновь нову симплексній таблиці. У якості ведучого віберемо елемент у стовбці х2.
План
Базис
В
x1
x2
x3
x4
x5
x6
x7 <...
