Page 221 - 4685

х(1) x(5) b
х(3) 155/2 0
х(4) 15 0 280
х(5) 1/5 1 25
J 1,2 0 35
Правила перерахунку елементів таблиці:
1. 1 Ÿ, Ÿ → 1; 1A, Ÿ → 0,
5
2. 1 Ÿ, H → + $,= . 25 = .
+ $,$ 35 7
3. 0 A → 0A − +,$ +$,= . 1000 − [b׎Œb = 375.
+ $,$ `b
4. 1 A, H → 1 A, H − + ,$ + $,= . 40 − [b×[b = !bb .
+ $,$ `b Œ
5. < H → <H − + $,= ¢ $ . 1,2 − [b×!,a = 0,2.
+ $,$ `b

5-й етап рішення задачі. Повторюємо пункти 2 – 5 і отримуємо
наступну таблицю:
х(3) x(5) b
х(1) 1 0 16 29/31
х(4) 0 0 25 30/31
х(2) 0 1 12 28/31
J 0 0 38,2871
У цій таблиці отримані нульові коефіцієнти в рядку оцінки, тому
відповідне їй рішення є оптимальним:
29 28 30
41 = 16 ; 42 = 12 ; 43 = 0; 44 = 25 ; 45 = 0; £ = 38,3871.
31 31 31
Часто до величин, що визначаються, в задачі лінійного програмування
висувають вимогу цілочисельності, виходячи зі змісту змінної. Це може бути
ціле число верстатів, вагонів, кількість працюючих. Вирішення цих завдань
значно складніше. Типовими алгоритмами їх рішення є методи Гомори і
Балаша.
Подвійна задача лінійного програмування
Кожну задачу лінійного програмування можна зіставити з іншою, яка
називається подвійною по відношенню до початкової (прямої).
Пряма задача:
>
i
maxEAI : = ; < 4 ;
!
= =
K
K =!
>

h ; 1 4 ≤ 0 A = 1, … , E;
= =
K
K =!
g 4 ≥ 0H = 1, … , I.
=

Подвійна задача:

217