Курсовая работа: Постановка и решение транспортной параметрической задачи
4. Решение параметрической транспортной задачи
4.1 Постановка параметрической транспортной задачи
Имеется четыре поставщика однородного груза с объемами поставок 100, 70, 70, 20 т. и три потребителя с объемами потребления 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=70 |
||
4.3 Решение задачи аналитическим методом
Полагая k=0, по известному алгоритму составим опорное решение методом Фогеля. Полученный опорный план перевозок и алгоритм выполнения с нахождением минимальных разностей стоимостей перевозок (Cij) в каждом столбце и строке изображен на рисунке 4.3.1.
Рис. 4.3.1. Составление первого опорного решения задачи по методу Фогеля
Процесс выполнения получения опорного решения с последовательным назначением перевозок в ячейки: А4В3 - А3В3 - А3В1 - А1В1 - А1В2 - A2B2.
Проверка плана на вырожденность: m+n-1=6. План невырожденный.
Проверим опорное решение на оптимальность по методу потенциалов. Расчет потенциалов строк и столбцов для занятых из условия vi + uj = cij для занятых клеток и проверка условия vi + uj ≤ cij для незанятых приведены в таблице 4.3.1.
Решение, полученное при k=0, является оптимальным для всех
значений параметра k, удовлетворяющих
условию 
.
Из условия для свободных клеток найдем:
∆13 = v3 + u1 - c'13 = -1 + 2 - 2 = -1
∆21 = v1 + u2 - c'21 = 0 + 3 - 5 = -2
∆23 = v3 + u2 - c'23 = -1 + 3 - 6 = -4
∆32 = v2 + u3 - c'32 = 2 + 4 - 7 = -1
∆41 = v1 + u4 - c'41 = 0 + 2+k - 6 = -4 + k
∆42 = v2 + u4 - c'42 = 2 + 2+k - 8 = -4 + k
Табл. 4.3.1. Проверка первого опорного решения на оптимальность методом потенциалов
| заполненные | незаполненные | ||||
| № |
vi + uj = cij |
значения | № |
vi + uj ≤ cij |
условие |
|
А1В1 |
v1+u1=2 |
v1=0, u1=2 |
А1В3 |
v3+u1<=2 |
соблюдается |
|
А1В2 |
v2+u1=4 |
v2=2 |
А2В1 |
v1+u2<=5 |
соблюдается |
|
A2B2 |
v2+u2=5 |
u2=3 |
А2В3 |
v3+u2<=6 |
соблюдается |
|
A3B1 |
v1+u3=4 |
u3=4 |
А3В2 |
v2+u3<=7 |
соблюдается |
|
A3B3 |
v3+u3=3 |
v3= -1 |
A4B1 |
v1+u4<=6 |
соблюдается |
|
A4B3 |
v3+u4=1+k |
u4=2+k |
A4B2 |
v2+u4<=8 |
соблюдается |
Определение значений k1 и k2:
k1 = max(-aij/Bij) = 
т.к.
все Bij ≥ 0
k2 = min(-aij/Bij) = (-a41/B41; -a42/B42) = min(4;4) = 4. Все Bij > 0.
Так как по условию задачи k≥0, то оптимальное решение сохраняется при 0≥k≥4.
При этом минимальная стоимость транспортных расходов составляет:
F(X1)min = 20*(1+k) + 40*3 + 30*4 + 90*2 + 10*4 + 70*5 = 830 + 20k
Таким образом, при 
, F(X1)min = 830 + 20k и
.
Чтобы получить оптимальное решение при k≥4 перераспределим поставки товаров в клетку (4,1), где k2=4. Вновь полученное распределение с учетом изменения стоимости перевозки в ячейке A4B3 (k=4) представлено на рисунке 4.3.2.
Рис. 4.3.2. Составление второго опорного решения задачи по методу Фогеля
Процесс выполнения получения опорного решения с последовательным назначением перевозок в ячейки: А4В1 - А3В3 - А3В1 - А1В1 - А1В2 - A2B2.
Проверка плана на вырожденность: m+n-1=6. План невырожденный.
Проверим опорное решение на оптимальность по методу потенциалов. Расчет потенциалов строк и столбцов для занятых из условия vi + uj = cij для занятых клеток и проверка условия vi + uj ≤ cij для незанятых приведены в таблице 4.3.2.
Табл. 4.3.2 Проверка второго опорного решения на оптимальность методом потенциалов
| заполненные | незаполненные | ||||
| № |
vi + uj = cij |
значения | № |
vi + uj ≤ cij |
условие |
|
А1В1 |
v1+u1=2 |
v1=0, u1=2 |
А1В3 |
v3+u1<=2 |
соблюдается |
|
А1В2 |
v2+u1=4 |
v2=2 |
А2В1 |
v1+u2<=5 |
соблюдается |
|
A2B2 |
v2+u2=5 |
u2=3 |
А2В3 |
v3+u2<=6 |
соблюдается |
|
A3B1 |
v1+u3=4 |
u3=4 |
А3В2 |
v2+u3<=7 |
соблюдается |
|
A3B3 |
v3+u3=3 |
v3= -1 |
A4B2 |
v2+u4<=8 |
соблюдается |
|
A4B1 |
v1+u4=6 |
u4=6 |
A4B3 |
v3+u4<=1+k |
соблюдается |
Решение, полученное при k=4, является оптимальным для всех
значений параметра k, удовлетворяющих
условию 
.
Из условия для свободных клеток найдем:
∆13 = a3 + b1 - C'13 = -1 + 2 - 2 = -1
∆21 = a1 + b2 - C'21 = 0 + 3 - 5 = -2
∆23 = a3 + b2 - C'23 = -1 + 3 - 6 = -4
∆32 = a2 + b3 - C'32 = 2 + 4 - 7 = -1
∆42 = a2 + b4 - C'42 = 2 + 6 - 8 = 0
∆43 = a3 + b4 - (C'43 + С''43) = -1 + 6 - (1+k) = 4-k
Определение значений k1 и k2
k1 = max(-aij/Bij) = -a43/B43 = 4. Все Bij < 0
k2 = min(-aij/Bij) = 
т.к.
все Bij ≤ 0
Так как по условию задачи k ≤ 9, то оптимальное решение сохраняется при 4≥k≥9.
При этом минимальная стоимость транспортных расходов составит:
F(X2)min = 20*6 + 60*3 + 10*4 + 90*2 + 10*4 + 70*5 = 910
Таким образом, при 
F(X2)min = 910 и
.
4.4 Решение задачи средствами Ms Excel
Создадим в окне программы Ms Excel две матрицы «План перевозок» и «Стоимость перевозок», согласно вышеизложенным правилам (рис 4.4.1). Также нужно указать ячейку содержащую изменяемый параметр k. При этом в клетке A4B3 матрицы «Стоимость перевозок» устанавливаем формулу, отображающую зависимость данного тарифа от параметра k: L7=1+L9.
Рис. 4.4.1. Фрагмент окна программы Ms Excel: Матрицы «План перевозок» и «Стоимость перевозок» с изменяемым тарифом C43.
В ячейки, которые должны отображать запасы поставщиков и потребности потребителей в матрице «План перевозок» вводим формулы суммирующие значения всех возможных поставок данных поставщиков и потребителей, например: B4=СУММ(C4:E4), C3=СУММ(С4:С7).
В ячейку целевой функции (N7) введем =СУММПРОИЗВ(C4:E7;J4:L7).
Метод решения параметрической транспортной задачи средствами Ms Excel заключается в нахождении оптимального решения при каждом значении параметра k, с сохранением сценария для каждой процедуры «Поиск решения». После этого необходимо из всего диапазона изменения параметра k выделить отдельные промежутки, на которых сохраняется оптимальное решение задачи и минимальная стоимость затрат.
В диалоговом окне «Поиск решения», согласно вышеуказанным правилам установим все необходимые ограничения и ссылки на необходимые ячейки (рис. 4.4.2). Также необходимо в ограничениях указать пределы изменения параметра k, т.е. 0≤k≤9.
Рис. 4.4.2. Диалоговое окно «Поиск решения»
В диалоговом окне «Параметры поиска решения» установить необходимые параметры (рис. 4.4.3).
Рис. 4.4.3. Диалоговое окно «Параметры поиска решения»
После нажатия на кнопку «Выполнить» в диалоговом окне «Результаты поиска решения» (рис. 4.4.5) нажать «Сохранить сценарий…» и в появившемся диалоговом окне «Сохранение сценария» задать имя данному сценарию и нажать «ОК» (рис. 4.4.4.).
Рис. 4.4.4. Диалоговое окно «Сохранение сценария»
После сохранения сценария в диалоговом окне «Результаты поиска решения» выделить необходимые типы отчетов и нажать «OK» (рис. 4.4.5.).
Рис. 4.4.5. Диалоговое окно «Результаты поиска решений
После выполнения всех операций в матрице «План перевозок» получим оптимальный план перевозок при k=0 (рис. 4.4.6.).
Рис. 4.4.6. Фрагмент окна программы Ms Excel: Результат поиска решения при k=0.
Полученное значение целевой функции F(x1)min=830.
Теперь аналогичным способом найдем оптимальный план перевозок при k=1. Проведя повторный расчет, получим новый план перевозок и значение целевой функции (рис 4.4.7.).
Рис. 4.4.7. Фрагмент окна программы Ms Excel: Результат поиска решения при k=1
Полученное значение целевой функции F(x2)min = 850.
Как видно из рисунков
4.4.5. и 4.4.6 планы перевозок в обоих случаях (k=0, k=1)
одинаковы. После дальнейших расчетов при всех остальных значениях параметра k обнаружим, что при 
план
перевозок остается неизменным, изменяется лишь значение целевой функции. При
значении параметра 
«Поиск решения»
выдает другой план перевозок, и значение целевой функции на данном промежутке
остается неизменным F(x)min = 910. Полученный план перевозок при
значении k=4 изображен на рисунке 4.4.8.
Рис. 4.4.8. Фрагмент окна программы Ms Excel: Результат поиска решения при k=4
Значения целевой функции, соответствующие параметру k в каждой итерации представлены в таблице 4.4.1.
Из представленных в
таблице 4.4.1 данных можно вывести определенную закономерность изменения
значения целевой функции на промежутке 
:
F(x1)min = 830, (k=0);
F(x2)min = F(x1)min +20 = 830+20, (k=1);
F(x3)min = F(x2)min +20 = 830 + 20*2 = 870, (k=2).
Следуя по той же цепочке, найдем:
F(x4)min = 830 + 20*3, (k=3).
F(x5)min = 830 + 20*4, (k=4).
Исходя из подобной логики можно представить F(x1)min = 830 + 20*0.
Отсюда можно вывести
формулу, отображающую закономерность изменения значения целевой функции при 
:
.
Для значений 
значение функции постоянно
F(x)=910.
Таблица 4.4.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.4.9.).
Рис. 4.4.9. Диалоговое окно «Диспетчер сценариев»
С помощью «Диспетчера сценариев» можно просмотреть план перевозок и значение целевой функции, получаемые при каждом значении параметра k. Также можно просмотреть отчет, отображающий значения изменяемых ячеек в каждой из итераций.
Заключение
Ответ.
, 
, F(X1)min
= 830 + 20k.
, 
, F(X2)min
= 910.
Представленная в данной курсовой работе параметрическая транспортная задача решена двумя способами: аналитическим методом Фогеля и средствами компьютерной программы Ms Excel. Оба предложенных метода дают одинаковое решение и определяют оптимальный план перевозок товара и минимальную стоимость всех перевозок для каждого из промежутков диапазона изменения параметра, определяющего тариф одной из перевозок.
Описанная в работе задача об оптимальных перевозках и методы ее решения – только отдельный пример огромного множества задач линейного программирования. Цель транспортной задачи разработка наиболее рациональных путей и способов транспортирования товаров, устранение чрезмерно дальних, встречных, повторных перевозок. Все это сокращает время продвижения товаров, уменьшает затраты предприятий, фирм, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д.
Библиографический список
1. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом анализе: Учебник. – 3-е изд., исп. – М.: Дело, 2002. – 688 с.
2. И.Л. Акулич. Математическое программирование в примерах и задачах: учебное пособие для ВУЗов. - М.: Высшая школа, 1986 г, 319 с.
3. Т.Н. Павлова, О.А. Ракова. Линейное программирование. Учебное пособие. - Димитровград, 2002 г.
4. Т.Н. Павлова, О.А. Ракова. Решение задач линейного программирования средствами Excel. Учебное пособие. - Димитровград, 2002 г.
5. В.И. Ермаков. Сборник задач по высшей математике для экономистов. - М.: Издательство Инфра, 2001 г, 574 с.
