Обоснование симплекс-метода.

↑

▷ Содержание

⇐ ПредыдущаяСтр 3 из 3

Имеется ЗЛП, представленная в форме с ограничениями-равенствами:

Пусть имеется набор переменных, который является допустимым:

В этом случае можно использовать симплекс-таблицу для получения оптимального решения.

Выполним обоснование симплекс-метода.

Определение.

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

Введем предположения:

1. ЗЛП – невырожденная.
2. ЗЛП имеет, по крайней мере, одно допустимое базисное решение.
3. Целевая функция F ограничена снизу на множестве допустимых решений.

(Существует такое с, что при любом допустимом решении, .)

При введенных предположениях справедлива следующая теорема:

Теорема.

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

Замечания по реализации симплекс-процесса.

Рассмотрим 2 случая.

1. Процесс перехода от одной симплекс-таблицы к другой невозможен:

а) в строке F нет положительных коэффициентов. В этом случае получено минимальное значение линейной формы F.

б) в F есть , но в выбранном столбце для поиска генерального элемента нет положительных коэффициентов . Это означает, что F не ограничена снизу. То есть, при все базисные переменные останутся положительными.

Пример.

1. Минимум линейной формы F не достигнут, и переход от одной к другой симплекс-таблице возможен. Но в процессе переходов симплекс- таблицы повторяются, то есть происходит «зацикливание».

Рекомендация:

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

Получение допустимого решения ЗЛП методом введения искусственного базиса.

Метод позволяет:

1. Разбить множество переменных ЗЛП на подмножества базисных и свободных переменных, при этом обеспечивая допустимое решение ЗЛП.

2. Установить, совместна ли система линейных ограничений в области неотрицательных значений переменных.

Пусть задана система линейных ограничений в виде:

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

Соотношение (**) будет справедливо, если

В силу неотрицательности очевидно, что , причем равенство нулю достигается лишь тогда, когда все . Имеем множество переменных ЗЛП, причем

- базисные переменные,

- свободные переменные.

Для решения этой задачи можно применить симплекс-метод, так как имеем допустимое решение. При этом необходимым и достаточным условием существования допустимого решения системы (*) является равенство нулю формы f. Если min f =0, это означает, что существует множество неотрицательных значений , которые обращают в нуль все .

Сформулируем правило:

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

Могут представиться два случая:

1. при этом все так же обращаются в нуль.

2. В этом случае система (*) не имеет допустимых решений.

Пример.

Введем вспомогательные переменные и представим ЗЛП в основной форме:

Далее заполняется симплекс-таблица и преобразовывается согласно алгоритму, рассмотренному в лекции 2.

Двойственность в ЗЛП

Понятие двойственности имеет значение

- Теоретического характера. Позволяет анализировать изменение оптимального решения ЗЛП в зависимости от варьирования параметров задачи (Анализ устойчивости решения);

- Практического характера. Позволяет осуществлять совершенствование методов планирования и управления.

Пример 1. Задача об использовании сырья

Оценим стоимость сырья в зависимости от доходов, которое оно приносит предприятию.

Каждый i -й ресурс имеет стоимость - .

Стоимость используемых ресурсов при производстве единицы j-го продукта будет составлять:

Стоимость используемых ресурсов не может быть меньше дохода - .

Стоимость ресурсов для производителя должна быть минимальной:

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

Рассмотренные постановки ЗЛП называются взаимодвойственными.

I. Прямая задача II. Двойственная к ней

Матрицы коэффициентов

Знаки неравенств

Условия задачи

max min

Свободные коэффициенты в системе линейных ограничений

Коэффициенты в линейной форме

Правила построения двойственной задачи

1. Если прямая задача имеет целью , то двойственная имеет целью , и наоборот.

2. Каждому ограничению прямой задачи соответствует двойственная переменная, и наоборот.

3. Матрицы ограничений прямой и двойственной задач взаимно транспонированы.

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

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

6. Перед построением двойственной задачи необходимо привести знаки всех ограничений в соответствие с линейной формой.

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

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

Познавательные статьи:



Алгоритмические операторы Matlab

Конструирование и порядок расчёта дорожной одежды

Исследования учёных: почему помогают молитвы?

Почему терпят неудачу многие предприниматели?