 |
Теоремы М-метода. Определение решения основной задачи по решению М-задачи.
|
|
|
|
Правила соответствия допустимых решений основной и М-задачи:
- Допустимому решению основной задачи соответствует допустимое решение М-задачи, которое получается добавлением нулей к решению исходной задачи (т.е. искусственные переменные = 0).
- Допустимому решению М-задачи с искусственными переменными = 0соответствует допустимое решение исходной задачи, которое получается отбрасыванием = 0 искусственных переменных.
Теоремы М-метода:
1. Если М-задача имеет оптимальное решение, в котором искусственные переменные = 0, то исходная задача также имеет оптимальное решение, которое получается отбрасыванием = 0 искусственных переменных.
2. Если М-задача имеет оптимальное решение, в котором не все искусственные переменные = 0, то исходная задача не имеет допустимых решений.
3. Если М-задача не имеет оптимального решения из-за неограниченности целевой функции, то исходная задача также не имеет оптимального решения:
А) или из-за несовместности системы ограничений;
Б) или из-за неограниченности целевой функции.
Постановка и правила записи двойственной задачи.
- Прямая (x-) задача:
- Двойственная (y-) задача:
Правила записи двойственных задач:
Прежде, чем записать двойственную задачу, необходимо прямую в исходной форме записать так, чтобы целевая функция стремилась к max, а ограничения типа >=, умножив обе части неравенства на -1, преобразовалась в типа ограничения <=.
1. Каждому ограничению прямой задачи ставится в соответствие переменная двойственной задачи, которая обозначается ч/з Yi.
2. Поиск max целевой функции заменяется поиском min.
Коэффициентами целевой функции двойственной задачи являются свободные члены ограничений прямой задачи.
|
|
|
Свободные члены целевой функции прямой задачи без изменений переносятся в целевую функцию двойственной задачи.
3. В ограничения двойственной задачи записываются по столбцам переменные прямой задачи.
Свободными членами ограничений двойственной задачи являются коэффициенты целевой функции прямой задачи.
Если на переменные прямой задачи наложено условие неотрицательности, то ограничения двойственной задачи имеют тип >=, если нет – то тип равенства.
4. Если в прямой задаче ограничение имеет тип =, то на соответствующую этому ограничению переменную двойственной задачи не накладывается условие неотрицательности.
Если ограничение имеет тип <=, то соответствующая переменная в двойственной задаче неотрицательна.
Экономический смысл двойственной задачи и двойственных оценок.
Свойства двойственных оценок:
- Показывают, насколько возросло бы значение целевой функции, если величину соответствующего ресурса увеличить на 1 единицу.
- Отражают сравнительную дефицитность: чем выше двойственная оценка, тем дефицитнее соответствующий ресурс.
- Можно определить нормы заменяемости ресурсов.
Свойства двойственных задач (теоремы двойственности). Графический метод решения двойственной задачи.
Т1: Если вектор Х0 есть допустимое решение х-задачи, а Y0 есть допустимое решение y-задачи и при этом Z(X0) = T (Y0), то X0 – оптимальное решение x-задачи, а y0 – оптимальное решение y-задачи.
Т2 (основная теория двойственности):
А) Если одна из двойственных задач имеет оптимальное решение, то 2я также имеет оптимальное решение с тем же значением целевой функции.
Б) Если одна из двойственных задач не имеет оптимального решения из-за неограниченности целевой функции, то система ограничений 2ой задачи несовместна.
Т3 (условие дополняющей нежесткости):
Пусть: X* - оптимальное решение прямой задачи.
|
|
|
Y* - оптимальное решение y-задачи.
В этом случае выполняется условие дополняющей нежесткости:
1) Если i-ограничение x-задачи оптимальным решением X* обращается в строгое равенство, то соответствующая переменная y-задачи будет строго положительной.
2) Если i-ограничение выполняется как строгое неравенство, то соответствующая переменная y-задачи будет = 0.
Запись оптимального решения прямой и двойственной задач.
1. Значение целевой функции двойственной задачи = значению целевой функции прямой задачи.
2. Значения основных переменных двойственной задачи = оценкам дополнительных переменных, введенных в соответствующие ограничения прямой задачи.
Эти величины получили названия двойственных оценок ограничений (объективно обусловленных оценок).
3. Значения дополнительных переменных двойственной задачи = оценкам соответствующих основных переменных прямой задачи..
Анализ оптимального решения с помощью коэффициентов последней симпликсной таблицы и двойственных оценок ограничений.
Двойственные оценки - дополнительные переменные, введенные в соответствующие ограничения прямой задачи
Двойственная оценка ограничений показывает, как изменится значение целевой функции при изменении правой части ограничения (моделирования объема ограничения) на единицу, т.е. двойственные оценки соответствуют целевой функции.
- Тип ограничений <=:
Ненулевая двойственная оценка показывает, на сколько улучшится значение целевой функции (при решение на max – увеличится, на min – уменьшится).
При увеличении правой части ограничения на 1 остальные условия остаются без изменений.
Нулевая оценка показывает, что ограничение выполняется как строгое неравенство (есть недоиспользование ресурсов). поэтому уменьшение правой части ограничения (например, объема ресурсов) на величину, не превышающую значение дополнительных переменных, не окажет влияние на целевую функцию.
- Тип ограничений >=:
Ненулевая двойственная оценка показывает, на сколько ухудшится значение целевой функции при увеличении правой части ограничения на 1.
Нулевая двойственная оценка показывает, что ограничение выполняется как строгое неравенство, и увеличение правой части ограничения на величину, не превышающую значение дополнительных переменных, не окажет влияние на целевую функцию.
|
|
|
Коэффициенты замещения – коэффициенты структурных изменений.
- Тип ограничений <=:
1. К.з. по основным небазисным переменным (не входят в оптимальное решение):
А) Положительные к.з. показывают величину уменьшения соответствующей i-базисной переменной при введении в базис j-основной свободной переменной единичной интенсивностью.
Б) Отрицательные переменные показывают величину увеличения.
2. К.з. по дополнительным переменным:
А) Положительные к.з. показывают величину увеличения соответствующих i-базисных перемнных.
Б) Отрицательные к.з. показывают величину уменьшения соответствующих i-базисных переменных.
- Тип ограничений >=:
По дополнительным переменным, вводимым в ограничение типа >=.
При увеличении продукции на 1:
А) Положительные к.з. показывают величину уменьшения.
Б) Отрицательные к.з. – величину увеличения.
|
|
|
