Шаг 4. Расчет всех элементов новой симплекс-таблицы.

Расчет новых значений элементов ключевой строки проводит­ся по формуле

^Ау^=Ау/^Ау >

где Ац — ключевой элемент.

В рассматриваемом примере (табл. 68) А^^л=40. Соответствен­но новые элементы ключевой строки будут равны:

^0=400/40=10; ^=0; ^52=40/40=1; А& =- 1/40=-0, 25; А$₄=0; ^₅ = 0; ^₆=0; ^₇ = 0; А& =1/40=0, 025.

Вычисление новых значений элементов в остальных строках симплекс-таблицы, включая индексную, производится по фор­муле

^АУ^=АУ~^АУкл^А'ы'

где Ау — значения элемента преобразуемой /-и строки, расположенного в клю­чевом столбце; А- у — элементы преобразованной ключевой строки.

Для примера проведем вычисления элементов 2-й строки:

у^₀ =12000-50-10=11500; А^ =5-50-0=5; А$₂ =50-50-1=0; ^₃=0-50-(-0, 025)=1, 25; А^ = 0-50-0=0; А$₅ =1-50-0=1; ^6=0-50-0=0; ^7 = 0-50-0=0; ^₈ =0-500, 025=-1, 25.

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

Анализ второй и последующих таблиц проводится по той же схеме. Кроме того, в этих таблицах проводится анализ размеще­ния искусственных переменных. Если на данной итерации какая-либо искусственная переменная перешла в число небазисных, то она должна быть исключена из дальнейшего рассмотрения. Фак­тически это делается путем вычеркивания из полученной симп­лекс-таблицы столбца, соответствующего искусственной пере­менной, ставшей небазисной. В целях упорядочения итерацион­ной процедуры симплекс-метода такое вычеркивание целесооб­разно считать самостоятельной итерацией. Для рассмат­риваемого примера вычеркивание единственной искусственной переменной х₈, ставшей небазисной, зафиксировано в переходе от таблицы 69 к таблице 70.

Преобразование таблиц заканчивается, если на очередной итерации достигается оптимальное решение (см. выше описание шага 1). Четвертая и пятая (последняя) симплекс-таблицы для рассматриваемого примера приведены в таблицах 71, 72.

Контроль вычислений можно осуществлять следующим обра­зом.

1. Логический контроль изменения значений целевой функ­ции: в задачах на максимум эти значения от итерации к итерации должны возрастать (не убывать), в задачах на минимум —убы­вать (не возрастать).

2. Логический контроль вычисления значений базисных пере­менных — в столбце А/о не должно появляться отрицательных чи­сел. Их появление свидетельствует о том, что, например, непра­вильно выбрана ключевая строка.

3. Расчет дополнительного столбца симплекс-таблиц (в табл. 68—72 это последний столбец), в котором размещают конт­рольные суммы, определяемые по формуле,

Я

Д', я+1~ 2^Ду- У = 0

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

Вторая симплекс-таблица задачи 14.5

1 х₄(ост.) 0 1 1500 10 0 10

2 х₅(ост.) 0 2 12000 5 0 1, 25 0 1

3 х₆(ост.) 0 3 1200 -10 0 20 0 0

4 х₇(ост.) 0 4 100 0 0 0, 025 0 0

5 *₂(осн.) 800 - 10 1 -0, 025 0 0

Индексная (^-ф 8000 -150 0 -20 0 0
строка

Третья симплекс-таблица задачи 14.5

о

12007, 25

101, 025

10, 975

71. Четвертая симплекс-таблица задачи 14.5

Пятая (последняя) симплекс-таблица задачи 14.5

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

2} ~ ^С) = ^А'ч = ^АЦ ~ Лкл Л^;, У = ОД, • - -, «,

а также по формуле (14.17). Кроме того, вычисление значений целевой функции может быть проконтролировано по исходной формуле

У' = 1

Ответ задачи находится в столбце значений базисных пере­менных последней симплексной таблицы. Из нее видно, что х_х = = 1500 га; х₂ = 90 голов; х₃ = 3200 ц; х₆ = 9800 ц; х₁ = 20 голов. Все остальные переменные, не вошедшие в базис, равны 0. Макси­мальное значение целевой функции 7, = 297 000 руб.

Проведем экономический анализ результатов решения задачи по данным последней симплексной таблицы. Из нее видно, что площадь под зерновыми культурами равна 1500 га (х! = 1500). Значение х₄, которое характеризует неиспользуемую площадь пашни, равно нулю.

