Материал: конспект 2

1

2

Итак, таким образом, двойственная задача несовместна (система ограничений вырожд.)

1) Для прямой задачи будет выполняться альтер. Целевая форма такой задачи лежит на –∞, либо такая задача противоречива (либо система ограничений несовместима).

Задача 2

Составим двойственную задачу

m in Р на ресурсы

ОДР – выпуклый разомкнутый сверху многогранник

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

Для того чтобы оценить оптимальный вектор х необходимо составить УДНС (Слейтера) на I для двойственной задачи

Составим УДН Слейтера для прямой задачи

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

Итак, получили оптимальный план прямой задачи без ее решения, воспользовавшись при этом 2-ой теоремой теории двойственности.

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

Проиллюстрируем особенности двойственного симплексного метода на примере следующей задачи:

Составим двойственную задачу по отношению к заданной

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

Оказывается, что отмеченный факт является необходимым и достаточным условием существования оптимального плана ЗЛП.

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

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

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

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

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

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

Идея решения ЗЛП двойственным симплексным методом в следующем: сохраняя двойственную допустимость решения, добиваются, чтобы оно было и прямодопустимым.

В связи с отмеченным алгебру двойственного симплексного метода можно указать в виде следующих правил:

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

2. Выбирают разрешающий столбец по минимуму двойственного симплексного соотношения (т. е. по минимальному отношению коэффициентов при неизвестных целевой формы к модулю отрицательных коэффициентов разрешающей строки).

3. Разрешающий элемент всегда отрицательный.

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

5. Если отрицательному коэффициенту разрешающей строки соответствуют неотрицательные значения коэффициентов при неизвестных, то двойственная задача ЗЛП не имеет решений.

Р ешим представленные ЗЛП двойственным симплексным методом

:(–2)