3. Перебор базисных решений при поиске оптимального решения в задачах линейного программирования.

Приступим к решению задачи (1) вторым способом. Вместо вершин многоугольника OABCEF будем перебирать базисные решения системы линейных уравнений, полученной из системы ограничений-неравенств. Изучив этот метод и сопоставив его с графическим методом перебора вершин многоугольника ограничений, мы окажемся в двух шагах от симплексного метода.

Сначала заменим ограничения-неравенства в задаче (1) ограничениями–равенствами. Для этого потребуются новые дополнительные переменные. Если произведено Х₁ изделий вида I₁ и X₂ изделий вида I₂, то количество неизрасходованного сырья вида S₁, которое обозначим , можно вычислить по формуле

= 35- (2X₁ + 3X₂).

Аналогично для неизрасходованных количеств сырья видов S₂ S₃ S₄, обозначенных соответственно , , , получим

= 21 - (2X₁ + X₂),

= 40 – (X₁ + 4X₂),

= 45 - (5X₁ + X₂).

Как и переменные X₁ и X₂, введенные дополнительные переменные неотрицательны.

 0,

 0,

 0,

 0.

Таким образом, введя новые переменные , , и , мы вместо ограничений-неравенств получили следующие ограничения – равенства:

+2X₁ + 3X₂ =35,

+2X₁ + X₂ =21, (3)

+ X₁ + 4X₂ =40,

+5X₁ + X₂ =45.

Система (3)состоит из четырех уравнений и содержит 6 неизвестных. Ситуация, когда число уравнений в системе ограничений-равенств меньше числа неизвестных, типична для задач линейного программирования. Если число уравнений в системе ограничений-равенств равно числу неизвестных и определитель системы не равен нулю, то единственное решение этой системы будет оптимальным решением. Понятно, что этот случай малоинтересен.

Запишем расширенную матрицу системы (3).

1.000 .000 .000 .000 2.000 3.000 35.000

.000 1.000 .000 .000 2.000 1.000 21.000

.000 .000 1.000 .000 1.000 4.000 40.000

.000 .000 .000 1.000 5.000 1.000 45.000

Здесь и далее используются три знака после запятой, ноль целых не печатается.

Очевидно, что переменные , , и в системе (3) можно рассматривать как базисные переменные, которые выражаются через свободные переменные X₁ и X₂, обозначающие количества произведенных изделий. Как обычно, свободным переменным можно присваивать произвольные значения и затем по ним вычислять значения базисных переменных. Но здесь поступим иначе. А именно, будем присваивать свободным переменным только ноль, что имеет четкую экономическую интерпретацию.

Если одна из переменных , , , , например, является свободной, то =0 означает отсутствие неизрасходованного сырья второго вида. Полагая = 0, мы тем самым требуем, чтобы сырье второго вида было израсходовано полностью, т. е. стало дефицитным.

Если же одна из переменных X₁ или X₂ , например, X₁ является свободной переменной, то, полагая X₁=0, мы требуем, чтобы изделие первого вида не производилось вовсе.

Если к расширенной матрице системы снизу приписать строку коэффициентов целевой функции, то получим таблицу, которую называют симплексной таблицей.

X₁ X₂

1.000 .000 .000 .000 2.000 3.000 35.000

.000 1.000 .000 .000 2.000 1.000 21.000

.000 .000 1.000 .000 1.000 4.000 40.000

.000 .000 .000 1.000 5.000 1.000 45.000

.000 .000 .000 .000 7.000 5.000 .000

Строка с обозначениями переменных перед каждой симплексной таблицей не обязательна, хотя она всегда подразумевается. Отметим, что целевая функция должна быть выражена через свободные переменные, т. е. записанные в симплексную таблицу коэффициенты целевой функции являются коэффициентами перед переменными, которые в ограничениях задачи являются свободными.

В качестве базисных переменных можно выбрать и другие переменные. Сколькими способами можно выбрать 4 базисные переменные из 6-ти переменных? Очевидно, таких способов .

