Симплексный метод

Задача 1.

Решить задачу линейного программирования симплексным методом.

Вариант 3.

Найти наибольшее значение функции f(X) = - x1 - x2 + 2x3 при ограничениях

2x1 + x2 + x3 £ 2

x1 - x2 + x3 £ 1,

xj ³ 0, j = 1, 2, 3.

Решение.

Приведем задачу к каноническому виду, вводя дополнительные неотрицательные переменные x4,5 ³ 0.

f(X) = - x1 - x2 + 2x3 ® max

2x1 + x2 + x3 + x4 = 2

x1 - x2 + x3 + x5 = 1,

xj ³ 0, j = 1, 2, 3, 4, 5.

Каноническая задача имеет необходимое число единичных столбцов, т. е. обладает очевидным начальным опорным решением.

Очевидное начальное опорное решение (0; 0; 0; 2; 1).

Решение осуществляется симплекс-методом с естественным базисом. Расчеты оформим в симплекс-таблицах

Номер симплекс-таблицыБазис

Cj

Ci

B-1-1200Q

A1

A2

A3

A4

A5

0

A4

02211102:1 = 1

A5

011-11011:1 = 1

j

-011-200
1

A4

011201-11:2 = 1/2

A3

211-1101

j

-23-1002
2

A2

-11/21/2101/2-1/2

A3

23/23/2011/21/2

j

-5/27/2001/23/2
Актуально: