Тема 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
40	30	28	46
80	65	70	75

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

+—

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

x
30	25	26	28
60	45	50	53

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

+—

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

x
14	11	13	10
28	21	22	20

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

+—

Дана ЗЛП

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

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

Дана ЗЛП

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

+—

Дана ЗЛП

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

+—

Дана ЗЛП

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

+—

Дана ЗЛП

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

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

Дана ЗЛП

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

+—

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

x
20	12	15	18
40	30	32	31

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

+—

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

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

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

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

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

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

Дана ЗЛП

,

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

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

Дана ЗЛП

,

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

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

Дана ЗЛП

,

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

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

Дана ЗЛП

,

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

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

Дана ЗЛП

,

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

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

Дана ЗЛП

,

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

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