Контрольная работа: Математичне програмування

індексний рядок симплекс метод

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

План	Базис	В	x1	x2	x3	x4	x5	x6	min
2	x3	2	0	2	1	0	1	-1	1
x4	0	0	3	0	1	1	-1	0
x1	2	1	0.5	0	0	-0.5	0.5	4
Індексний рядок	F(X2)	2	0	-1.5	0	0	-0.5	0.5+1M	0

Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х2.

План	Базис	В	x1	x2	x3	x4	x5	x6
3	x3	2	0	0	1	-0.6667	0.3333	-0.3333
x2	0	0	1	0	0.3333	0.3333	-0.3333
x1	2	1	0	0	-0.1667	-0.6667	0.6667
Індексний рядок	F(X3)	2	0	0	0	0.5	0	1M

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

Оптимальний план можна записати так:

x3 = 2

x2 = 0

x1 = 2

F(X) = 1*2 + 2*0 = 2

Складемо двоїсту задачу до прямої задачі.

2y1+2y2+2y3≥1

3y1+4y2+y3≥2

6y1+4y2+4y3 => min

y1 ≥ 0

y2 ≥ 0

y3 ≤ 0

Рішення двоїстої задачі дає оптимальну систему оцінок ресурсів.

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

З першої теореми двоїстості випливає, що Y = C*A-1.

Складемо матрицю A з компонентів векторів, що входять в оптимальний базис.

Визначивши зворотну матрицю А-1 через алгебраїчні доповнення, отримаємо:

Як видно з останнього плану симплексного таблиці, зворотна матриця A-1 розташована в стовпцях додаткових змінних .

Тоді Y = C*A-1 =

Оптимальний план двоїстої задачі дорівнює:

y1 = 0

y2 = 0.5

y3 = 0

Z(Y) = 6*0+4*0.5+4*0 = 2

Завдання 3