тпр
.docОмский государственный технический университет
Кафедра «Автоматизированные системы обработки информации и управления»
КУРСОВОЙ ПРОЕКТ
по дисциплине «Математическое программирование»
Пояснительная записка
Руководитель проекта:
Зыкина А.В.
Разработал студент гр. Ас–312
Долуман В.А.
Омск - 2005
СОДЕРЖАНИЕ
ЗАДАНИЕ
8. Распределить машин по мастерским
Фирма имеет три авторемонтные мастерские, которые обслуживают три автотранспортных депо. Затраты на техобслуживание и ремонт в различных мастерских различны. Автопарк в каждом депо ограничен.
Распределить машины трех депо по мастерским на техобслуживание так, чтобы суммарные затраты фирмы были минимальными.
1 МАТЕМАТИЧЕСКАЯ МОДЕЛЬ
Авторемонтные мастерские – i
Авторемонтные депо – j
Aij – затраты j мастерской на техобслуживание i депо
Xij - i машина обслуживается в j мастерской
Bi – количество машин в i депо
L=aij*xij -> min
x11+x21+x31 <= b1
x12+x22+x32 <= b2
x13+x23+x33 < = b3
Ограничения.
– i-я машина поедет только в одно депо;
- i-я машина находится хотя бы в одном депо
, j машина в i мастерской
, иначе
Решаем полученную целевую функцию сначала симплекс методом, затем производим решение методом Гомори, так как нам нужно получить целочисленное решение.
Депо 1 Маст. 1
Депо 2 Маст. 2
Депо 3 Маст.3
2 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
2.1 Алгоритм симплекс-метода для задачи на минимум
Ш0: Приводим задачу ЛП к специальной форме.
Ш1: Составляем симплекс-таблицу, соответствующую специальной форме:
|
b |
… |
… |
|||
L |
… |
… |
||||
… |
… |
|||||
. |
. |
… |
||||
… |
… |
|||||
. |
. |
… |
||||
… |
… |
Этой таблице соответствует допустимое базисное решение задачи. Значение целевой функции на этом решении
Ш2: Проверка на оптимальность. Если среди элементов индексной строки симплекс – таблицы нет ни одного положительного элемента то, оптимальное решение задачи ЛП найдено: . Алгоритм завершает работу.
Ш3: Проверка на неразрешимость. Если среди есть положительный элемент , а в соответствующем столбце нет ни одного положительного элемента , то целевая функция L является неограниченной снизу на допустимом множестве. В этом случае оптимального решения не существует. Алгоритм завершает работу.
Ш4: Выбор ведущего столбца q. Среди элементов выбираем максимальный положительный элемент .Этот столбец объявляем ведущим.
Ш5: Выбор ведущей строки p. Среди положительных элементов столбца находим элемент , для которого выполняется равенство: . Строку p объявляем ведущей. Элемент объявляем ведущим.
Ш6: Преобразование симплексной таблицы. Составляем новую симплекс-таблицу, в которой:
а) вместо базисной переменной записываем , вместо небазисной переменной записываем ;
б) ведущий элемент заменяем на обратную величину ;
в) все элементы ведущего столбца (кроме ) умножаем на ;
г) все элементы ведущей строки (кроме ) умножаем на ;
д) оставшиеся элементы симплексной таблицы преобразуются по следующей схеме «прямоугольника».
Из элемента вычитается произведение трех сомножителей:
первый - соответствующий элемент ведущего столбца;
второй - соответствующий элемент ведущей строки;
третий - обратная величина ведущего элемента .
Преобразуемый элемент и соответствующие ему три сомножителя как раз и являются вершинами «прямоугольника».
Ш7: Переход к следующей итерации (на Ш2).
2.2 Алгоритм метода Гомори
Ш1: Симплекс-методом находим оптимальное решение задачи без учета условия целочисленности. Если задача не имеет решения, то неразрешима и исходная задача ЦЛП. В случае алгоритм завершает работу.
Ш2: Пусть оптимальная таблица имеет вид:
|
b |
… |
||
L |
… |
|||
. |
… |
|||
. |
. |
… |
||
… |
Если элементы – целые, то оптимальное решение является целочисленным. В этом случае вычисления заканчиваем. Иначе, переходим к следующему шагу.
Ш3: Среди дробных компонент таблицы выбираем элемент с максимальной дробной частью и по строке i составляем дополнительное ограничение:
Здесь - целая часть числа (наибольшее целое число, не превышающее число ).
Ш4: Добавляем построенное ограничение к последней симплекс-таблице и, применяя двойственный симплекс-метод, находим оптимальное решение. Переходим к Ш2.
-
Признаком отсутствия целочисленного решения служит появление в таблице хотя бы одной строки с дробным свободным членом и целыми остальными коэффициентами (поскольку соответствующее уравнение неразрешимо в целых числах).
-
На Ш4 двойственный симплекс-метод применяется до тех пор, пока не будет получена оптимальная симплексная таблица (возможно потребуется несколько итераций).
Если на Ш4 в базис вводится переменная дополнительного ограничения , то эта строка вычеркивается из симплексной таблицы (соответствующее ограничение является избыточным).
2.3 Алгоритм двойственного симплекс-метода
Ш0: Начинаем с симплексной таблицы
|
b |
… |
||
L |
… |
|||
… |
||||
. |
. |
… |
||
… |
где .
Ш1: Проверка на оптимальность. Если , то решение - оптимальное.
Ш2: Выбор ведущей строки. Выбираем среди номеров i, для которых , номер k с максимальным по модулю значением: . Строка k объявляется ведущей.
Ш3: Проверка на неразрешимость. Если в строке нет отрицательных элементов, то двойственная целевая функция неограничена и, следовательно, прямая задача не имеет допустимых решений. Процесс решения завершается.
Ш4: Выбор ведущего столбца s. Выбираем среди отрицательных элементов строки элемент с номером s, для которого выполняется равенство :. Столбец s объявляется ведущим, а элемент - ведущим элементом.
Ш5: Проводим стандартное преобразование симплексной таблицы (Ш6 из прямого симплекс-метода).
3 ОПИСАНИЕ ИНТЕРФЕЙСА ПРОГРАММЫ
Главное окно программы изображено на рисунке 1
Рисунок 1
4 АНАЛИЗ МОДЕЛИ НА ЧУВСТВИТЕЛЬНОСТЬ
Проведем анализ на чувствительность задачи линейного программирования: