по дисциплине «Методы оптимизации
в управлении»
Тема: «Постановка и решение
транспортной параметрической задачи»
Москва 2013
Содержание
Введение
Задача оптимизации может быть
успешно решена с помощью ЭВМ, даже при
небольшой вычислительной мощности. При
этом качество расчета и скорость вычислений
зависит от используемого программного
обеспечения.
Существует несколько основных
алгоритмов оптимизации: методом перебора,
симплекс-методом, Двойственная задача, (решением экстремальных
уравнений или неравенств).
Многие задачи оптимизации
сводятся к отысканию наименьшего или
наибольшего значения некоторой функции,
которую принято называть целевой функцией
или критерием качества. Постановка задачи
и методы исследования существенно зависят
от свойств целевой функции и той информации
о ней, которая может считаться доступной
в процессе решения задачи, а также которая
известна до решения задачи.
Линейным программированием
называются задачи оптимизации, в которых
целевая функция является линейной функцией
своих аргументов, а условия, определяющие
их допустимые значения, имеют вид линейных
уравнений и неравенств. Линейное программирование
начало развиваться в первую очередь в
связи с задачами экономики, с поиском
способов оптимального распределения
и использования ресурсов. Оно послужило
основой широкого использования математических
методов в экономике.
Актуальность линейного программирования
и обусловила выбор темы «Постановка и
решение транспортной параметрической
задачи» данной курсовой работы. Использование
метода потенциалов линейного программирования
представляет собой важность и ценность
– оптимальный вариант выбирается из
достаточно значительного количества
альтернативных вариантов. Также все экономические
задачи, решаемые с применением линейного
программирования, отличаются альтернативностью
решения и определенными ограничивающими
условиями.
Цель курсовой работы – продемонстрировать
на конкретном примере решение задачи
линейного программирования (ЗЛП), приобрести
навыков решения задач линейного программирования
в табличном редакторе Microsoft Excel.
Задачи работы обусловлены
ее целью:
Во-первых, раскрыть теоретическое
содержание данной темы.
Во-вторых, сформулировать и
найти оптимальное решение задач с помощью
средств MS Excel.
Постановка задачи необходимо разработать программу,
решающую базовую задачу линейного программирования
методом потенциала с помощью MS Excel.
Транспортная задача является
классической задачей исследования операций.
Множество задач распределения ресурсов
сводится именно к этой задаче. Распределительные
задачи связаны с распределением ресурсов
по работам, которые необходимо выполнить.
Задачи этого класса возникают тогда,
когда имеющихся в наличии ресурсов не
хватает для выполнения каждой работы
наиболее эффективным образом. Поэтому
целью решения задачи, является отыскания
такого распределения ресурсов по работам,
при котором либо минимизируются общие
затраты, связанные с выполнением работ,
либо максимизируется получаемый в результате
общий доход.
1 Описание метода потенциалов
Метод потенциалов позволяет, исходя
из некоторого опорного плана, построить
за конечное число итераций решение транспортной
- задачи.
Метод потенциалов впервые предложили
Л. В. Канторович и М. К. Гавурин в 1949 г. Позже аналогичный метод разработал
Г. Данциг, исходя из общих идей ЛП.
Общая схема метода такова.
В данном начальном опорном плане перевозок
каждому пункту ставят в соответствие
некоторое число, называемое его предварительным
потенциалом. Предварительные потенциалы
выбирают так, чтобы их разность для любой
пары пунктов Ai и Bj, связанных основной
коммуникацией, была равна cij.
Если окажется, что разность предварительных
потенциалов для всех других коммуникаций
не превосходит cij,
то данный план перевозок – оптимальное решение задачи. В противном
случае указывают способ улучшения текущего
плана транспортной - задачи.
Описание алгоритма метода
потенциалов.
Алгоритм складывается из предварительного
этапа и конечного числа однотипных итераций.
- Проверяется тип модели транспортной
задачи и в случае открытой модели сводим ее к закрытой;
- Находится опорный план перевозок
путем составления 1-й таблицы;
- Проверяем план (таблицу) на
удовлетворение системе уравнений и на
невыражденность; в случае вырождения
плана добавляем условно заполненные клетки с помощью
« 0 »;
- Для опорного плана определяются
потенциалы ui и vj, соответствующие базисным клеткам,
по условию: ui + vj = cij
Таких уравнений будет m + n -
1 , а переменных будет m + n. Для их определения
одну из переменных полагают равной любому
постоянному значению. Обычно принимают
u1 = 0.
- После этого для небазисных
клеток опорного плана определяются оценки cij , где cij =ui + vj - cij
При этом если cij Ј0, то опорный план оптимален,
если же среди cij окажется хотя бы один положительный
элемент, то опорный план можно улучшить.
- Улучшение опорного плана осуществляется
путем целенаправленного переноса из клетки
в клетку транспортной таблицы отдельных
перевозок без нарушения баланса
по некоторому замкнутому циклу.
Циклом транспортной таблицы называется
последовательное соединение замкнутой
ломаной линией некоторых клеток, расположенных
в одном ряду (строке, столбце), причем
число клеток в одном ряду должно быть
равно двум.
Каждый цикл имеет четное число
вершин, одна из которых в клетке с небазисной
переменной, другие вершины в клетках
с базисными переменными. Клетки отмечаются
знаком «+», если перевозки в данной клетке
увеличиваются и знаком «–» в противном
случае. Цикл начинается и заканчивается
на выбранной небазисной переменной и
отмечается знаком «+». Далее знаки чередуются.
Количество единиц продукта,
перемещаемого из клетки в клетку по циклу,
постоянно, поэтому сумма перевозок в
каждой строке и в каждом столбце остаются
неизменными. Стоимость всего плана изменяется
на цену цикла.
Цена цикла – это стоимость перевозки
единицы продукта по циклу с учетом знаков
вершин.
Улучшение опорного плана осуществляется
путем нахождения цикла с отрицательной
ценой.
Если критерий оптимальности
не выполняется, то переходим к следующему
шагу. Для этого:
а) в качестве начальной небазисной
переменной принимается та, у которой
оценка cij имеет максимальное значение;
б) составляется цикл пересчета;
в) находится число перерасчета
по циклу: число X=min{Xij}, где Xij - числа в заполненных
клетках со знаком « - »;
г) составляется новая таблица,
добавляя X в плюсовые клетки и отнимая
X из минусовых клеток цикла;
Через конечное число шагов
(циклов) обязательно приходят к ответу,
так как транспортная задача всегда имеет
решение.
2 Математическая
постановка задачи об оптимальных перевозках
В общем виде задачу можно представить
следующим образом: в m пунктах производства
A1, A2, …, Am имеется однородный
груз в количестве соответственно a1, a2, …, am. Этот груз
необходимо доставить в n пунктов назначения
B1, B2, …, Bn в количестве
соответственно b1, b2, …, bn. Стоимость
перевозки единицы груза (тариф) из пункта
Ai в пункт Bj равна cij.
Требуется составить план перевозок,
позволяющий вывести все грузы и имеющий
минимальную стоимость.
Обозначим через xij количество
груза, перевозимого из пункта Ai, в пункт
Bj. Запишем условия
задачи в распределительную таблицу, которую
будем использовать для нахождения решения
(таблица. 2.1).
Таблица 2.1. Модель распределительной
таблицы.
Bi
Ai |
B1 |
B2 |
… |
Bj |
… |
Bn |
b1 |
b2 |
… |
bi |
… |
bn |
A1 a1 |
c11
x11 |
c12
x12 |
… |
с1j
x1j |
… |
c1n
x1n |
A2 a2 |
c21
x21 |
c22
x22 |
… |
c2j
x2j |
… |
c2n
x2n |
… |
… |
… |
… |
… |
… |
… |
Ai ai |
ci1
xi1 |
ci2
xi2 |
… |
cij
xij |
… |
cin
xin |
… |
… |
… |
… |
… |
… |
… |
Am am |
cm1
xm1 |
cm2
xm2 |
… |
cmj
xmj |
... |
cmn
xmn |
Математическая модель транспортной
задачи имеет вид
при ограничениях:
Оптимальным решением задачи
является матрица
удовлетворяющая системе ограничений
и доставляющая минимум целевой функции.
3 Метод решения задачи об оптимальных
перевозках средствами Ms Excel
Нахождение оптимального плана
перевозок с применением компьютерной
программы Ms Excel осуществляется посредством
функции "Поиск решения".
Схема выполнения:
1. Для удобства расчетов
необходимо отдельно создать
матрицу, отображающую стоимость перевозок
(Cij) (рисунок
3.1.), а также матрицу, которая должна будет
отображать искомый план перевозок (рисунок.
3.2.).
Рисунок 3.1 – Фрагмент окна
программы Ms Excel: Модель таблицы «Стоимость
перевозок».
2. В таблице «Стоимость
перевозок» в ячейках запасов
поставщиков и потребностей потребителей
записать количество запасов
поставщиков и потребностей потребителей
соответственно, указанное в условии задачи.
3. Таблицу "План перевозок"
создать с пустыми полями (заполненными
единицами), заранее заданного числового
формата. В ячейках запасов (потребностей)
каждого поставщика (потребителя) ввести
формулу, выполняющую суммирование всех
возможных поставок этого поставщика
(потребителя).
Рисунок 3.2 – Фрагмент окна
программы Ms Excel: Модель таблицы «План
перевозок».
4. В ячейке целевой
функции ввести формулу, высчитывающую
сумму произведений элементов
матрицы "Стоимость перевозок"
и соответствующих элементов матрицы
"План перевозок".
5. В диалоговом окне
функции "Поиск решения" установить
необходимые ограничения, в целевой ячейке
указать адрес ячейки с формулой целевой
функции и установить ее равной минимальному
значению, в качестве изменяемых ячеек
выбрать диапазон всех элементов матрицы
"План перевозок". Ограничения в "Поиске
решений" заключаются в необходимости
равенства запасов (потребностей), в матрице
"План перевозок" соответствующим
запасам и потребностям, указанным в матрице
"Стоимость перевозок". Также все
элементы матрицы "План перевозок"
должны быть неотрицательными и целочисленными.
6. В диалоговом окне "Параметры
поиска решения" установить параметр
"Линейная модель" и число итераций,
равное 100.
7. Выполнить функцию "Поиск
решения" нажатием на кнопку "Выполнить".
В качестве отчета по результатам выбрать
необходимый пункт в списке "Тип отчета"
диалогового окна «Результаты поиска
решения».
После выполнения вышеуказанных
действий при условии, что задача имеет
решение, в матрице «План перевозок» запишется
оптимальное решение задачи, т.е. оптимальный
план перевозок с указанием объемов поставок
в каждой ячейке. В ячейке с целевой функцией
запишутся совокупные затраты поставок.
4 Решение параметрической транспортной
задачи
4.1 Постановка параметрической транспортной
задачи
Имеется четыре поставщика:
A1 – ОАО”Катрен”, A2 – ОАО“СИА ИНТЕРНЕЙШЕНЛ”,
A3 – ЗАО“ПрофитМед”, A4 – ЗАО”Роста”
однородного груза лекарственных препаратов
с объемами поставок 100, 70, 70, 20 т. и три потребителя:
B1 – ООО «Родник», B2 – «36,6», B3 – «Будь
здоров» с объемами потребления 120, 80,
60 т. Стоимость транспортных расходов
задана матрицей
причем стоимость перевозки
груза от четвертого поставщика до третьего
потребителя изменяется в диапазоне 0≤k≤9.
Определить оптимальный план
перевозок, обеспечивающий минимальные
транспортные расходы.
Изобразим матричную запись
задачи (таблица. 4.1.1)
Таблица 4.1.1 – Матричная запись
задачи
Bj
Ai |
B1 |
B2 |
B3 |
120 |
80 |
60 |
A1 |
100 |
2 |
4 |
2 |
X11 |
X12 |
X13 |
A2 |
70 |
5 |
5 |
6 |
X21 |
X22 |
X23 |
A3 |
70 |
4 |
7 |
3 |
X31 |
X32 |
X33 |
A4 |
20 |
6 |
8 |
1+k |
X41 |
X42 |
X43 |
4.2. Математическая модель задачи
Целевая
функция
.
где Xij – объем поставок груза,
при ограничениях:
Xij≥0,
Подробные
ограничения по потребностям и запасам
каждого потребителя и поставщика соответственно
отражены в Таблице 4.2.1.
Таблица 4.2.1 – Ограничения по
потребностям и запасам
По
потребностям |
По
запасам |
B1 |
X11+X21+X31+X41=120 |
A1 |
X11+X12+X13=100 |
B2 |
X12+X22+X32+X42=80 |
A2 |
X21+X22+X23=70 |
B3 |
X13+X23+X33+X43=60 |
A3 |
X31+X32+X33=70 |
| |
|
A4 |
X41+X42+X43=20 |