После подстановки значений у, = 1, уг = 2 и у3 = 0 получим следующее неравенство (проверьте!): г, + 6г2 > 4.

Таким образом, любые значения величин г1 и г2, от 0 до 1, удовлетворяющие неравенству г, + 6г2 > 4, приведут к доходности производства моделей поездов. Например, для значений гх = 0,6 и гг = 0,6 получаем z, - с, = 4 - 0,6 - 6x0,6 = -0,2. Вместе с тем отметим, что сокращение времени выполнения второй операции в 6 раз эффективнее сокращения времени выполнения первой операции.

УПРАЖНЕНИЯ 4.3.2

1. В задаче из примера 4.3.2 предположим, что время выполнения второй операции при сборке модели поезда сокращено с 3 до 1,25 минуты. На сколько должно быть сокращено время выполнения первой операции, чтобы производство этой игрушки стало доходным?

2. В задаче из примера 4.3.2 предположим, что фабрика игрушек рассматривает возможность производства еще одного вида игрушки - модели пожарной машины. При сборке этой модели первая операция не используется, а вторая и третья требуют соответственно 1 и 3 минуты для сборки одной модели. Доход от одной модели пожарной машины составляет 4 долл. Посоветуете ли вы фабрике производить эти игрушки?

3. Компания использует токарные и сверлильные станки для производства четырех типов деталей: РР1, РР2, РРЗ и РР4. В следующей таблице представлены технологические данные, характеризующие производство этих деталей.

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

4. Рассмотрите оптимальное решение задачи из предыдущего упражнения. Компания подсчитала, что с помощью специальных мероприятий можно уменьшить общее время производства изделий, не вошедших в оптимальное базисное решение, на 20%. Будет ли после этого производство таких изделий рентабельно? Если нет, то на сколько следует сократить время производства данных изделий?

4.4. РАЗНОВИДНОСТИ СИМПЛЕКС-МЕТОДА

В симплекс-методе, описанном в главе 3, решение задачи начинается с некоторого допустимого базисного решения. На последующих итерациях осуществляется переход также к допустимым базисным решениям с постепенным улучшением

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

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

Эти три алгоритма - прямой, двойственный и обобщенный - дают основу для проведения анализа чувствительности, как будет показано в разделе 4.5.

4.4.1. Двойственный симплекс-метод

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

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

Двойственное условие оптимальности. Вводимая в базис переменная определяется как переменная, на которой достигается следующий минимум:

небалисныед:

а <0

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

Чтобы существовало начальное оптимальное ( супероптимальное ) и недопустимое решение, необходимо выполнение двух условий.

1. Целевая функция должна удовлетворять условию оптимальности обычного симплекс-метода (см. главу 3).

2. Все ограничения должны быть неравенствами типа < .

Второе условие можно удовлетворить простым умножением на -1 неравенств типа > . Если есть ограничения в виде равенств, то эти равенства заменяются на два неравенства. Например, равенство хх + х2 = 2 эквивалентно двум неравенствам

хг + хг<2, x, + х2>2,

или лг, + х2<2, -jc, - jc2< -2.

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

Пример 4.4.1

Дана следующая задача ЛП.

Минимизировать z = Злг, + 2х2

при ограничениях

Зх, +x2>3, 4х, + Зх, > 6, х+х2< 3, xvx2>0.

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

Поскольку Zj - Cj < 0 для всех j= 1, 5, начальное базисное решение (х3 = -3, xt = -6, xs = 3) является оптимальным и недопустимым.

Двойственное условие допустимости указывает на переменную х4 (= -6) как на исключаемую из базиса. Теперь применим двойственное условие оптимальности для определения вводимой переменной. Для этого используем следующую таблицу.

Переменные

z-строка (q - Су) хд-строка, щ

z,-c.

Отношение

-3 -4

-2 -3

Приведенные отношения показывают, что вводимой переменной будет х2. Отметим, что переменные xf будут кандидатами на включение в базисное решение только тогда, когда коэффициент a4j будет строго отрицательным. По этому критерию переменные хъ, х4 и хъ не рассматриваются как кандидаты на включение в базис.