Симплекс метод. Реферат "Решение задачи линейного программирования симплексметодом" 2008
 Скачать 358.5 Kb.
|
Области допустимых решений для двойственных переменныхВид ограничений прямой задачи, а также дополнительные и искусственные переменные, образующие начальный допустимый базис, определяют ОДР для соответствующих двойственных переменных. 1. Рассмотрим ограничение (2) прямой задачи:  Область допустимых решений ДП ( ) определяется знаками ограничений (8) и (9) двойственной задачи и знаком ограничения (2) прямой задачи. Для определения ОДР найдём ограничения ДЗ, соответствующие остаточным переменным ПЗ. Коэффициенты целевой функции для остаточных переменных равны нулю ( ).Т. о., при решении задачи максимизации ограничениям прямой задачи, имеющим знак ограничения  , соответствуют неотрицательные двойственные переменные:  . 2. Рассмотрим ограничение (3) прямой задачи:  . При введении искусственных переменных в целевую функцию вводятся коэффициенты штрафа М, поэтому для задачи максимизации получим:  . Т. о., при решении задачи максимизации ограничениям прямой задачи, имеющим знак равенства, соответствуют двойственные переменные, не ограниченные в знаке  . 3. Рассмотрим ограничение (4) прямой задачи:  В целевой функции избыточные переменные имеют коэффициенты, равные нулю ( ), а искусственные переменные коэффициенты, равные величине штрафа со своим знаком, в результате для задачи максимизации получим:  Т. о., при решении задачи максимизации ограничениям прямой задачи, имеющим знак  , соответствуют неположительные двойственные переменные  . 4. Если в прямой задаче есть переменная, неограниченная в знаке, то в двойственной задаче получатся два ограничения, имеющие одинаковые коэффициенты при двойственных переменных, но разные знаки ограничений. Для удобства решения эти ограничения сворачивают в одно со знаком равенства (тем самым число ограничений двойственной задачи сводится к числу исходных переменных прямой задачи). По аналогии можно записать условия двойственной задачи при решении задачи минимизации. Для удобства пользования некоторые соотношения при переходе от прямой задаче к двойственной приведены в таблице.
В двойственной задаче переменные могут быть неотрицательными (  ), не ограниченными в знаке ( ), неположительными ( ). При решении ДЗ, как и ПЗ должны выполняться условия неотрицательности ограничений и переменных. Для представления двойственной задачи в стандартной форме используются следующие подстановки: если переменная не ограничена в знаке, то  ; если  , то  . Такие подстановки следует использовать во всех ограничениях, содержащих эти переменные, а также в выражении для целевой функции. После приведения ДЗ к стандартному виду используется симплекс - метод. Алгоритм получения решения тот же, что и для прямой задачи. II. Практическая часть 1. Решение задачи линейного программирования графическим методом. Дана следующая задача линейного программирования (ЗЛП).      ,  1.1. Все ограничения задачи  . 1.2. Переменная  ограниченна в знаке, поэтому  . Переменная  не ограничена в знаке, поэтому вводим замену  , где  . Область допустимых решений будет ограничиваться I и IV квадрантом. 1.3. Построение ограничений и градиента целевой функции  : 1.4. Область допустимых решений – отрезок AB. 1.5. Точка А – оптимальная. Координаты т. А:   ;  ;  . 2. Решение задачи линейного программирования симплекс-методом. Прямая задача. Задачу линейного программирования для любой вершины в компактной форме можно представить в виде:   Для получения используем алгоритм, приведённый в теоретической части. 1. Переход от неравенств к равенствам по правилам введения дополнительных переменных. Исходную задачу необходимо привести к стандартной форме: введем замену по переменной  , и дополнительные переменные:     ,  Полученный вид ЗЛП не позволяет сформировать начальный допустимый базис, т. к. нельзя выделить единичные орты во втором и третьем равенствах. Для получения начального допустимого базиса введём искусственные переменные. В результате получим:    , 2. Общее число переменных определим по формуле:  =3+2+2=7, где  - число искусственных переменных. Число базисных переменных определяется числом ограничений, т. к.  , то система имеет три базисные переменные  и  небазисные переменные  . 3. Получение  - строки для СТ (0). Приведём целевую функцию к виду . Получим из (2):  , из (3):   4. Формирование симплекс – таблицы на первом шаге: Н  ачальный базисС  Т (0) РС
5. Определение разрешающего столбца. При решении задачи максимизации выбираем в | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