Нужно быстро распознавать свободные и базисные переменные в симплексной таблице. Столбцы из единичек и нулей, как правило, соответствуют базисным переменным. Остальные столбцы, кроме последнего, соответствуют свободным переменным.

Ниже представлены 15 последовательно сменяемых симплексных таблиц, соответствующих разным выборам свободных и базисных переменных. Оказывается, каждой из 15-ти симплексных таблиц соответствует точка на графике, представленном на рис. 1. Каждая таблица, кроме первой, получается из предыдущей изменением статуса двух переменных: одна из свободных переменных переводится в категорию базисных переменных, и одна из базисных переменных становится свободной переменной.

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

Полезно выразить старые свободные переменные целевой функции через новые свободные переменные и результаты вычислений сравнить с числами в последней строке таблицы.

Номера базисных переменных указаны перед каждой таблицей. Например, 1236 означает, что , , и X₂ - базисные переменные. Единички в символе 111001, расположенном ниже, обозначают те же базисные переменные , , и X₂, а нули обозначают свободные переменные и X₁. Таким образом, обозначения “1236” и “111001” дублируют друг друга.

BAPIAHT 1

2X₁ + 3X₂ 35

2X₁ + 1X₂ 21

1X₁ + 4X₂ 40

5X₁ + 1X₂ 45

7X₁ + 5X₂

1234

111100 - такой выбор переменных соответствует точке О(0,0)

X₁ X₂

1.000 .000 .000 .000 2.000 3.000 35.000

.000 1.000 .000 .000 2.000 1.000 21.000

.000 .000 1.000 .000 1.000 4.000 40.000

.000 .000 .000 1.000 5.000 1.000 45.000

.000 .000 .000 .000 7.000 5.000 .000

1235

111010 - такой выбор переменных соответствует точке F(9,0)

1.000 .000 .000 -.400 .000 2.600 17.000

.000 1.000 .000 -.400 .000 .600 3.000

.000 .000 1.000 -.200 .000 3.800 31.000

.000 .000 .000 .200 1.000 .200 9.000

.000 .000 .000 -1.400 .000 3.600 -63.000

1236

111001 - такой выбор переменных соответствует точке P(0,45)

1.000 .000 .000 -3.000 -13.000 .000 -100.000

.000 1.000 .000 -1.000 -3.000 .000 -24.000

.000 .000 1.000 -4.000 -19.000 .000 -140.000

.000 .000 .000 1.000 5.000 1.000 45.000

.000 .000 .000 -5.000 -18.000 .000 -225.000

1256

110011 - такой выбор переменных соответствует точке V(7.368, 8.158)

1.000 .000 -.684 -.263 .000 .000 -4.211

.000 1.000 -.158 -.368 .000 .000 -1.895

.000 .000 -.053 .211 1.000 .000 7.368

.000 .000 .263 -.053 .000 1.000 8.158

.000 .000 -.947 -1.211 .000 .000 -92.368

1246

110101 - такой выбор переменных соответствует точке A(0,10)

1.000 .000 -.750 .000 1.250 .000 5.000

.000 1.000 -.250 .000 1.750 .000 11.000

.000 .000 -.250 1.000 4.750 .000 35.000

.000 .000 .250 .000 .250 1.000 10.000

.000 .000 -1.250 .000 5.750 .000 -50.000

1245

110110 - такой выбор переменных соответствует точке T(40,0)

1.000 .000 -2.000 .000 .000 -5.000 -45.000

.000 1.000 -2.000 .000 .000 -7.000 -59.000

.000 .000 -5.000 1.000 .000 -19.000 -155.000

.000 .000 1.000 .000 1.000 4.000 40.000

.000 .000 -7.000 .000 .000 -23.000 -280.000

1345

101110 - такой выбор переменных соответствует точке N(10.5, 0)

1.000 -1.000 .000 .000 .000 2.000 14.000

.000 -.500 1.000 .000 .000 3.500 29.500

