Материал: kozinova_at_osharina_nn_matematika_lineinaia_algebra_analiti

Следовательно, для нашей задачи: y3o y4o y5o 0

Учитывая это, решим систему ограничений задачи:

Решение двойственной задачи можно найти, используя схему соответствия переменных взаимно-двойственных задач и оценочную строку симплекс-таблицы (табл. 2) для оптимального базисного плана:

Анализируя оценочную строку таблицы и используя предложенную схему соответствия переменных, получим:

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

106

Примечание. Задача линейного программирования может иметь неединственное решение. Наличие нуля в оценочной строке, при оценке оптимального базисного плана, в столбце неосновной переменной может говорить о наличии бесконечного множества решений у задачи линейного программирования. Альтернативный оптимальный базисный план может

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

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

Новая задача в канонической форме имеет вид:

F 6x1 6x2 max – прибыль (функция цели)

Решение задачи (табл. 3) начнем с анализа допустимого базисного плана, соответствующего оптимальному плану выпуска продукции, полученному в

остается оптимальным и в новых условиях, когда прибыль от единицы продукции первого вида составит 6 ед. Наличие нуля в оценочной строке, при оценке оптимального базисного плана, в столбце неосновной переменной x3

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

Максимальный доход предприятия при этом составит:

F o max F 66 (ед.)

Пример 5. Найдем решение задачи линейного программирования: (каноническая форма задачи)

оптимальности допустимого базисного решения при максимизации функции цели, имеются отрицательные оценочные числа F1 , F2 .

На втором шаге переведем x1 в группу основных переменных, а x4 в

группу неосновных. Выполним преобразования системы ограничений так, чтобы новая основная переменная осталась только во втором уравнении с

108

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

Таблица 4

На третьем шаге, переводя x2 в группу основных переменных, не удается отправить в число неосновных любую из переменных x1 , x3 и получить новое

6.5.Модифицированный симплексный метод

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

Модифицированная задача формируется следующим образом:

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

к левым частям уравнений системы ограничений, включающих основные переменные первоначального базисного плана с отрицательными коэффициентами, прибавляются неотрицательные искусственные переменные xk , yk ;

если в исходной задаче ведется поиск минимума функции целиZ Y min , то модифицированная функция цели принимает вид

109

ZM Z Y M yk min ,

FM F X M xk max , k

где xk − сумма искусственных переменных, и M .

k

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

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

Пример 6. Решим задачу планирования оптимальных цен ресурсов:

Z BT Y 60 y1 22 y2 7 y3 min

1 3 3 1

затраты на имеющиеся на предприятии запасы ресурсов

ограничения со стороны продавца ресурсов

Y 0 – естественные ограничения

3 1

Каноническая форма задачи имеет вид:

ZM 60 y1 22 y2 7 y3 min − функция цели

Y T 0 – естественные ограничения

1 5

110