Постановка и решение транспортной параметрической задачи
Постановка и решение
транспортной параметрической задачи
Введение
математический перевозка
транспортный компьютерный
Задача оптимизации может быть успешно решена с помощью ЭВМ,
даже при небольшой вычислительной мощности. При этом качество расчета и
скорость вычислений зависит от используемого программного обеспечения.
Существует несколько основных алгоритмов оптимизации: методом
перебора, симплекс-методом, Двойственная задача, (решением экстремальных
уравнений или неравенств).
Многие задачи оптимизации сводятся к отысканию наименьшего
или наибольшего значения некоторой функции, которую принято называть целевой
функцией или критерием качества. Постановка задачи и методы исследования
существенно зависят от свойств целевой функции и той информации о ней, которая
может считаться доступной в процессе решения задачи, а также которая известна
до решения задачи.
Линейным программированием называются задачи оптимизации, в
которых целевая функция является линейной функцией своих аргументов, а условия,
определяющие их допустимые значения, имеют вид линейных уравнений и неравенств.
Линейное программирование начало развиваться в первую очередь в связи с
задачами экономики, с поиском способов оптимального распределения и
использования ресурсов. Оно послужило основой широкого использования
математических методов в экономике.
Актуальность линейного программирования и обусловила выбор
темы «Постановка и решение транспортной параметрической задачи» данной курсовой
работы. Использование метода потенциалов линейного программирования
представляет собой важность и ценность - оптимальный вариант выбирается из
достаточно значительного количества альтернативных вариантов. Также все
экономические задачи, решаемые с применением линейного программирования,
отличаются альтернативностью решения и определенными ограничивающими условиями.
Цель курсовой работы - продемонстрировать на конкретном
примере решение задачи линейного программирования (ЗЛП), приобрести навыков
решения задач линейного программирования в табличном редакторе 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
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
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 осуществляется посредством функции «Поиск решения».
Схема выполнения:
. Для удобства расчетов необходимо отдельно создать матрицу,
отображающую стоимость перевозок (Cij) (рисунок 3.1.), а также
матрицу, которая должна будет отображать искомый план перевозок (рисунок.
3.2.).
Рисунок 3.1 - Фрагмент окна программы Ms Excel: Модель таблицы
«Стоимость перевозок».
. В таблице «Стоимость перевозок» в ячейках запасов
поставщиков и потребностей потребителей записать количество запасов поставщиков
и потребностей потребителей соответственно, указанное в условии задачи.
. Таблицу «План перевозок» создать с пустыми полями
(заполненными единицами), заранее заданного числового формата. В ячейках
запасов (потребностей) каждого поставщика (потребителя) ввести формулу,
выполняющую суммирование всех возможных поставок этого поставщика
(потребителя).
Рисунок 3.2 - Фрагмент окна программы Ms Excel: Модель таблицы «План
перевозок»
. В ячейке целевой функции ввести формулу, высчитывающую
сумму произведений элементов матрицы «Стоимость перевозок» и соответствующих
элементов матрицы «План перевозок».
. В диалоговом окне функции «Поиск решения» установить
необходимые ограничения, в целевой ячейке указать адрес ячейки с формулой целевой
функции и установить ее равной минимальному значению, в качестве изменяемых
ячеек выбрать диапазон всех элементов матрицы «План перевозок». Ограничения в
«Поиске решений» заключаются в необходимости равенства запасов (потребностей),
в матрице «План перевозок» соответствующим запасам и потребностям, указанным в
матрице «Стоимость перевозок». Также все элементы матрицы «План перевозок»
должны быть неотрицательными и целочисленными.
. В диалоговом окне «Параметры поиска решения» установить
параметр «Линейная модель» и число итераций, равное 100.
. Выполнить функцию «Поиск решения» нажатием на кнопку
«Выполнить». В качестве отчета по результатам выбрать необходимый пункт в
списке «Тип отчета» диалогового окна «Результаты поиска решения».
После выполнения вышеуказанных действий при условии, что
задача имеет решение, в матрице «План перевозок» запишется оптимальное решение
задачи, т.е. оптимальный план перевозок с указанием объемов поставок в каждой
ячейке. В ячейке с целевой функцией запишутся совокупные затраты поставок.
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
|
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
|
4.3
Решение задачи средствами Ms Excel
Создадим в окне программы Ms Excel две матрицы «План
перевозок» и «Стоимость перевозок», согласно вышеизложенным правилам (рис
4.3.1). Также нужно указать ячейку содержащую изменяемый параметр k. При этом в клетке A4B3 матрицы «Стоимость
перевозок» устанавливаем формулу, отображающую зависимость данного тарифа от
параметра k:
L7=1+L9.
Рисунок 4.3.1 - Фрагмент окна программы Ms Excel: Матрицы «План
перевозок» и «Стоимость перевозок» с изменяемым тарифом C43
В ячейки, которые должны отображать запасы поставщиков и
потребности потребителей в матрице «План перевозок» вводим формулы суммирующие
значения всех возможных поставок данных поставщиков и потребителей, например: B4=СУММ (C4:E4), C3=СУММ (С4:С7).
В ячейку целевой функции (N7) введем =СУММПРОИЗВ
(C4:E7; J4:L7).
Метод решения параметрической транспортной задачи средствами Ms Excel заключается в нахождении
оптимального решения при каждом значении параметра k, с сохранением сценария
для каждой процедуры «Поиск решения». После этого необходимо из всего диапазона
изменения параметра k выделить отдельные промежутки, на которых сохраняется оптимальное
решение задачи и минимальная стоимость затрат.
В диалоговом окне «Поиск решения», согласно вышеуказанным
правилам установим все необходимые ограничения и ссылки на необходимые ячейки
(рис. 4.3.2). Также необходимо в ограничениях указать пределы изменения
параметра k,
т.е. 0≤k≤9.
Рисунок 4.3.2 - Диалоговое окно «Поиск решения»
В диалоговом окне «Параметры поиска решения» установить
необходимые параметры (рис. 4.3.3).
Рисунок 4.3.3 - Диалоговое окно «Параметры поиска решения»
После нажатия на кнопку «Выполнить» в диалоговом окне
«Результаты поиска решения» (рис. 4.3.5) нажать «Сохранить сценарий…» и в
появившемся диалоговом окне «Сохранение сценария» задать имя данному сценарию и
нажать «ОК» (рис. 4.3.4.).
Рисунок 4.3.4 - Диалоговое окно «Сохранение сценария»
После сохранения сценария в диалоговом окне «Результаты
поиска решения» выделить необходимые типы отчетов и нажать «OK» (рисунок. 4.3.5.).
Рисунок 4.3.5 - Диалоговое окно «Результаты поиска решений
После выполнения всех операций в матрице «План перевозок»
получим оптимальный план перевозок при k=0 (рисунок 4.3.6.).
Рисунок. 4.3.6 - Фрагмент окна программы Ms Excel: Результат поиска
решения при k=0
Теперь аналогичным способом найдем оптимальный план перевозок
при k=1.
Проведя повторный расчет, получим новый план перевозок и значение целевой
функции (рисунок 4.3.7.).
Рисунок 4.3.7 - Фрагмент окна программы Ms Excel: Результат поиска
решения при k=1
Полученное значение целевой функции F(x2)min = 850.
Как видно из рисунков 4.3.5. и 4.3.6 планы перевозок в обоих
случаях (k=0, k=1) одинаковы. После дальнейших расчетов при всех остальных
значениях параметра k обнаружим, что при план перевозок остается неизменным,
изменяется лишь значение целевой функции. При значении параметра «Поиск решения» выдает другой план
перевозок, и значение целевой функции на данном промежутке остается неизменным F(x)min = 910. Полученный план перевозок при
значении k=4 изображен на рисунке 4.3.8.
Рисунок 4.3.8 - Фрагмент окна программы Ms Excel: Результат поиска
решения при k=4
Значения целевой функции, соответствующие параметру k в каждой итерации
представлены в таблице 4.3.1.
Из представленных в таблице 4.3.1 данных можно вывести
определенную закономерность изменения значения целевой функции на промежутке :
F(x1)min = 830, (k=0);
F(x2)min = F(x1)min
+20 = 830+20, (k=1);(x3)min = F(x2)min
+20 = 830 + 20*2 = 870, (k=2).
Следуя по той же цепочке, найдем:
F(x4)min = 830 + 20*3, (k=3).(x5)min
= 830 + 20*4, (k=4).
Исходя из подобной логики можно представить F(x1)min = 830 + 20*0.
Отсюда можно вывести формулу, отображающую закономерность
изменения значения целевой функции при :
.
Для значений значение функции постоянно F(x)=910.
Ответ.
, , F(X1)min = 830 +
20k.
, , F(X2)min = 910.
Таблица 3.3.1 - Значения целевой функции в каждой итерации
номер итерации i
|
значение параметра ki
|
значение функции F(xi)min
|
1
|
0
|
830
|
2
|
1
|
850
|
3
|
2
|
870
|
4
|
3
|
890
|
5
|
4
|
910
|
6
|
5
|
910
|
7
|
6
|
910
|
8
|
7
|
910
|
9
|
8
|
910
|
10
|
9
|
910
|
Команда «Сервис → Сценарии» открывает диалоговое окно
«Диспетчер сценариев», которое отображает сохраненные сценарии каждой итерации
нахождения оптимального плана перевозок (рис 4.3.9.).
Рисунок 4.3.9 - Диалоговое окно «Диспетчер сценариев»
С помощью «Диспетчера сценариев» можно просмотреть план
перевозок и значение целевой функции, получаемые при каждом значении параметра k. Также можно просмотреть
отчет, отображающий значения изменяемых ячеек в каждой из итераций.
Заключение
Представленная в данной курсовой работе параметрическая
транспортная задача решена средствами компьютерной программы Ms Excel. Методом потенциалов
определяет оптимальный план перевозок товара и минимальную стоимость всех
перевозок для каждого из промежутков диапазона изменения параметра,
определяющего тариф одной из перевозок.
Описанная в работе задача об оптимальных перевозках и метод
ее решения - только отдельный пример огромного множества задач линейного
программирования.
В ходе выполнения курсовой работы были решены следующие
поставленные задачи:
Во-первых, раскрыть теоретическое содержание данной темы.
Во-вторых, сформулировать и найти оптимальное решение задач с
помощью средств MS Excel.
Цель транспортной задачи - разработка наиболее рациональных
путей и способов транспортирования товаров, устранение чрезмерно дальних,
встречных, повторных перевозок. Все это сокращает время продвижения товаров,
уменьшает затраты предприятий, фирм, связанные с осуществлением процессов
снабжения сырьем, материалами, топливом, оборудованием и т.д.
Используемая
литература
1. Кудинов Ю.И. Практическая работа в Excel: Учебное пособие. -
Липецк: ЛГТУ, 2001. - 67 с.
2. Красс М.С., Чупрынов Б.П. Основы
математики и ее приложения в экономическом анализе: Учебник. - 3-е изд., исп. -
М.: Дело, 2002. - 688 с.
. Юдин Д.Б., Гольштейн Е.Г. Задачи и
методы линейного программирования. Издательство «Советское радио» Москва -1961
. Иванов Ю.П., Лотов А.В. Математические
модели в экономике. - М.; Наука, 1979 г.
5. Т.Н. Павлова, О.А. Ракова. Решение задач
линейного программирования средствами Excel. Учебное пособие, 2002 г.