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

Модификации симплекс метода. Методы искусственного базиса и больших штрафов

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

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

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. Опишите метод больших штрафов. Как составить M -задачу для задачи линейного программирования в канонической форме?

5. Опишите связь между исходной задачей и M -задачей. Как выбирается число M.

6. Как прочесть решение исходной задачи по решению M -задачи?