Линейное программирование, Симплекс – метод. Каким образом можно найти первоначальный план

Материалы для контроля знаний.

Контрольные вопросы по теории.

Глава№1.

Линейное программирование, Симплекс – метод.

1. Какова основная форма задачи Л.П.?

2. Что называется планом задачи Л.П.?

3. Какой план называется опорным?

4. Каково условие опорности плана?

5. Какие переменные называются базисными?

6. Как найти опорный план, если известны базисные переменные?

7. Каково условие оптимальности опорного плана?

8. В чем заключается шаг Симплекс – метода?

9. Когда при  решении задачи Л.П. Симплекс – методом делается вывод, что целевая функция неограниченна?

10. Каким  образом можно найти первоначальный план?

11. Какие условия влеку, что задача Л.П. не имеет допустимых решений?

12. Каковы этапы сведения задачи Л.П. от общей формы к основной?

13. Как исключить переменные, принимающие отрицательные значения?

14. Каким образом преобразуются ограничения неравенства?

15. Каковы этапы решения задачи Симплекс – методом?

Глава №2.

Графический метод решения задачи линейного программирования.

Вопросы по теории:

1.  Как построить прямую по уравнению ах + by = с ?

2.  Как определить полуплоскость, определяемую неравенством ах + by≤c, (ах + by≥c)

3. Как определить направление убывания (возрастания) линейной функции?

4. Каковы этапы решения задачи Л.П. с двумя переменными графическим методом?

Глава №3.

Математические модели простейших экономических задач.

1.  Какова формулировка задачи о ресурсах?

2.  Какова формулировка задачи о рационе?

3.  Какова формулировка задачи о смесях?

4.  Как графически решается задача о двухкомпонентных смесях?

Глава №4

Двойственные задачи.

1.  Сформулировать симметричную двойственную задачу

2.  Что утверждает основная теорема двойственности?

3.  Какие существую возможности связи между типами  пары самосопряженных задач?

4.  Как определить оптимальный план в симметричной двойственной задаче?

5.  Как определить знаки ограничений в двойственной задаче?

6.  Какие переменные в двойственной задаче неотрицательны?

Глава №5

Целочисленная задача Л.П.

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

2.  Как строится сечение Гомори?

3.  В каких случаях можно утверждать, что целочисленная задача Л.П. не имеет допустимых решений?

Глава№6

Транспортная задача Л.П.

1.  Как формулируется транспортная задача?

2.  Когда транспортная задача имеет решения?

3.  Как выглядит задача линейного программирования, соответствующая транспортной задаче?

4.  Как вычислить потенциалы?

5.  Каково условие оптимальности решения?

6.  Какая модель транспортной задачи называется открытой?

7.  Как открытую модель преобразовать в закрытую?

8.  Каков смысл дополнительных переменных при решении открытой модели транспортной задачи?

Глава№7

Экономические задачи, сводящиеся к транспортной модели.

1.  Какова формулировка задачи о назначении?

2.  Каким образом задача о назначении сводится к транспортной задаче?

3.  Как найти первоначальное решение транспортной задачи с запрещенными перевозками?

Глава№8

Задачи по теории графов.

1.  Каково определение графа? Ориентированного графа (орграфа)? Что такое цикл? Что такое дерево?

2.  Как формулируется задача о минимальном пути?

3.  Как записывается первоначальная таблица?

4.  Как по окончательной таблице определить минимальный путь?

Глава№9

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

1.  В чем состоит задача сетевого планирования?

2.  Как строится временной сетевой график?

3.  Что такое критический путь?

4.  Что такое резерв времени в сетевой задаче?

5.  Как выглядит формальный алгоритм сетевого планирования?

6.  Какие оптимизационные задачи ставятся в рамках сетевого планирования?

Глава№10

Динамическое программирование.

1.  Как формулируется задача об инвестировании предприятий (привести пример)?

2.  Как формулируется задача о замене оборудования (привести пример)?

3.  В чем суть задачи динамического программирования?

4.  Как формулируется задача кратчайшего пути через сеть (привести пример)?

Глава№11

Теория игр.

1.  Определить предмет и задачи теории игр.

2.  Дайте понятие матричных игр.

3.  Когда достигается равновесная ситуация матричной игры?

4.  Что такое седловая точка в матричной игре?

5.  Какие стратегии  матричной игры называются смешанными?

6.  Назовите Теоремы Теории матричных игр.

7.  Приведите алгоритм графического решения матричных игр.

8.  Рассмотрите на примере процедуру снижения размеров матрицы при помощи правила доминирования.

9.  Приведите алгоритм решения игр с помощью Линейного программирования.

Глава№12

Теория массового обслуживания

1.  Дайте определение ТМО с очередью.

2.  Дайте определение ТМО с отказом.

3.  Назовите основные показатели эффективности ТМО.

4.  Что называют интенсивностью потока события?

5.  Дайте определение стационарным потокам событий, ординарным потокам событий и потокам событий без последствий.

6.  Что называют простейшим потоком события?

7.  Начертите граф состояний ТМО с отказами и поясните его смысл.

8.  Приведите основные показатели эффективности одноканальной и многоканальной ТМО с неограниченной и ограниченной очередями.