Лабораторная работа № 2

Симплекс-метод в чистом виде

Цель работы: изучение симплекс-метода для решения задачи линейного программирования с использованием симплекс-таблиц, получение навыков кодирования изученного алгоритма, отладки и тестирования соответствующих программ.

Задания для подготовки к работе

1. Выяснить: какой вид должна иметь задача ЛП, чтобы можно было применять симплекс-метод в чистом виде, а также как составляется первая симплекс-таблица?

2. Изучить алгоритм перехода от одной симплекс-таблицы к другой при решении задачи симплекс-методом.

3. Запрограммировать и отладить изученный алгоритм. В рамках подготовки тестовых данных решить вручную одну из следующих ниже задач.

Варианты заданий

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

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

1. К какому виду должна быть приведена задача линейного программирования перед применением симплекс-метода?

2. Как составить первую симплекс-таблицу?

3. Опишите порядок работы с симплекс-таблицей. Сформулируйте правило выбора разрешающего элемента.

4. В чем заключается признак того, что симплекс-таблица является последней?

5. Как прочесть решение задачи по последней симплекс-таблице?

6. В каком случае по последней симплекс-таблице можно заключить, что задача не имеет решения по причине неограниченности целевой функции на области допустимых значений?

7. Как избежать зацикливания симплекс алгоритма?

8. Что понимается под трудоемкостью симплекс метода? Что означает его экспоненциальная трудоемкость на классе всех задач линейного программирования?

9. Существуют ли алгоритмы решения задач линейного программирования полиномиальной трудоемкости? Обладает ли класс всех задач линейного программирования полиномиальной сложностью?