Исследование операций
Лабораторная работа №1
МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.
Контрольные вопросы
1. Постановка задачи линейного программирования. Свободные и базисные переменные.
2. Привилегированная форма ограничений.
3. Симплексные таблицы. Построение начального опорного плана.
4. Критерий оптимальности опорного плана.
5. Симплексное преобразование.
6. Двойственная задача.
7. Двойственный симплекс-метод или М-задача?
ЛИТЕРАТУРА
1. Сухарев А. Г., Тимохов А. В., Федоров В. В. Курс методов оптимизации. – М.: Наука, Главная редакция физико-математической литературы, 1986. – 328 с.
2. Кузнецов А. В., Сакович В. А., Холод Н. И. Высшая математика: математическое программирование: Учебник для студ. экон. спец. вузов. – Минск: Выш. шк., 1994. – 286 с.
3. Аладьев В. З., Шишаков М. Л. Введение в среду пакета Mathematica 2.2. – М.: Инф.-издат. дом "Филинъ", 1997. – 368 с.
Часть 1. СИМПЛЕКС-МЕТОД
Цель – изучение универсального метода решения задач линейного программирования (ЗЛП) – симплекс-метода (СМ).
Указания по организации самостоятельной работы студентов
Перед тем, как приступить к выполнению лабораторной работы, следует изучить [3, с. 11-62]. Здесь цветом выделены важные замечания.
Объектом исследования является задача линейного программирования, представленная в каноническом виде:
(1)
Необходимо найти точку 
из области допустимых решений (ОДР) 
, доставляющую целевой функции 
оптимальное значение.
Теоретические сведения
Симплексный метод решения задач линейного программирования является итерационным методом и состоит из следующих трёх этапов:
1. Построение начального опорного плана;
2. Формулировка критерия оптимальности опорного плана;
3. Переход к не худшему опорному плану и в конечном итоге к оптимальному плану 
, доставляющему оптимальное значение целевой функции .
Любую корректно сформулированную задачу линейного программирования можно представить в виде:
(2)
Система ограничений-равенств имеет предпочтительный вид, и получается из (1) методом Жордана-Гаусса. Переменные 
называются базисными переменными (БП), а переменные 
– свободными переменными (СП).
В этом случае начальный опорный план будет иметь следующую структуру:
.
Внимание!! Все параметры aij и bi брать после выделения базиса, записав систему в предпочтительном виде (2). Выбирать базис так, чтобы bi³0. Эти условия необходимы! Обойти трудности с выбором базиса можно, введя искусственный базис (см. лекция 3 и программа SimplexWin).
Используя связь между БП и СП, преобразуем выражение для целевой функции таким образом, чтобы оно содержало только свободные переменные:
где 
;
.
Из последней формулы непосредственно следует, что
.
Величины 
называются оценками свободных переменных.
Исследуемая задача линейного программирования может быть наглядно представлена в виде таблицы, называемой симплексной таблицей (СТ).
Симплексная таблица, соответствующая начальному опорному плану 
, будет иметь вид:
| БП | 
| 
| 
| 
|
| 
| |||
| 
| 
| 
| |
| 
| 
|
(Внимание! В разных источниках внешний вид симплекс-таблиц может различаться.)
Очевидно, что для базиса 
.
Анализ последней (m +1)-й строки симплексной таблицы позволяет сформулировать критерий оптимальности опорного плана:
если решается задача линейного программирования на максимум и для некоторого опорного плана все 
, то этот опорный план – оптимальный;
если решается задача на минимум и для некоторого опорного плана все 
, то этот опорный план – оптимальный.
Рассмотрим задачу на максимум.
Если для некоторого значения индекса j 0 оценка СП 
, то следует перейти к не худшему опорному плану и соответствующей ему новой симплексной таблице. Столбец, находящийся в СТ над оценкой называют разрешающим столбцом СТ, а переменную 
– разрешающей переменной. Увеличив значение СП 
можно увеличить значение целевой функции. Для того, чтобы не выйти при этом за пределы ОДР , увеличение следует производить на величину
(≥0 для НЕ двойственного СМ),
которая называется наименьшим симплексным отношением.
Строка с индексом i 0 называется разрешающей строкой СТ, а элемент 
– разрешающим или ключевым элементом.
Структура нового опорного плана будет следующей:
.
Переход к новой симплексной таблице, называемый симплексным преобразованием, осуществляется по следующим правилам:
1. Элементы разрешающей строки i 0 в новой симплексной таблице, включая β i0, должны быть заменены на элементы вида:
.
Заметим, что на месте разрешающего элемента будет находиться элемент
.
2. Элементы разрешающего столбца j 0 исходной СТ должны быть заменены на
.
3. Все остальные элементы новой симплексной таблицы могут быть найдены по формулам:
После перехода к новой симплексной таблице и определения не худшего опорного плана следует проверить критерий оптимальности и, в случае его невыполнения, построить следующий опорный план и т. д. до нахождения оптимального решения.
Порядок выполнения лабораторной работы
Изучить симплексный метод решения задач линейного программирования.
Переписать систему ограничений-равенств своего варианта из таблицы 1 в предпочтительном виде.
Заполнить симплекс-таблицу и проделать вручную 1 шаг.
Составить схему алгоритма.
Составить программу на одном из алгоритмических языков или пакетов.
Вывести на печать промежуточные результаты, показывающие процесс решения; значение точки экстремума 
и функции в точке экстремума 
.
Решить ту же задачу с применением программы simplexWin, инсталлировав ее в открытую для пользователя папку, например, C:\temp
Получить последовательность симплекс-таблиц для вашего варианта. Результаты вывести в Excel и сравнить. Программа решает любой тип задачи, самостоятельно преобразуя задачу на минимум в стандартную задачу на максимум: F ® - F и добавляет (- Mz) даже там, где можно обойтись! (Метод искусственных переменных – «М -задача» описан в лекции №3). Ваши промежуточные таблицы зависят от выбора начального базиса и могут не совпасть с полученными программой. Для вырожденной прямой задачи обратную задачу эта прога может решить неверно.
Решить ту же задачу с применением встроенной функции пакета “Mathematica”.
rr=Maximize[2x[1]-4x[2]+x[3]+30,
3x[1]-3x[2]+x[3]-x[4]==4&&
-4x[1]-x[2]-3x[3]-x[5]==-12&&
x[1]>=0&&
x[2]>=0&&
x[3]>=0&&
x[4]>=0&&
x[5]>=0,
{x[1],x[2],x[3],x[4],x[5]}]
out -> {36,{x[1]®3,x[2]®0,x[3]®0,x[4]®5,x[5]®0}}
Замечание. В версиях 4, и ниже пакета Mathematica вместо Maximize[] работает встроенная функция ConstrainMax.
Вместо пакета Mathematica можно пользоваться любым другим, например, Mathcad.
Сделанное занести в отчет:
Дата, Лаб.№ и название. Группа, ФИО, №вар. Исходные данные. Симплекс-таблица ручного расчета. Программа и результаты. Все таблицы в simplexWin. Проверка расчета в “Mathematica”, Выводы. Теорию из методички переносить не надо J
