Решение транспортной задачи
Процесс определения минимальных затрат. Построение математической модели транспортной задачи. Стоимость доставки единицы груза из пункта. Построение опорного плана и его улучшение. Решение двойственной транспортной задачи и анализ оптимального плана.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | контрольная работа |
Язык | русский |
Дата добавления | 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Создание и реализация алгоритма решения транспортной задачи методом наименьших стоимостей. Схема алгоритма основной программы. Основные шаги алгоритма решения транспортной задачи. Инструкция по эксплуатации программы и обзор результатов ее выполнения.
курсовая работа [2,0 M], добавлен 12.02.2013Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Стандартная и каноническая форма записи задачи линейного программирования. Ее запись на листе MS Excel. Математическая модель транспортной задачи, состоящей в определении оптимального плана перевозок некоторого однородного груза, результаты ее решения.
контрольная работа [1,1 M], добавлен 25.01.2016Применение методов линейного программирования для решения оптимизационных задач. Основные понятия линейного программирования, свойства транспортной задачи и теоремы, применяемые для ее решения. Построение первичного опорного плана и системы потенциалов.
курсовая работа [280,8 K], добавлен 17.11.2011Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.
дипломная работа [2,4 M], добавлен 20.11.2010Составление программы для расчета начального базиса сбалансированной транспортной задачи, где суммарные запасы поставщиков равны суммарным запросам потребителей. Алгоритм метода потенциалов. Пример решения транспортной задачи методом наименьшей стоимости.
отчет по практике [991,3 K], добавлен 06.12.2013Краткий обзор решения транспортных задач. Экономическая интерпретация поставленной задачи. Разработка и описание алгоритма решения задачи. Построение математической модели. Решение задачи вручную и с помощью ЭВМ. Анализ модели на чувствительность.
курсовая работа [844,3 K], добавлен 16.06.2011Сущность и назначение основных алгоритмов оптимизации. Линейное программирование. Постановка и аналитический метод решения параметрической транспортной задачи, математическая модель. Метод решения задачи об оптимальных перевозках средствами MS Excel.
курсовая работа [465,6 K], добавлен 24.04.2009Решение задачи линейного программирования табличным симплексным методом и транспортной задачи венгерским методом. Построение имитационной модели гибкого производственного модуля. Алгоритмы автоматизированного проектирования средств вычислительной техники.
контрольная работа [117,9 K], добавлен 08.12.2010Анализ решения задачи линейного программирования. Симплексный метод с использованием симплекс-таблиц. Моделирование и решение задач ЛП на ЭВМ. Экономическая интерпретация оптимального решения задачи. Математическая формулировка транспортной задачи.
контрольная работа [196,1 K], добавлен 15.01.2009