Задания к лабораторным работам

Лабораторная работа 1. Свойства области допустимых решений задачи линейного программирования

1.1. По содержательному описанию экономической задачи построить математическую модель задачи линейного программирования. Привести задачу к канонической форме. В канонической форме модель должна содержать 3-4 ограничения и 5-6 переменных.

1.2. Найти все базисные решения с помощью диалоговой системы решения и анализа задач линейного программирования IBLP.

1.3. Решить задачу графически в пространстве двух произвольно выбранных свободных переменных. Произвести вручную необходимые для этого преобразования задачи к симметричной форме. Отобразить на графике все базисные решения, выделить среди них опорные.

1.4. Повторить все геометрические построения в пространстве двух других свободных переменных.

1.5. Пользуясь полученными графиками, сформулировать свойства области допустимых решений задачи линейного программирования. Объяснить, в каких случаях число базисных решений будет меньше теоретически возможного.

Лабораторная работа 2. Симплекс-метод. Варианты разрешимости задачи линейного программирования

2.1. По содержательному описанию экономической задачи построить математическую модель задачи линейного программирования.

2.2. Найти начальный опорный план методом вспомогательной задачи и оптимальное решение симплекс-методом вручную и в обучающем режиме работы диалоговой системы решения и анализа задач линейного программирования IBLP. Объяснить правила перехода от одной симплекс-таблицы к другой (признак оптимальности, возможность улучшения плана, выбор переменных, вводимой и выводимой из базиса).

2.3. Изменить условия задачи так, чтобы

– задача имела единственное оптимальное решение;

– задача имела множество оптимальных решений. Записать его параметрически;

– задача была неразрешима из-за неограниченности целевой функции;

– задача была разрешима при неограниченности области допустимых решений;

– задача имела вырожденное оптимальное решение;

– задача была неразрешима из-за несовместности системы ограничений;

– задача разрешима и требует применения метода искусственного базиса.

Сформулировать аналитические признаки указанных ситуаций. Дать геометрическую интерпретацию каждого варианта.

2.5. Для сгенерированной задачи линейного программирования с 10 ограничениями и 15 переменными в симметричной форме найти оптимальные решения задач максимизации и минимизации симплекс-методом в обучающем режиме работы диалоговой системы IBLP. В отчете привести количество итераций, общее время решения каждой задачи и среднее время, затраченное на одну итерацию.