.000 -2.500 .000 1.000 .000 -1.500 -7.500

.000 .500 .000 .000 1.000 .500 10.500

.000 -3.500 .000 .000 .000 1.500 -73.500

1346

101101 - такой выбор переменных соответствует точке L(0, 21)

1.000 -3.000 .000 .000 -4.000 .000 -28.000

.000 -4.000 1.000 .000 -7.000 .000 -44.000

.000 -1.000 .000 1.000 3.000 .000 24.000

.000 1.000 .000 .000 2.000 1.000 21.000

.000 -5.000 .000 .000 -3.000 .000 -105.000

1356

101011 - такой выбор переменных соответствует точке E(8,5)

1.000 -4.333 .000 1.333 .000 .000 4.000

.000 -6.333 1.000 2.333 .000 .000 12.000

.000 -.333 .000 .333 1.000 .000 8.000

.000 1.667 .000 -.667 .000 1.000 5.000

.000 -6.000 .000 1.000 .000 .000 -81.000

1456

100111 - такой выбор переменных соответствует точке H(6.286, 8.429)

1.000 -.714 -.571 .000 .000 .000 -2.857

.000 -2.714 .429 1.000 .000 .000 5.143

.000 .571 -.143 .000 1.000 .000 6.286

.000 -.143 .286 .000 .000 1.000 8.429

.000 -3.286 -.429 .000 .000 .000 -86.143

3456

001111 - такой выбор переменных соответствует точке C(7, 7)

-1.750 1.250 1.000 .000 .000 .000 5.000

.750 -3.250 .000 1.000 .000 .000 3.000

-.250 .750 .000 .000 1.000 .000 7.000

.500 -.500 .000 .000 .000 1.000 7.000

-.750 -2.750 .000 .000 .000 .000 -84.000

2456

010111 - такой выбор переменных соответствует точке B(4, 9)

-1.400 1.000 .800 .000 .000 .000 4.000

-3.800 .000 2.600 1.000 .000 .000 16.000

.800 .000 -.600 .000 1.000 .000 4.000

-.200 .000 .400 .000 .000 1.000 9.000

-4.600 .000 2.200 .000 .000 .000 -73.000

2356

011011 - такой выбор переменных соответствует точке Z(7.692, 6.538)

-.231 1.000 .000 -.308 .000 .000 -.923

-1.462 .000 1.000 .385 .000 .000 6.154

-.077 .000 .000 .231 1.000 .000 7.692

.385 .000 .000 -.154 .000 1.000 6.538

-1.385 .000 .000 -.846 .000 .000 -86.538

2346

011101 - такой выбор переменных соответствует точке K(0, 11.667)

-.333 1.000 .000 .000 1.333 .000 9.333

-1.333 .000 1.000 .000 -1.667 .000 -6.667

-.333 .000 .000 1.000 4.333 .000 33.333

.333 .000 .000 .000 .667 1.000 11.667

-1.667 .000 .000 .000 3.667 .000 -58.333

2345

011110 - такой выбор переменных соответствует точке G(17.500, 0)

-1.000 1.000 .000 .000 .000 -2.000 -14.000

-.500 .000 1.000 .000 .000 2.500 22.500

-2.500 .000 .000 1.000 .000 -6.500 -42.500

.500 .000 .000 .000 1.000 1.500 17.500

-3.500 .000 .000 .000 .000 -5.500 -122.500

Далее повторение 15-ти предыдущих таблиц в другом формате с двумя знаками после запятой (выбирай формат по вкусу).

1234

111100 - такой выбор переменных соответствует точке О(0,0)

X₁ X₂

1 0 0 0 2 3 35

0 1 0 0 2 1 21

0 0 1 0 1 4 40

0 0 0 1 5 1 45

0 0 0 0 7 5 0

1235

111010 - такой выбор переменных соответствует точке F(9,0)

1 0 0 -0,4 0 2,6 17

0 1 0 -0,4 0 0,6 3

