Тема 7. Симплексный метод решения злп. Основные теоремы. Двойственные злп

План X=(х_1, х_2,…х_m, 0,…,0) ЗЛП на min будет оптимальным, если справедливы условия для j=

+—Z_j-C_j£0

План X=(х_1, х_2,…х_m, 0,…,0) ЗЛП на max будет оптимальным, если справедливы условия для j=

+—Z_j-C_j³0

Разрешающий столбец при решении ЗЛП на max целевой функции выбирается исходя из условия

+—

Разрешающий столбец при решении ЗЛП на min целевой функции выбирается исходя из условия

+—

Значение целевой функции в таблице с оптимальным планом находится

+—на пересечении строки оценок со столбцом

 

Оптимальным планом ЗЛП называется

+—опорный план, приводящий к максимуму или минимуму целевой функции

 

ЗЛП решается симплексным методом, если в ЭММ ЗЛП в каноническом виде матрица коэффициентов системы ограничений

+—содержит единичную подматрицу

 

Значения базисных переменных оптимального плана ЗЛП находятся в

+—столбце

 

При решении ЗЛП симплексным методом свободные члены системы ограничений должны быть

+—³ 0

 

При решении ЗЛП симплексным методом разрешающая строка выбирается по правилу

+—

При решении ЗЛП симплексным методом оценки находятся в симплекс – таблице в

+—(m+1)–й строке

 

При составлении симметричной пары двойственных задач, если исходная ЗЛП , , , то двойственная задача имеет вид

+—

При решении прямой ЗЛП решение двойственной задачи в симплекс – таблице с оптимальным планом получается

+—на пересечении строки оценок и столбцов, соответствующих начальному базису ЗЛП

 

Если i – е ограничение прямой ЗЛП обращается в строгое неравенство, то соответствующая компонента двойственной задачи

+—равна нулю

 

Если j – е ограничение двойственной задачи обращается в строгое неравенство, то соответствующая компонента прямой ЗЛП

+—равна нулю

 

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

+—имеет оптимальное решение и или

Если исходная ЗЛП имеет вид , , , то целевая функция симметричной двойственной задачи имеет вид

+—

Если исходная ЗЛП имеет вид , , , то целевая функция симметричной двойственной задачи имеет вид

+—

Если исходная ЗЛП имеет вид , , , то ограничения симметричной двойственной задачи имеют вид

+—

Если исходная ЗЛП имеет вид , , , то ограничения симметричной двойственной задачи имеют вид

+—

Опорным планом ЗЛП называется

+—базисное неотрицательное решение системы ограничений

 

Если множество наряду со своими точками содержит и отрезок, соединяющий любые его две точки, то оно называется

+—выпуклым

 

Множество планов ЗЛП

+—выпукло

 

Если при решении ЗЛП на максимум для некоторого фиксированного j найдется оценка , то опорный план является

+—неоптимальным

 

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

+—свободные члены системы ограничений исходной задачи

 

Свободными членами системы ограничений двойственной задачи являются

+—коэффициенты целевой функции исходной задачи

 

Если исходная ЗЛП была на максимум целевой функции, то двойственная задача будет

+—на минимум

 

Если исходная ЗЛП была на минимум целевой функции, то двойственная задача будет

+—на максимум

 

Если в исходной ЗЛП система ограничений в матричной форме имеет вид , то в двойственной ЗЛП она примет вид

+—

Если в исходной ЗЛП система ограничений в матричной форме имеет вид , то в двойственной ЗЛП она примет вид

+—

Пары двойственных задач называются симметричными, если в исходной задаче система ограничений задана в виде

+—системы неравенств

 

Пары двойственных задач называются несимметричными, если в исходной задаче система ограничений задана в виде

+—системы уравнений

 

В симметричной паре двойственных ЗЛП условие неотрицательности

+—накладывается и на исходные, и на двойственные переменные

 

В несимметричной паре двойственных ЗЛП условие неотрицательности

+—накладывается только на исходные переменные

 

Если целевая функция одной из пары двойственных задач не ограничена, то другая

+—не имеет решения

 

Если система ограничений ЗЛП имеет вид , то в начальном опорном плане базисными переменными являются

+—дополнительные переменные

 

Если при решении ЗЛП симплексным методом на max целевой функции найдется оценка и при этом все , то

+—ЗЛП не имеет решения

 

Если при решении ЗЛП симплексным методом на min целевой функции найдется оценка и при этом все , то

+—ЗЛП не имеет решения

 

При решении ЗЛП на max целевой функции в симплекс – таблице с оптимальным планом все

+—неотрицательны

 

При решении ЗЛП на min целевой функции в симплекс – таблице с оптимальным планом все

+—неположительны

 

Дана ЭММ ЗЛП:

,

, .

Число дополнительных переменных ЭММ в канонической форме равно

+—2

Дана ЭММ ЗЛП:

,

, .

Целевая функция двойственной ЗЛП имеет вид:

+—

Дана ЭММ ЗЛП:

,

, .

Максимальное значение целевой функции равно

+—

Дана ЭММ ЗЛП:

,

, .

Целевая функция двойственной ЗЛП имеет вид:

+—

Дана ЭММ ЗЛП:

,

, .

Минимальное значение целевой функции двойственной ЗЛП равно

+—6

Дана ЭММ ЗЛП:

,

, .

Число дополнительных переменных ЭММ в канонической форме равно

+—2

Если исходная ЗЛП имеет вид ,

, ,

то значения двойственных переменных в таблице с оптимальным планом находятся в столбцах

+— и

Если исходная ЗЛП имеет вид ,

, ,

то значения двойственных переменных в таблице с оптимальным планом находятся в столбцах

+— и

Если двойственная задача имеет вид ,

то в исходной задаче число переменных равно

+—3

Если исходная ЗЛП имеет вид ,

, ,

то значения двойственных переменных в таблице с оптимальным планом находятся в столбцах

+— и

Если исходная задача имеет вид ,

, ,

то коэффициентами при неизвестных целевой функции двойственной задачи являются

+—10;4

Если двойственная задача имеет вид ,

, ,

то коэффициентами при неизвестных целевой функции исходной задачи являются

+—2;3