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


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

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



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

 
 

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

 

 
 

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

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

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

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

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

  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. Перед построением двойственной задачи необходимо привести знаки всех ограничений в соответствие с линейной формой.

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

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



Поделиться:


Последнее изменение этой страницы: 2016-04-25; просмотров: 549; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.221.26.137 (0.013 с.)