Главная Коллекция "Otherreferats" Программирование, компьютеры и кибернетика Решение транспортной задачи

Решение транспортной задачи

Процесс определения минимальных затрат. Построение математической модели транспортной задачи. Стоимость доставки единицы груза из пункта. Построение опорного плана и его улучшение. Решение двойственной транспортной задачи и анализ оптимального плана.

Рубрика	Программирование, компьютеры и кибернетика
Вид	контрольная работа
Язык	русский
Дата добавления	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

	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

	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

затраты математический транспортный

	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

	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

	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

	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
Решение транспортной задачи в векторной постановке в среде Maple
Сущность и постановка транспортной задачи для 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

Другие документы, подобные "Решение транспортной задачи"

весь список подобных работ

скачать работу можно здесь

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.