Розв'язок задачі лінійного програмування (стр. 2 из 4)

(8)

Таким чином вектор

є планом у тому випадку, коли його компоненти невід’ємні. За припущенням

, отже ті компоненти вектора в які входять будуть невід’ємними, тому необхідно розглядати лише ті компоненти, які містять додатні . Отже необхідно знайти таке значення , при якому для всіх буде виконуватися умова невід’ємності плану задачі:

(9)

З (3.36) отримуємо, що для шуканого

має виконуватися умова . Отже вектор буде планом задачі для будь-якого q, що задовольняє умову

,

де мінімум знаходимо по тих i, для яких

.

Опорний план не може містити більш ніж m додатних компонент, тому в плані

необхідно перетворити в нуль хоча б одну з компонент. Припустимо, що

для деякого значення і, тоді відповідна компонента плану

перетвориться в нуль. Нехай це буде перша компонента плану, тобто

.

Підставимо значення

у вираз:

,

якщо позначити

, ,

то рівняння можна подати у вигляді розкладу:

,

якому відповідає наступний опорний план:

.

Для визначення наступного плану необхідно аналогічно продовжити процес: будь-який вектор, що не входить в базис розкласти за базисними векторами, а потім визначити таке

, для якого один з векторів виключається з базису.

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

Необхідно відмітити, що для випадку коли вектор

підлягає включенню в базис, а в його розкладі всі , то, очевидно, не існує такого , який виключав би один з векторів розкладу (3.35). В такому випадку план містить m+1 додатних компонент, отже система векторів буде лінійно залежною і визначає не кутову точку багатогранника розв’язків, а функціонал не може в ній досягати свого максимального значення. Це означає, що функціонал є необмеженим на багатограннику розв’язків.

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

Теорема 1. Якщо для деякого вектора

виконується умова , то план не є оптимальним і можливо побудувати такий план Х, для якого виконуватиметься нерівність .

Доведення. Помножимо (3.39) і (3.40) на

і віднімемо результати відповідно з (3.37) та (3.38), отримаємо:

(*)

У співвідношенні до обох частин додається величина

для , додатні, тому завжди можливо знайти таке , що всі коефіцієнти при векторах були невід’ємними, іншими словами отримати новий план задачі виду:

,

якому згідно відповідає значення функціоналу

Так як за умовою теореми

і , то .

Що і потрібно було довести.

Теорема 2. Якщо для деякого вектора

виконується умова , то план не є оптимальним і можливо побудувати такий план Х, для якого виконуватиметься нерівність .

Запишемо канонічну задачу:

Розв’яжемо симплекс-методом:

1	1	0	-M	0	0
x1	x2	x3	x4	x5	x6	B	T
x4	4	3	-1	1	0	0	12	3	**
x5	-1	2	0	0	1	0	4	–
x6	1	-1	0	0	0	1	4	4
F	-1	-1	0	0	0	0	0	0
Mf	-4	-3	1	0	0	0	-12	0
**

1	1	0	-M	0	0
x1	x2	x3	x4	x5	x6	B	T
x1	1	0,75	-0,25	0,25	0	0	3	4
x5	0	2,75	-0,25	0,25	1	0	7	2,545	**
x6	0	-1,75	0,25	-0,25	0	1	1	–
F	0	-0,25	-0,25	0,25	0	0	3	0
Mf	0	0	0	1	0	0	0	0
**

1	1	0	-M	0	0
x1	x2	x3	x4	x5	x6	B	T
x1	1	0	-0,1818	0,1818	-0,2727	0	1,091	–
x2	0	1	-0,09091	0,09091	0,3636	0	2,545	–
x6	0	0	0,09091	-0,09091	0,6364	1	5,455	60	**
F	0	0	-0,2727	0,2727	0,09091	0	3,636	0
Mf	0	0	0	1	0	0	0	0
**

1	1	0	-M	0	0
x1	x2	x3	x4	x5	x6	B	T
x1	1	0	0	0	1	2	12	–
x2	0	1	0	0	1	1	8	–
x3	0	0	1	-1	7	11	60	60
F	0	0	0	0	2	3	20	0
Mf	0	0	0	1	0	0	0	0

Отже, х* = (12, 8, 60), L(x*)max = 20.

Задача 3

Для задачі побудувати двоїсту, розв’язати і за розв’язком знайти розв’язок двоїстої:

Розв’язання:

Кожна задача лінійного програмування пов’язана з іншою, так званою двоїстою задачею.