 |
|
|
Архитектура Астрономия Аудит Биология Ботаника Бухгалтерский учёт Войное дело Генетика География Геология Дизайн Искусство История Кино Кулинария Культура Литература Математика Медицина Металлургия Мифология Музыка Психология Религия Спорт Строительство Техника Транспорт Туризм Усадьба Физика Фотография Химия Экология Электричество Электроника Энергетика |
ТЕМА 7. Симплексный метод решения ЗЛП. Основные теоремы
Двойственные ЗЛП.
План X=(х1, х2,…хm, 0,…,0) ЗЛП на min будет оптимальным, если справедливы условия для j= План X=(х1, х2,…хm, 0,…,0) ЗЛП на max будет оптимальным, если справедливы условия для j= Разрешающий столбец при решении ЗЛП на max целевой функции выбирается исходя из условия ! Разрешающий столбец при решении ЗЛП на min целевой функции выбирается исходя из услови Значение целевой функции в таблице с оптимальным планом находится !на пересечении строки оценок со столбцом первоначального базиса
Оптимальным планом ЗЛП называется !опорный план, приводящий к максимуму или минимуму целевой функции
ЗЛП решается симплексным методом, если в ЭММ ЗЛП в каноническом виде матрица коэффициентов системы ограничений !содержит единичную подматрицу Значения базисных переменных оптимального плана ЗЛП находятся в !столбце При решении ЗЛП симплексным методом свободные члены системы ограничений должны быть !³ 0 При решении ЗЛП симплексным методом разрешающая строка выбирается по правилу!
При решении ЗЛП симплексным методом оценки
При составлении симметричной пары двойственных задач, если исходная ЗЛП При решении прямой ЗЛП решение двойственной задачи в симплекс – таблице с оптимальным планом получается !на пересечении строки оценок и столбцов, соответствующих начальному базису ЗЛП
Если i – е ограничение прямой ЗЛП обращается в строгое неравенство, то соответствующая компонента двойственной задачи
Если j – е ограничение двойственной задачи обращается в строгое неравенство, то соответствующая компонента прямой ЗЛП
Если одна из пары двойственных задач обладает оптимальным планом, то другая !имеет оптимальное решение и
Если исходная ЗЛП имеет вид
Если исходная ЗЛП имеет вид
Если исходная ЗЛП имеет вид
Если исходная ЗЛП имеет вид
Опорным планом ЗЛП называется!базисное неотрицательное решение системы ограничений
Если множество наряду со своими точками содержит и отрезок, соединяющий любые его две точки, то оно называется !выпуклым
Множество планов ЗЛП !выпукло
Если при решении ЗЛП на максимум для некоторого фиксированного j найдется оценка
Коэффициентами при неизвестных целевой функции двойственной задачи являются !коэффициенты при неизвестных целевой функции исходной задачи
Свободными членами системы ограничений двойственной задачи являются !коэффициенты при неизвестных исходной задачи
Если исходная ЗЛП была на максимум целевой функции, то двойственная задача будет !на минимум Если исходная ЗЛП была на минимум целевой функции, то двойственная задача будет!на максимум
Если в сходной ЗЛП система ограничений в матричной форме имеет вид
Если в исходной ЗЛП система ограничений в матричной форме имеет вид
Пары двойственных задач называются симметричными, если в исходной задаче система ограничений задана в виде !системы неравенств
Пары двойственных задач называются несимметричными, если в исходной задаче система ограничений задана в виде !системы уравнений
В симметричной паре двойственных ЗЛП условие неотрицательности !накладывается и на исходные, и на двойственные переменные
В несимметричной паре двойственных ЗЛП условие неотрицательности !накладывается только на исходные переменные
Если целевая функция одной из пары двойственных задач не ограничена, то другая !не имеет решения
Если система ограничений ЗЛП имеет вид
Если при решении ЗЛП симплексным методом на max целевой функции найдется оценка Если при решении ЗЛП симплексным методом на min целевой функции найдется оценка
При решении ЗЛП на max целевой функции в симплекс – таблице с оптимальным планом все
При решении ЗЛП на min целевой функции в симплекс – таблице с оптимальным планом все
Поиск по сайту: |
!Zj-Cj£0
находятся в симплекс – таблице в !(m+1)–й строке
, 
, 
, то двойственная задача имеет вид 
!равна нулю
!равна нулю
или 
, 
, 
, 
, 
, то опорный план является !неоптимальным
, то в двойственной ЗЛП она примет вид ! 
, то в двойственной ЗЛП она примет вид ! 
, то в начальном опорном плане базисными переменными являются !значения целевой функции
и при этом все 
, то !ЗЛП не имеет решения
и при этом все 
!неотрицательны