0 0 1 -0,2 0 3,8 31

0 0 0 0,2 1 0,2 9

0 0 0 -1,4 0 3,6 -63

1236

111001 - такой выбор переменных соответствует точке P(0,45)

1 0 0 -3 -13 0 -100

0 1 0 -1 -3 0 -24

0 0 1 -4 -19 0 -140

0 0 0 1 5 1 45

0 0 0 -5 -18 0 -225

1256

110011 - такой выбор переменных соответствует точке V(7.368, 8.158)

1 0 -0,68 -0,26 0 0 -4,21

0 1 -0,15 -0,36 0 0 -1,89

0 0 -0,05 0,21 1 0 7,37

0 0 0,26 -0,05 0 1 8,16

0 0 -0,94 -1,21 0 0 -92,36

1246

110101 - такой выбор переменных соответствует точке A(0,10)

1 0 -0,75 0 1,25 0 5

0 1 -0,25 0 1,75 0 11

0 0 -0,25 1 4,75 0 35

0 0 0,25 0 0,25 1 10

0 0 -1,25 0 5,75 0 -50

1245

110110 - такой выбор переменных соответствует точке T(40,0)

1 0 -2 0 0 -5 -45

0 1 -2 0 0 -7 -59

0 0 -5 1 0 -19 -155

0 0 1 0 1 4 40

0 0 -7 0 0 -23 -280

1345

101110 - такой выбор переменных соответствует точке N(10.5, 0)

1 -1 0 0 0 2 14

0 -0,49 1 0 0 3,5 29,5

0 -2,5 0 1 0 -1,5 -7,49

0 0,5 0 0 1 0,5 10,5

0 -3,49 0 0 0 1,5 -73,5

1346

101101 - такой выбор переменных соответствует точке L(0, 21)

1 -3 0 0 -4 0 -28

0 -3,99 1 0 -6,99 0 -43,99

0 -0,99 0 1 3 0 24

0 1 0 0 2 1 21

0 -4,99 0 0 -2,99 0 -104,99

1356

101011 - такой выбор переменных соответствует точке E(8,5)

1 -4,33 0 1,33 0 0 4

0 -6,33 1 2,33 0 0 12

0 -0,33 0 0,33 1 0 8

0 1,67 0 -0,66 0 1 5

0 -5,99 0 1 0 0 -81

1456

100111 - такой выбор переменных соответствует точке H(6.286, 8.429)

1 -0,71 -0,57 0 0 0 -2,85

0 -2,71 0,43 1 0 0 5,14

0 0,57 -0,14 0 1 0 6,29

0 -0,14 0,29 0 0 1 8,43

0 -3,28 -0,42 0 0 0 -86,14

3456

001111 - такой выбор переменных соответствует точке C(7, 7)

-1,74 1,25 1 0 0 0 5

0,75 -3,25 0 1 0 0 3

-0,24 0,75 0 0 1 0 7

0,5 -0,5 0 0 0 1 7

-0,74 -2,75 0 0 0 0 -84

2456

010111 - такой выбор переменных соответствует точке B(4, 9)

-1,39 1 0,8 0 0 0 4

-3,79 0 2,6 1 0 0 16

0,8 0 -0,59 0 1 0 4

-0,19 0 0,4 0 0 1 9

-4,59 0 2,2 0 0 0 -72,99

2356

011011 - такой выбор переменных соответствует точке Z(7.692, 6.538)

-0,23 1 0 -0,3 0 0 -0,92

-1,46 0 1 0,38 0 0 6,15

-0,07 0 0 0,23 1 0 7,69

0,38 0 0 -0,15 0 1 6,54

-1,38 0 0 -0,84 0 0 -86,53

2346

011101 - такой выбор переменных соответствует точке K(0, 11.667)

-0,33 1 0 0 1,33 0 9,33

-1,33 0 1 0 -1,66 0 -6,66

-0,33 0 0 1 4,33 0 33,33

0,33 0 0 0 0,67 1 11,67

