Порядок выполнения лабораторной работы

Исследование операций

Лабораторная работа №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 для НЕ двойственного СМ),

которая называется наименьшим симплексным отношением.

Строка с индексом i ₀ называется разрешающей строкой СТ, а элемент – разрешающим или ключевым элементом.

Структура нового опорного плана будет следующей:

.

Переход к новой симплексной таблице, называемый симплексным преобразованием, осуществляется по следующим правилам:

1. Элементы разрешающей строки i ₀ в новой симплексной таблице, включая β _i0, должны быть заменены на элементы вида:

.

Заметим, что на месте разрешающего элемента будет находиться элемент

.

2. Элементы разрешающего столбца j ₀ исходной СТ должны быть заменены на

.

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