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

3x1+2x2≥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	min
3	x1	7	1	0	-0.03	-0.24	0	0.03	0.24	0
x2	3	0	1	0.05	-0.14	0	-0.05	0.14	3
x5	8	0	0	-0.05	0.14	1	0.05	-0.14	11
Індексний рядок	F(X3)	44	0	0	-0.02	-1.62	0	-99999.98	-99998.38	0

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

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

x1 = 7

x2 = 3

x5 = 8

F(X) = 5*7 + 3*3 = 44

Визначаємо оптимальний план двоїстої задачі до поставленої задачі лінійного програмування.

F(Y)= 14Y1+27Y2-11Y3 (max)

Обмеження:

8Y1+3Y2+0Y3≤5

-14Y1+2Y2-11Y3≤3

Y1≥0

Y2≥0

Y3≥0