Пусть необходимо найти оптимальный план производства

двух видов продукции х\ и Х2 (табл. 5.2).

Т а б л и ц а 5.2

Исходные данные примера

Вид

продукции

1

! 2

Объем ресурса

Норма расхода ресурса

на единицу прибыли

А

5

20

20

В

8

4

36

Прибыль

на единицу изделия

7

3

-

1. Построим ОМ

F(x) = 1х\ + 3*2 -> тах;

5х\ + 2*2 < 20 — ограничение по ресурсу А\

%х\ + 4^2 - 36 — ограничение по ресурсу В.

2. Преобразуем задачу в приведенную каноническую форму.

Для этого достаточно ввести дополнительные переменные хз и

Х4. В результате неравенства преобразуются в строгие равенства:

5х\ + 2x2 + хз = 20,

8xi + 4x2 + х4 = 36.

Построим исходную симплексную таблицу и найдем начальное

базисное решение. Им будет пара значений дополнительных

переменных, которым соответствует единичная подматрица

хз = 20 и х4 = 36.

Базисные

переменные

*з

х4

FJ-CJ

Свободные

члены (план)

20

36

-

*i

5

8

7

*2

2

4

3

*з

1

0

0

х4

0

1

0

1-я итерация. Находим генеральный столбец и генеральную

строку:

max (7, 3) = 7,

. Г20 36^ 20

Генеральный элемент равняется 5.

Базисные

переменные

Л'1

*4

FJ-CJ

Свободные

члены (план)

4

4

28

XI

1

0

0

*2

0,4

0,8

0,2

*з

0,2

-1,6

-1,4

*4

0

1

0

2-я итерация. Найденное базисное решение не является оптимальным,

так как строка оценок (Fj - Cj) содержит один положительный

элемент. Находим генеральный столбец и генеральную

строку:

max (0, 0,3,-1,4, 0) =0,2,

mm

_4_._4_

0,4' 0,8

_4_

0,8

Базисные

переменные

х\

*2

FJ-CJ

Свободные

члены (план)

2

5

29

*1

1

0

0

*2

0

1

0

*з

1

-2

-1

Х4

-0,5

1,25

-0,25

Найденное решение оптимально, так как все специальные

оценки целевой функции (Fj - Cj) равны нулю или отрицательны.

F(x) = 29; х\ = 2; Х2 = 5.