Таким образом, выполняется первое ограничение каноничес­кой формы записи данной задачи (14.15):

х, +х₄ = 1500 + 0= 1500 га.

Поголовье коров в результате решения получилось равным 90 (х₂ = 90). Величина х₇ = 20 в ответе задачи характеризует факт, что на ферме хозяйства 20 ското-мест остались незанятыми. Та­ким образом, выполняется четвертое условие:

х₂ + х₇ = 90 + 20 = 110 голов.

Значение избыточной переменной х₃ = 3200 ц показывает, что плановое производство молока перекрыто на 3200 ц, что видно из пятого ограничения:

40х₂ - х₃ + х₈ = 40 ■ 90 - 3200 + 0 = 400 ц.

Значение х₆ в рассматриваемой задаче характеризует недоис­пользование кормов (х₆ = 9800 ц). Тем самым выполняется третье условие канонической записи задачи:

-10x1 + 80х₂ + х₆ = -10 ■ 1500 + 80-90 + 9800 = 2000 ц.

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

Значение переменной х₅ в решении задачи равно нулю (х₅ = 0). Это говорит о том, что ресурсы труда в оптимальном плане использованы полностью и второе условие системы огра­ничений также выполняется:

5*! + 50х₂ + х₅ = 5 • 1500 + 50 ■ 90 + 0 = 12 000 чел.-ч.

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

14.7. СХЕМА ПОСТРОЕНИЯ ДВОЙСТВЕННОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Одним из способов экономического анализа решения, его чувствительности к возможным изменениям является построе­ние так называемых двойственных задач. В принципе любой зада­че линейного программирования соответствует действенная (об­ратная) по отношению к ней; она строится по определенным правилам. Воспользуемся простой и наиболее универсальной схемой, основанной на представлении любой задачи в стандарт­ной форме, в которой все ограничения приведены к типу «=» с помощью остаточных и избыточных переменных, но без искусст­венных переменных, а правые части ограничений и все перемен­ные неотрицательны (ТахаХ. Введение в исследование опера­ций. Книга 1. - М.: Мир, 1985. - С. 133):

г=^чх^\

З

тах или тт

(14.20)

п

2> //*/=6_; ; /=1,..., т; (14.21)

у = 1

х_у> 0, у= 1,..., я, где Х[,..., х„ — совокупность основных, остаточных и избыточных переменных.

Двойственная задача по отношению к этой прямой строится по следующей схеме:

1) каждому /-му ограничению из системы (14.21) сопоставляется ассоциированная с ним двойственная переменная у,, /= \,..., т;

2) каждой переменной X/, }= {,..., п прямой задачи сопоставля­ется одно ограничение двойственной задачи (всего п ограниче­ний), причем в качестве коэффициента при переменной у-, в у'-м ограничении двойственной задачи используется /-й коэффици­ент у'-го столбца матрицы 11 ау\ I, а в качестве правых частей огра­ничений — коэффициенты с, - при переменных в выражении для целевой функции 2 прямой задачи;

3) в качестве коэффициентов при переменных у, в выражении для целевой функции ^двойственной задачи используются пра­вые части Ь-, ограничений прямой задачи;

4) на переменные у_{ изначально условия неотрицательности не накладываются (однако они могут появиться как результат при­менения п. 2 данной схемы — примеры см. ниже);

5) направление оптимизации (максимизация или минимиза­ция целевой функции) и тип ограничений для двойственной за­дачи определяются в соответствии с направлением оптимизации в прямой задаче (табл. 73).

73. Схема взаимосвязи прямой и двойственной задач

Максимизация Минимизация «>»

Минимизация Максимизация «<»

Таким образом, если, например, в задаче (14.20), (14.21) зада­на максимизация целевой функции 2, то соответствующая двой­ственная задача имеет вид

т

И^Х*, -?, —> гшп; ₍₁₄.22)

т

5> //У; > С;;./=1, -, л, (14.23)

причем двойственные переменные У\,..., у_т не ограничены в зна­ке.

Рассмотрим два конкретных примера построения двойствен­ной задачи.

Задача 14.6. Проектом внутрихозяйственного землеустройства предусмотрено коренное и поверхностное улучшение заболочен­ных (100 га) и закустаренных (140 га) пастбищ. Определить, ка­кие мероприятия и на какой площади целесообразно провести для получения максимального выхода продукции (в переводе на кормовые единицы) с улучшенных угодий. На эти мероприятия запланировано 6 млн руб. Другие исходные данные приведены в таблице 74.