Тема 10. Метод искусственного базиса. Целочисленное и динамическое программирование

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

+—-M

 

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

+—+M

 

Искусственные переменные в систему ограничений в каноническом виде вводятся с коэффициентом

+—1

 

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

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

 

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

+—по наименьшему отрицательному числу в строке (m+2)

 

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

+—по наибольшему положительному числу в (m+2)-ой строке

 

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

+—искусственные переменные

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

+—двух строках

 

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

+—столбце

 

При решении ЗЛП методом искусственного базиса коэффициенты при М в выражении записываются в симплекс – таблицу в

+—(m+2) – ю строку

 

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

+—искусственных переменных

 

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

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

 

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

+—

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

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

 

Задача целочисленного программирования это ЗЛП, в которую вводятся требование

+—переменные - целые,

 

Метод Гомори – это метод решения задач

+—целочисленного программирования

 

Если все искусственные переменные выведены из базиса (метод искусственного базиса) и план не оптимальный, то для ЗЛП на max разрешающий столбец выбирается

+—по наименьшему отрицательному числу в (m+1)-ой строке

Если при решении ЗЛП на min методом искусственного базиса , то в (m+2)- ю строку симплекс – таблицы записываются элементы

+—

Если при решении ЗЛП на max методом искусственного базиса , то в (m+2)- ю строку симплекс – таблицы записываются элементы

+—

Если все искусственные переменные выведены из базиса (метод искусственного базиса) и план не оптимальный, то для ЗЛП на min разрешающий столбец выбирается

+—по наибольшему положительному числу в (m+1)-ой строке

 

Недостатком метода Гомори является требование целочисленности

+—всех переменных (дополнительных и основных)

 

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

+—все целыми

 

Если в оптимальном плане ЗЛП несколько дробных компонент , то дополнительное ограничение (необходимое условие целочисленности) составляют для строки с

+—максимальной дробной частью

 

Дополнительное ограничение (необходимое условие целочисленности) имеет вид

—

—

—

+—

 

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

+—неделимых единиц

 

Задача целочисленного программирования решается методом

+—Гомори

 

Метод решения задач динамического программирования называется методом

+—функциональных уравнений

 

Экономический процесс называется управляемым, если

+—можно влиять на ход его развития

 

Задачи динамического программирования называются

+—многошаговыми

 

Совокупность решений, принимаемых на каждом этапе с целью влияния на ход процесса называется

+—управлением (стратегией)

 

В задаче оптимального распределения ресурсов (динамическое программирование) функциональное уравнение имеет вид

+—

—

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

+—методом искусственного базиса

 

Расширенная задача в методе искусственного базиса составляется путем введения в систему ограничений и целевую функцию

+—искусственных переменных

 

Метод функциональных уравнений является методом решения задач

+—динамического программирования

 

План ЗЛП на max при решении методом искусственного базиса будет оптимальным, если все искусственные переменные выведены из базиса и в (m+1)-ой строке все элементы будут

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

 

В динамическом программировании - это функция

+—полезности

 

Дана задача распределения капиталовложений (в млн.руб.) между 3 – мя предприятиями.

x

В ответе записать капиталовложения, полученные предприятиями, соответственно

+—

Дана задача распределения капиталовложений (в млн.руб.) между 3 – мя предприятиями.

x

В ответе записать капиталовложения, полученные предприятиями, соответственно

+—

Дана задача распределения капиталовложений (в млн.руб.) между 3 – мя предприятиями.

x

В ответе записать капиталовложения, полученные предприятиями, соответственно

+—

Дана ЗЛП

Задача решается

+—методом искусственного базиса

 

Дана ЗЛП

Функция цели расширенной задачи имеет вид

+—

Дана ЗЛП

Функция цели расширенной задачи имеет вид

+—

Дана ЗЛП

Функция цели расширенной задачи имеет вид

+—

Дана ЗЛП

Задача решается

+—методом искусственного базиса

Дана ЗЛП

Функция цели расширенной задачи имеет вид

+—

 

Дана задача распределения капиталовложений (в млн.руб.) между 3 – мя предприятиями.

x

В ответе записать капиталовложения, полученные предприятиями, соответственно

+—

Задача об эффективном распределении денежных средств между предприятиями решается методом

+—динамического программирования

В задаче об эффективном распределении денежных средств между предприятиями - это

+—количество средств, выделенных - му предприятию

 

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

+—общему доходу

Дана ЗЛП

,

Искусственные переменные вводятся в

+—2-е и 3-е ограничения

Дана ЗЛП

,

Искусственные переменные вводятся в

+—все ограничения

Дана ЗЛП

,

Искусственные переменные вводятся в

+—3-е ограничение

Дана ЗЛП

,

Искусственные переменные вводятся в

+—1-е и 3-е ограничения

Дана ЗЛП

,

Искусственные переменные вводятся в

+—2-е и 3-е ограничения

Дана ЗЛП

,

Искусственные переменные вводятся в

+—1-е и 3-е ограничения