-1,66 0 0 0 3,67 0 -58,33

2345

011110 - такой выбор переменных соответствует точке G(17.500, 0)

-0,99 1 0 0 0 -2 -13,99

-0,49 0 1 0 0 2,5 22,5

-2,49 0 0 1 0 -6,5 -42,49

0,5 0 0 0 1 1,5 17,5

-3,49 0 0 0 0 -5,5 -122,5

-----------------------------------------------------------------

Для каждой симплексной таблицы можно выписать значения свободных переменных, равные нулю и соответствующие им значения базисных переменных. Например, для первой таблицы.

=35,

=21,

=40,

=45.

X₁ =0,

X₂ =0.

Такие значения переменных означают, что еще ничего не произведено, раз X₁ =0 и X₂ =0, и поэтому сырье не расходовалось, значения остальных переменных равны первоначальным запасам сырья =35, =21, =40, =45. А раз ничего не произведено, то доход равен нулю, и число в правом нижнем углу таблицы равно нулю.

Из второй таблицы имеем

=17,

=3,

=31,

=0.

X₁ =9,

X₂ =0.

Произведено X₁ =9 единиц продукции первого вида и не производилась продукция второго вида (X₂=0), и поэтому первоначальные запасы сырья уменьшились. Осталось =17, =3, =31, =0. Сырье вида S₄ израсходовано полностью ( =0), оно стало дефицитным.

Нулевые значения свободных переменных не являются результатом вычислений. Здесь свободным переменным X₂ и присвоены нулевые значения, причем мы сами, как договорились ранее, присваиваем нули этим свободным переменным.

Стоимость произведенной продукции (число в правом нижнем углу таблицы нужно умножить на минус один) равна 63, что непосредственно проверяется умножением числа произведенных изделий X₁=9 на стоимость одного изделия C₁=7.

Для третьей таблицы получаем

= - 100,

= - 24,

= -140,

= 0.

X₁ =0,

X₂ =45.

Базисные значения переменных , , отрицательны, нарушены условия неотрицательности переменных. В связи с этим третью таблицу и еще 8 других таблиц можно было бы исключить из рассмотрения, но мы этого не делаем и рассматриваем все возможности выбора базисных переменных. Даже в случае, когда нарушены условия неотрицательности переменных, можно дать экономическую интерпретацию полученным результатам: на производство 45 единиц продукции второго вида будут израсходованы запасы всех видов сырья и потребуется дополнительно еще 100 единиц сырья первого вида, 24 единицы сырья второго вида и 140 единиц сырья третьего вида. С использованием этих дополнительных ресурсов доход составит 225 единиц.

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

Аналогично можно выписать значения свободных и базисных переменных из остальных таблиц.

Если проигнорировать таблицы с нарушением условия неотрицательности переменных, то метод перебора базисных решений приведет нас к оптимальному решению, которое содержится в 11-ой таблице.

-1.750 1.250 1.000 .000 .000 .000 5.000

.750 -3.250 .000 1.000 .000 .000 3.000

-.250 .750 .000 .000 1.000 .000 7.000

.500 -.500 .000 .000 .000 1.000 7.000

-.750 -2.750 .000 .000 .000 .000 -84.000

Из этой таблицы получаем

= 0,

= 0,

= 5,

= 3.

X₁ =7,

X₂ =7.

Стоимость произведенной продукции (число в правом нижнем углу нужно умножить на минус один) равна 84. Это и есть максимальный доход, который можно получить, если изготовить X₁ =7 изделий первого вида и X₂ =7 изделий второго вида. Подставляя X₁ =7 и X₂ =7 в целевую функцию F(X₁, X₂) = 7X₁ + 5X₂, получим то же самое число 84.

При получении максимального дохода сырье первого вида ( = 0) и сырье второго вида ( = 0) израсходовано полностью. Эти виды сырья дефицитны. Недефицитными, т. е. не использованными полностью, являются сырье третьего вида ( = 5) и сырье четвертого вида ( = 3).