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

Розв’язок

Розв’яжемо задачу лінійного програмування симплексним методом.

Визначимо максимальне значення цільової функції F(X) = x1+2x2 за таких умов-обмежень.

2x1+3x2≤6

2x1+4x2≤4

2x1+x2≥4

Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних (перехід до канонічної форми).

2x1 + 3x2 + 1x3 + 0x4 + 0x5 = 6

2x1 + 4x2 + 0x3 + 1x4 + 0x5 = 4

2x1 + 1x2 + 0x3 + 0x4-1x5 = 4

Введемо штучні змінні x.

2x1 + 3x2 + 1x3 + 0x4 + 0x5 + 0x6 = 6

2x1 + 4x2 + 0x3 + 1x4 + 0x5 + 0x6 = 4

2x1 + 1x2 + 0x3 + 0x4-1x5 + 1x6 = 4

Для постановки завдання на максимум цільову функцію запишемо так:

F(X) = x1+2x2 - Mx6 => max

Отриманий базис називається штучним, а метод рішення називається методом штучного базису.

З рівнянь висловлюємо штучні змінні:

x6 = 4-2x1-x2+x5

які підставимо в цільову функцію:

F(X) = x1 + 2x2 - M(4-2x1-x2+x5) => max

або

F(X) = (1+2M)x1+(2+1M)x2+(-1M)x5+(-4M) => max

Матриця коефіцієнтів A = a(ij) цієї системи рівнянь має вигляд:

Вирішимо систему рівнянь відносно базисних змінних:

x3, x4, x6,

Вважаючи, що вільні змінні рівні 0, отримаємо перші опорний план:

X1 = (0,0,6,4,0,4)

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