Решение транспортной задачи
Процесс определения минимальных затрат. Построение математической модели транспортной задачи. Стоимость доставки единицы груза из пункта. Построение опорного плана и его улучшение. Решение двойственной транспортной задачи и анализ оптимального плана.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | контрольная работа |
Язык | русский |
Дата добавления | 14.03.2013 |
Размер файла | 22,4 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Решение транспортной задачи
Минимальные затраты составят: F(x) = 60*140 + 54*20 + 54*90 + 55*45 + 51*130 + 65*55 + 57*100 + 57*10 = 33290
Математическая модель транспортной задачи:
F = ??cijxij, (1)
при условиях:
?xij = ai, i = 1,2,…, m, (2)
?xij = bj, j = 1,2,…, n, (3)
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
1 |
2 |
3 |
4 |
5 |
Запасы |
||
1 |
70 |
71 |
74 |
75 |
60 |
140 |
|
2 |
54 |
50 |
65 |
54 |
55 |
110 |
|
3 |
55 |
51 |
50 |
61 |
55 |
175 |
|
4 |
65 |
70 |
57 |
65 |
57 |
165 |
|
Потребности |
120 |
130 |
100 |
90 |
150 |
Проверим необходимое и достаточное условие разрешимости задачи.
?a = 140 + 110 + 175 + 165 = 590; ?b = 120 + 130 + 100 + 90 + 150 = 590
Занесем исходные данные в распределительную таблицу.
1 |
2 |
3 |
4 |
5 |
Запасы |
||
1 |
70 |
71 |
74 |
75 |
60 |
140 |
|
2 |
54 |
50 |
65 |
54 |
55 |
110 |
|
3 |
55 |
51 |
50 |
61 |
55 |
175 |
|
4 |
65 |
70 |
57 |
65 |
57 |
165 |
|
Потребности |
120 |
130 |
100 |
90 |
150 |
Этап I. Поиск первого опорного плана.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
1 |
2 |
3 |
4 |
5 |
Запасы |
||
1 |
70[50] |
71 |
74 |
75[90] |
60 |
140 |
|
2 |
54 |
50[110] |
65 |
54 |
55 |
110 |
|
3 |
55[55] |
51[20] |
50[100] |
61 |
55 |
175 |
|
4 |
65[15] |
70 |
57 |
65 |
57[150] |
165 |
|
Потребности |
120 |
130 |
100 |
90 |
150 |
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
v1=70 |
v2=66 |
v3=65 |
v4=75 |
v5=62 |
||
u1=0 |
70[50] |
71 |
74 |
75[90] |
60 |
|
u2=-16 |
54 |
50[110] |
65 |
54 |
55 |
|
u3=-15 |
55[55] |
51[20] |
50[100] |
61 |
55 |
|
u4=-5 |
65[15] |
70 |
57 |
65 |
57[150] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
Выбираем максимальную оценку свободной клетки (2;4): 54
Для этого в перспективную клетку (2;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 |
2 |
3 |
4 |
5 |
Запасы |
||
1 |
70[50][+] |
71 |
74 |
75[90][-] |
60 |
140 |
|
2 |
54 |
50[110][-] |
65 |
54[+] |
55 |
110 |
|
3 |
55[55][-] |
51[20][+] |
50[100] |
61 |
55 |
175 |
|
4 |
65[15] |
70 |
57 |
65 |
57[150] |
165 |
|
Потребности |
120 |
130 |
100 |
90 |
150 |
Цикл приведен в таблице (2,4; 2,2; 3,2; 3,1; 1,1; 1,4; ).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 1) = 55. Прибавляем 55 к объемам грузов, стоящих в плюсовых клетках и вычитаем 55 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
5 |
Запасы |
||
1 |
70[105] |
71 |
74 |
75[35] |
60 |
140 |
|
2 |
54 |
50[55] |
65 |
54[55] |
55 |
110 |
|
3 |
55 |
51[75] |
50[100] |
61 |
55 |
175 |
|
4 |
65[15] |
70 |
57 |
65 |
57[150] |
165 |
|
Потребности |
120 |
130 |
100 |
90 |
150 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
v1=70 |
v2=71 |
v3=70 |
v4=75 |
v5=62 |
||
u1=0 |
70[105] |
71 |
74 |
75[35] |
60 |
|
u2=-21 |
54 |
50[55] |
65 |
54[55] |
55 |
|
u3=-20 |
55 |
51[75] |
50[100] |
61 |
55 |
|
u4=-5 |
65[15] |
70 |
57 |
65 |
57[150] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
Выбираем максимальную оценку свободной клетки (4;3): 57
Для этого в перспективную клетку (4;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 |
2 |
3 |
4 |
5 |
Запасы |
||
1 |
70[105][+] |
71 |
74 |
75[35][-] |
60 |
140 |
|
2 |
54 |
50[55][-] |
65 |
54[55][+] |
55 |
110 |
|
3 |
55 |
51[75][+] |
50[100][-] |
61 |
55 |
175 |
|
4 |
65[15][-] |
70 |
57[+] |
65 |
57[150] |
165 |
|
Потребности |
120 |
130 |
100 |
90 |
150 |
Цикл приведен в таблице (4,3; 4,1; 1,1; 1,4; 2,4; 2,2; 3,2; 3,3; ).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 1) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
5 |
Запасы |
||
1 |
70[120] |
71 |
74 |
75[20] |
60 |
140 |
|
2 |
54 |
50[40] |
65 |
54[70] |
55 |
110 |
|
3 |
55 |
51[90] |
50[85] |
61 |
55 |
175 |
|
4 |
65 |
70 |
57[15] |
65 |
57[150] |
165 |
|
Потребности |
120 |
130 |
100 |
90 |
150 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
v1=70 |
v2=71 |
v3=70 |
v4=75 |
v5=70 |
||
u1=0 |
70[120] |
71 |
74 |
75[20] |
60 |
|
u2=-21 |
54 |
50[40] |
65 |
54[70] |
55 |
|
u3=-20 |
55 |
51[90] |
50[85] |
61 |
55 |
|
u4=-13 |
65 |
70 |
57[15] |
65 |
57[150] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
Выбираем максимальную оценку свободной клетки (1;5): 60
Для этого в перспективную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 |
2 |
3 |
4 |
5 |
Запасы |
||
1 |
70[120] |
71 |
74 |
75[20][-] |
60[+] |
140 |
|
2 |
54 |
50[40][-] |
65 |
54[70][+] |
55 |
110 |
|
3 |
55 |
51[90][+] |
50[85][-] |
61 |
55 |
175 |
|
4 |
65 |
70 |
57[15][+] |
65 |
57[150][-] |
165 |
|
Потребности |
120 |
130 |
100 |
90 |
150 |
Цикл приведен в таблице (1,5; 1,4; 2,4; 2,2; 3,2; 3,3; 4,3; 4,5; ).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 4) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
5 |
Запасы |
||
1 |
70[120] |
71 |
74 |
75 |
60[20] |
140 |
|
2 |
54 |
50[20] |
65 |
54[90] |
55 |
110 |
|
3 |
55 |
51[110] |
50[65] |
61 |
55 |
175 |
|
4 |
65 |
70 |
57[35] |
65 |
57[130] |
165 |
|
Потребности |
120 |
130 |
100 |
90 |
150 |
затраты математический транспортный
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
v1=70 |
v2=61 |
v3=60 |
v4=65 |
v5=60 |
||
u1=0 |
70[120] |
71 |
74 |
75 |
60[20] |
|
u2=-11 |
54 |
50[20] |
65 |
54[90] |
55 |
|
u3=-10 |
55 |
51[110] |
50[65] |
61 |
55 |
|
u4=-3 |
65 |
70 |
57[35] |
65 |
57[130] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
Выбираем максимальную оценку свободной клетки (2;1): 54
Для этого в перспективную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 |
2 |
3 |
4 |
5 |
Запасы |
||
1 |
70[120][-] |
71 |
74 |
75 |
60[20][+] |
140 |
|
2 |
54[+] |
50[20][-] |
65 |
54[90] |
55 |
110 |
|
3 |
55 |
51[110][+] |
50[65][-] |
61 |
55 |
175 |
|
4 |
65 |
70 |
57[35][+] |
65 |
57[130][-] |
165 |
|
Потребности |
120 |
130 |
100 |
90 |
150 |
Цикл приведен в таблице (2,1; 2,2; 3,2; 3,3; 4,3; 4,5; 1,5; 1,1; ).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 20.
Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Хij, стоящих в минусовых клетках.
В результате получим новый опорный план.
1 |
2 |
3 |
4 |
5 |
Запасы |
||
1 |
70[100] |
71 |
74 |
75 |
60[40] |
140 |
|
2 |
54[20] |
50 |
65 |
54[90] |
55 |
110 |
|
3 |
55 |
51[130] |
50[45] |
61 |
55 |
175 |
|
4 |
65 |
70 |
57[55] |
65 |
57[110] |
165 |
|
Потребности |
120 |
130 |
100 |
90 |
150 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
v1=70 |
v2=61 |
v3=60 |
v4=70 |
v5=60 |
||
u1=0 |
70[100] |
71 |
74 |
75 |
60[40] |
|
u2=-16 |
54[20] |
50 |
65 |
54[90] |
55 |
|
u3=-10 |
55 |
51[130] |
50[45] |
61 |
55 |
|
u4=-3 |
65 |
70 |
57[55] |
65 |
57[110] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
Выбираем максимальную оценку свободной клетки (3;1): 55
Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 |
2 |
3 |
4 |
5 |
Запасы |
||
1 |
70[100][-] |
71 |
74 |
75 |
60[40][+] |
140 |
|
2 |
54[20] |
50 |
65 |
54[90] |
55 |
110 |
|
3 |
55[+] |
51[130] |
50[45][-] |
61 |
55 |
175 |
|
4 |
65 |
70 |
57[55][+] |
65 |
57[110][-] |
165 |
|
Потребности |
120 |
130 |
100 |
90 |
150 |
Цикл приведен в таблице (3,1; 3,3; 4,3; 4,5; 1,5; 1,1; ).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 45. Прибавляем 45 к объемам грузов, стоящих в плюсовых клетках и вычитаем 45 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
5 |
Запасы |
||
1 |
70[55] |
71 |
74 |
75 |
60[85] |
140 |
|
2 |
54[20] |
50 |
65 |
54[90] |
55 |
110 |
|
3 |
55[45] |
51[130] |
50 |
61 |
55 |
175 |
|
4 |
65 |
70 |
57[100] |
65 |
57[65] |
165 |
|
Потребности |
120 |
130 |
100 |
90 |
150 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
v1=70 |
v2=66 |
v3=60 |
v4=70 |
v5=60 |
||
u1=0 |
70[55] |
71 |
74 |
75 |
60[85] |
|
u2=-16 |
54[20] |
50 |
65 |
54[90] |
55 |
|
u3=-15 |
55[45] |
51[130] |
50 |
61 |
55 |
|
u4=-3 |
65 |
70 |
57[100] |
65 |
57[65] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij. Выбираем максимальную оценку свободной клетки (4;1): 65.
1 |
2 |
3 |
4 |
5 |
Запасы |
||
1 |
70[55][-] |
71 |
74 |
75 |
60[85][+] |
140 |
|
2 |
54[20] |
50 |
65 |
54[90] |
55 |
110 |
|
3 |
55[45] |
51[130] |
50 |
61 |
55 |
175 |
|
4 |
65[+] |
70 |
57[100] |
65 |
57[65][-] |
165 |
|
Потребности |
120 |
130 |
100 |
90 |
150 |
Цикл приведен в таблице (4,1; 4,5; 1,5; 1,1; ). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 55. Прибавляем 55 к объемам грузов, стоящих в плюсовых клетках и вычитаем 55 из Хij, стоящих в минусовых клетках
1 |
2 |
3 |
4 |
5 |
Запасы |
||
1 |
70 |
71 |
74 |
75 |
60[140] |
140 |
|
2 |
54[20] |
50 |
65 |
54[90] |
55 |
110 |
|
3 |
55[45] |
51[130] |
50 |
61 |
55 |
175 |
|
4 |
65[55] |
70 |
57[100] |
65 |
57[10] |
165 |
|
Потребности |
120 |
130 |
100 |
90 |
150 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
v1=68 |
v2=64 |
v3=60 |
v4=68 |
v5=60 |
||
u1=0 |
70 |
71 |
74 |
75 |
60[140] |
|
u2=-14 |
54[20] |
50 |
65 |
54[90] |
55 |
|
u3=-13 |
55[45] |
51[130] |
50 |
61 |
55 |
|
u4=-3 |
65[55] |
70 |
57[100] |
65 |
57[10] |
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij.
Минимальные затраты составят:
F(x) = 60*140 + 54*20 + 54*90 + 55*45 + 51*130 + 65*55 + 57*100 + 57*10 = 33290
Все вычисления и комментарии к полученным результатам доступны в расширенном режиме. Также приведено решение двойственной транспортной задачи и анализ оптимального плана.
Проверка решения в Excel
Загрузите шаблон для проверки в Excel (ссылка приведена ниже)
Откройте его в MS Excel
Мышкой или с помощью клавиатуры перейдите к ячейке B16
Выполните команду Сервис / Поиск решения
Нажмите <Параметры>. Отметье Линейная модель, Неотрицательные значения
В диалоговом окне укажите:
в поле Равной: минимальному значению
в поле изменяя ячейки: $B$9:$F$12
в поле Ограничения добавьте заданные ограничения
Поле должно иметь следующее содержание:$G$9:$G$12<=$H$9:$H$12
$B$13:$F$13=$B$14:$F$14
Нажмите на кнопку Выполнить
Значения переменных Xi может различаться, но целевая функция F(x) должна иметь такое же значение
Размещено на Allbest.ru
Подобные документы
Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.
контрольная работа [118,5 K], добавлен 11.04.2012Определение оптимального плана перевозок однородного груза из k-пунктов отправления в m-пункты назначения. Описание алгоритма нахождения потока минимальной стоимости. Решение транспортной задачи вручную и в среде MathCad, сравнение полученных результатов.
курсовая работа [773,6 K], добавлен 09.12.2010Особенности решения транспортной задачи распределительным методом и анализ результатов. Построение математической модели, алгоритма. Создание программы для решения транспортной задачи распределительным методом в программной среде Borland Delphi 7.
курсовая работа [1000,7 K], добавлен 23.06.2012Сущность и постановка транспортной задачи для n переменных, их виды, применение и пример решения в MS Excel. Управляющие структуры ветвления Maple языка (if предложение). Решение транспортной задачи в векторных координатах для двух и трёх матриц.
дипломная работа [109,3 K], добавлен 12.01.2011Математическая постановка транспортной задачи открытой модели методом потенциалов при известных показателях запаса груза поставщика и потребности потребителя; ее решение ручным способом и с помощью компьютерной программы, написанной в среде Delphi.
курсовая работа [167,2 K], добавлен 16.01.2011Условия математической транспортной задачи для ее решения методом потенциалов. Опорный план и проверка целевой функции. Окончательный вариант плана поставок товара предоставленный программой "АОС транспортная задача". Стоимость доставки единицы груза.
лабораторная работа [1,4 M], добавлен 15.10.2015Решение в среде Microsoft Excel с помощью программной модели "Поиск решения" транспортной задачи, системы нелинейных уравнений, задачи о назначениях. Составление уравнения регрессии по заданным значениям. Математические и алгоритмические модели.
лабораторная работа [866,6 K], добавлен 23.07.2012Оптимизация затрат на доставку продукции потребителям. Характеристика транспортной задачи, общий вид решения, обобщение; содержательная и математическая постановка задачи, решение с помощью программы MS Excel: листинг программы, анализ результатов.
курсовая работа [514,8 K], добавлен 04.02.2011Построение математической модели. Выбор, обоснование и описание метода решений прямой задачи линейного программирования симплекс-методом, с использованием симплексной таблицы. Составление и решение двойственной задачи. Анализ модели на чувствительность.
курсовая работа [100,0 K], добавлен 31.10.2014Методы решения задач линейного программирования: планирования производства, составления рациона, задачи о раскрое материалов и транспортной. Разработка экономико-математической модели и решение задачи с использованием компьютерного моделирования.
курсовая работа [607,2 K], добавлен 13.03.2015