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

Двойственный симплекс метод

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

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

1. Изучить правило составления двойственных задач, а также формулировки и применения первой, второй и третьей теорем двойственности.

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

3. Изучить понятие псевдоплана, построение симплекс-таблицы, отвечающей псевдоплану. Освоить метод последовательного уточнения оценок. Составить и отладить программу решения задачи ЛП методом последовательного уточнения оценок.

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

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

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. Опишите алгоритм последовательного уточнения оценок.