Транспортная задача

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

СОДЕРЖАНИЕ

Введение

Теоретическая часть

Транспортная задача

Постановка задачи

История поиска методов решения

Методы решения

Итерационное улучшение плана перевозок

Описание метода Северо-Западного угла

Метод наименьшего элемента

Решение с помощью теории графов

Практическая часть

Определение исходного опорного плана

Этап I. Поиск первого опорного плана

Этап II. Улучшение опорного плана

Проверка опорного плана на оптимальность

Переход от неоптимального опорного плана к лучшему

Решение транспортной задачи встроенными функциями Microsoft office - Excel

Код программы

ВВЕДЕНИЕ

Под названием "транспортная задача" объединяется широкий круг задач с единой математической моделью. Классическая транспортная задача - задача о наиболее экономном плане перевозок однородного продукта или взаимозаменяемых продуктов из пунктов производства в пункты потребления, встречается чаще всего в практических приложениях линейного программирования. Линейное программирование является одним из разделов математического программирования - области математики, разрабатывающей теорию и численные методы решения многомерных экстремальных задач с ограничениями.

Огромное количество возможных вариантов перевозок затрудняет получение достаточно экономного плана эмпирическим или экспертным путем. Применение математических методов и вычислительных в планировании перевозок дает большой экономический эффект. Транспортные задачи могут быть решены симплексным методом, однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его получить оптимальное решение.

В зависимости от способа представления условий транспортной задачи она может быть представлена в сетевой (схематичной) или матричной (табличной) форме. Транспортная задача может также решаться с ограничениями и без ограничений.

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Основное понятие

Транспортная задача (задача Монжа -- Канторовича) -- математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение.

Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача является по теории сложности вычислений NP-сложной или входит в класс сложности NP. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной.

Постановка задачи

Транспортная задача (классическая) -- задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).

История поиска методов решения

Проблема была впервые сформулирована французским математиком Гаспаром Монжем в 1781 году. Основное продвижение было сделано на полях во время Великой Отечественной войны советским математиком и экономистом Леонидом Канторовичем. Поэтому иногда эта проблема называется транспортной задачей Монжа -- Канторовича.

Методы решения

Классическую транспортную задачу можно решить симплекс-методом, но в силу ряда особенностей её можно решить проще (для задач малой размерности).

Условия задачи располагают в таблице, вписывая в ячейки количество перевозимого груза из A_i в B_j груза X_ij ? 0, а в маленькие клетки -- соответствующие тарифы C_ij.

Итерационное улучшение плана перевозок. Нахождение опорного плана

Требуется определить опорный план и путём последовательных операций найти оптимальное решение. Опорный план можно найти следующими методами: «северо-западного угла», «наименьшего элемента», двойного предпочтения и аппроксимации Фогеля.

Метод северо-западного угла (диагональный)

Описание метода северо-западного угла:

Метод состоит в следующем. Просматривается матрица тарифов перевозок C,начиная с левого верхнего угла (клетки). В эту клетку записывается величина D=MIN(A,B). Она вычитается из запасов и потребностей соответствующего склада и магазина. Обнулившаяся строка или столбец исключаются из рассмотрения, затем процесс опять повторяется для левой верхней клетки оставшейся матрицы и так до тех пор, пока весь запас товаров не будет исчерпан.

Краткое описание сущности задачи:

В экономике помимо соотношений затрат, выпуска, спроса, предложения и т.п., часто возникает необходимость выбора одного из возможных вариантов функционирования экономической системы. Экономически оправдано в таких условиях, поставить вопрос о выборе наилучшего варианта, который задается в виде критерия - цели. В количественном выражении критерий представляет собой функциональную зависимость от переменных показателей, в дальнейшем будем ее называть целевой функцией. Наилучший вариант в таком случае соответствует наибольшему (экстремальному, оптимальному или наименьшему) значению функции.

В экономических задачах такого рода, в основном имеется ограниченная область переменных параметров и, следовательно, оптимальное значение целевой функции нужно найти на ограниченном множестве. Область исследования, заключающаяся в нахождении алгоритмов решения подобных задач, образует направление, которое называется математическим программированием.

Другие варианты решения задачи

Метод наименьшего элемента

Одним из способов решения задачи является метод минимального (наименьшего) элемента. Его суть заключается в сведении к минимуму побочных перераспределений товаров между потребителями.

Алгоритм:

Из таблицы стоимостей выбирают наименьшую стоимость и в клетку, которая ей соответствует, вписывают большее из чисел.

Проверяются строки поставщиков на наличии строки с израсходованными запасами и столбцы потребителей на наличие столбца, потребности которого полностью удовлетворены. Такие столбцы и строки далее не рассматриваются.

Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п. 1, в противном случае задача решена.

Итерации

После нахождения опорного плана перевозок, нужно применить один из алгоритмов его улучшения, приближения к оптимальному.

· Метод падающего камня (нем.)

· Метод потенциалов (нем.).

Решение с помощью теории графов

Рассматривается двудольный граф, в котором пункты производства находятся в верхней доле, а пункты потребления -- в нижней. Пункты производства и потребления попарно соединяются рёбрами бесконечной пропускной способности и цены за единицу потока C_ij.

К верхней доле искусственно присоединяется исток. Пропускная способность рёбер из истока в каждый пункт производства равна запасу продукта в этом пункте. Цена за единицу потока у этих рёбер равна 0.

Аналогично к нижней доле присоединяется сток. Пропускная способность рёбер из каждого пункта потребления в сток равна потребности в продукте в этом пункте. Цена за единицу потока у этих рёбер тоже равна 0.

Дальше решается задача нахождения максимального потока минимальной стоимости (mincost maxflow). Её решение аналогично нахождению максимального потока в алгоритме Форда -- Фалкерсона. Только вместо кратчайшего дополняющего потока ищется самый дешёвый. Соответственно, в этой подзадаче используется не поиск в ширину, а алгоритм Беллмана -- Форда. При возврате потока стоимость считается отрицательной.

Алгоритм «mincost maxflow» можно запускать и сразу -- без нахождения опорного плана. Но в этом случае процесс решения будет несколько более долгим. Выполнение алгоритма «mincost maxflow» происходит не более чем за O(u²e²) операций. ( e -- количество рёбер, u -- количество вершин.) При случайно подобранных данных обычно требуется гораздо меньше -- порядка O(ue) операций.

При решении несбалансированной транспортной задачи применяют приём, позволяющий сделать ее сбалансированной. Для этого вводят фиктивные пункты назначения или отправления. Выполнение баланса транспортной задачи необходимо для того, чтобы иметь возможность применить алгоритм решения, построенный на использовании транспортных таблиц.

ПРАКТИЧЕСКАЯ ЧАСТЬ

Транспортная задача

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

Распределительный метод является одним из вариантов базового симплексного метода. Поэтому идея распределительного метода (как и симплексного) содержит такие же три существенных момента.

Прежде всего, отыскивается какое-то решение задачи -- исходный опорный план. Затем посредством специальных показателей опорный план проверяется на оптимальность. Если план оказывается не оптимальным, переходят к другому плану. При этом второй и последующие планы должны быть лучше предыдущего. Так за несколько последовательных переходов от не оптимального плана приходят к оптимальному.

	B1	B2	B3	B4	B5	Запасы
A1	5	8	15	20	9	240
A2	8	7	6	12	14	160
A3	16	11	19	10	5	200
Потребности	180	40	160	120	100	600

Проверим необходимое и достаточное условие разрешимости задачи.

? a = 240 + 160 + 200 = 600

? b = 180 + 40 + 160 + 120 + 100 = 600

Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой. Занесем исходные данные в распределительную таблицу.

	B1	B2	B3	B4	B5	Запасы
A1	5	8	15	20	9	240
A2	8	7	6	12	14	160
A3	16	11	19	10	5	200
Потребности	180	40	160	120	100	600

Первая итерация заключается в определении исходного опорного плана и проверке его на оптимальность.

Определение исходного опорного плана. Первый опорный план может быть найден посредством различных способов: по правилу северо-западного угла, приоритету ближайших пунктов, способу минимального элемента С=(cij), способу Фогеля и по способу Лебедева-Тихомирова.

Этап I. Поиск первого опорного плана

Используя метод северо-западного угла, построим первый опорный план транспортной задачи.

План начинается заполняться с верхнего левого угла.

Искомый элемент равен 5

Для этого элемента запасы равны 240, потребности 180. Поскольку минимальным является 180, то вычитаем его.

X₁₁ = min(240,180) = 180.

5	8	15	20	9	240 - 180 = 60
x	7	6	12	14	160
x	11	19	10	5	200
180 - 180 = 0	40	160	120	100	0

Искомый элемент равен 8

Для этого элемента запасы равны 60, потребности 40. Поскольку минимальным является 40, то вычитаем его.

X₁₂ = min(60,40) = 40.

5	8	15	20	9	60 - 40 = 20
x	x	6	12	14	160
x	x	19	10	5	200
0	40 - 40 = 0	160	120	100	0

Искомый элемент равен 15

Для этого элемента запасы равны 20, потребности 160. Поскольку минимальным является 20, то вычитаем его.

X₁₃ = min(20,160) = 20.

5	8	15	x	x	20 - 20 = 0
x	x	6	12	14	160
x	x	19	10	5	200
0	0	160 - 20 = 140	120	100	0

Искомый элемент равен 6

Для этого элемента запасы равны 160, потребности 140. Поскольку минимальным является 140, то вычитаем его.

X₂₃ = min(160,140) = 140.

5	8	15	x	x	0
x	x	6	12	14	160 - 140 = 20
x	x	x	10	5	200
0	0	140 - 140 = 0	120	100	0

Искомый элемент равен 12

Для этого элемента запасы равны 20, потребности 120. Поскольку минимальным является 20, то вычитаем его.

X₂₄ = min(20,120) = 20.

5	8	15	x	x	0
x	x	6	12	x	20 - 20 = 0
x	x	x	10	5	200
0	0	0	120 - 20 = 100	100	0

Искомый элемент равен 10

Для этого элемента запасы равны 200, потребности 100. Поскольку минимальным является 100, то вычитаем его.

X₃₄ = min(200,100) = 100.

5	8	15	x	x	0
x	x	6	12	x	0
x	x	x	10	5	200 - 100 = 100
0	0	0	100 - 100 = 0	100	0

Искомый элемент равен 5

Для этого элемента запасы равны 100, потребности 100. Поскольку минимальным является 100, то вычитаем его.

X₃₅ = min(100,100) = 100.

5	8	15	x	x	0
x	x	6	12	x	0
x	x	x	10	5	100 - 100 = 0
0	0	0	0	100 - 100 = 0	0

	B1	B2	B3	B4	B5	Запасы
A1	5[180]	8[40]	15[20]	20	9	240
A2	8	7	6[140]	12[20]	14	160
A3	16	11	19	10[100]	5[100]	200
Потребности	180	40	160	120	100

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.

2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

5*180 + 8*40 + 15*20 + 6*140 + 12*20 + 10*100 + 5*100 = 4100

Этап II. Улучшение опорного плана

Проверка опорного плана на оптимальность. Чтобы установить является ли опорный план оптимальным, надо проверить, как повлияет на величину целевой функции любое возможное перераспределение поставок.

План распределения поставок будет оптимальным лишь в том случае, когда целевая функция имеет минимальное значение, т.е. когда дальнейшее уменьшение затрат на поставку будет невозможно.

Проверим возможность уменьшения суммарных затрат на поставку продукции. С этой целью для каждой свободной от поставки клетки определяется величина Д_ij, характеризующая изменение суммарных затрат на поставку (в расчете на единицу перераспределяемой продукции), при условии включения в план единичной поставки х_ij=1 от поставщика А_i к потребителю В_j.

При этом должно быть произведено такое изменение остальных поставок, чтобы получившаяся совокупность поставок не нарушала баланса спроса и поставок транспортной задачи.

Величина Д_ij называется оценкой свободной клетки (или характеристика).

В исходном решении задачи имеются клетки свободные от поставок.

Необходимо вычислить значение оценок Д_ij для этих свободных от поставок клеток. С этой целью для каждой свободной клетки составляется означенный цикл перерасчета (или замкнутая цепь, круг, кольцо, контур и т.д.).

Под циклом пересчета (цепью) понимается замкнутая ломаная линия. Вершинами цикла (цепи) являются клетки таблицы, проще - вершины лежат в клетках таблицы.

Причем одна из вершин находится в свободной от поставки клетке, в той, для которой определяется оценка Д_ij. Все другие вершины находятся в базисных клетках, т.е. клетках, занятых поставками.

Вершины, в которых поставки при перераспределении увеличиваются, отмечаются плюсом и называются положительными вершинами и, наоборот, вершины, в которых поставки при перераспределении уменьшаются отмечаются минусом и называются отрицательными вершинами.

В цикле знаки по вершинам расставляют начиная с вершины, лежащей в свободной клетке, для которой определяется Д_ij. В нее записывают знак плюс, затем знаки по вершинам чередуются: минус, плюс,минус, плюс и т. Д., независимо от того, расставляют ли их по часовой стрелке или в обратном направлении. Таким образом, в цикле всегда насчитывается одинаковое число положительных и отрицательных вершин.

Следующий этап решения транспортной задачи заключается в улучшении опорного плана.

Если при каком-то опорном плане оказывается несколько свободных клеток с отрицательными оценками Д_ij, то за один переход к лучшему плану можно занять поставкой только одну клетку - ту, которая обеспечивает наибольшее снижение целевой функции.

Шаг 1. Определяем оценку для каждой свободной клетки.

(1;4): В свободную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	B5	Запасы
A1	5[180]	8[40]	15[20][-]	20[+]	9	240
A2	8	7	6[140][+]	12[20][-]	14	160
A3	16	11	19	10[100]	5[100]	200
Потребности	180	40	160	120	100

Цикл приведен в таблице (1,4; 1,3; 2,3; 2,4; ).

Оценка свободной клетки равна Д₁₄ = (20) - (15) + (6) - (12) = -1.

(1;5): В свободную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	B5	Запасы
A1	5[180]	8[40]	15[20][-]	20	9[+]	240
A2	8	7	6[140][+]	12[20][-]	14	160
A3	16	11	19	10[100][+]	5[100][-]	200
Потребности	180	40	160	120	100

Цикл приведен в таблице (1,5; 1,3; 2,3; 2,4; 3,4; 3,5; ).

Оценка свободной клетки равна Д₁₅ = (9) - (15) + (6) - (12) + (10) - (5) = -7.

(2;1): В свободную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	B5	Запасы
A1	5[180][-]	8[40]	15[20][+]	20	9	240
A2	8[+]	7	6[140][-]	12[20]	14	160
A3	16	11	19	10[100]	5[100]	200
Потребности	180	40	160	120	100

Цикл приведен в таблице (2,1; 2,3; 1,3; 1,1; ).

Оценка свободной клетки равна Д₂₁ = (8) - (6) + (15) - (5) = 12.

(2;2): В свободную клетку (2;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	B5	Запасы
A1	5[180]	8[40][-]	15[20][+]	20	9	240
A2	8	7[+]	6[140][-]	12[20]	14	160
A3	16	11	19	10[100]	5[100]	200
Потребности	180	40	160	120	100

Цикл приведен в таблице (2,2; 2,3; 1,3; 1,2; ).

Оценка свободной клетки равна Д₂₂ = (7) - (6) + (15) - (8) = 8.

(2;5): В свободную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	B5	Запасы
A1	5[180]	8[40]	15[20]	20	9	240
A2	8	7	6[140]	12[20][-]	14[+]	160
A3	16	11	19	10[100][+]	5[100][-]	200
Потребности	180	40	160	120	100

Цикл приведен в таблице (2,5; 2,4; 3,4; 3,5; ).

Оценка свободной клетки равна Д₂₅ = (14) - (12) + (10) - (5) = 7.

(3;1): В свободную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	B5	Запасы
A1	5[180][-]	8[40]	15[20][+]	20	9	240
A2	8	7	6[140][-]	12[20][+]	14	160
A3	16[+]	11	19	10[100][-]	5[100]	200
Потребности	180	40	160	120	100

Цикл приведен в таблице (3,1; 3,4; 2,4; 2,3; 1,3; 1,1; ).

Оценка свободной клетки равна Д₃₁ = (16) - (10) + (12) - (6) + (15) - (5) = 22.

(3;2): В свободную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	B5	Запасы
A1	5[180]	8[40][-]	15[20][+]	20	9	240
A2	8	7	6[140][-]	12[20][+]	14	160
A3	16	11[+]	19	10[100][-]	5[100]	200
Потребности	180	40	160	120	100

Цикл приведен в таблице (3,2; 3,4; 2,4; 2,3; 1,3; 1,2; ).

Оценка свободной клетки равна Д₃₂ = (11) - (10) + (12) - (6) + (15) - (8) = 14.

(3;3): В свободную клетку (3;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	B5	Запасы
A1	5[180]	8[40]	15[20]	20	9	240
A2	8	7	6[140][-]	12[20][+]	14	160
A3	16	11	19[+]	10[100][-]	5[100]	200
Потребности	180	40	160	120	100

Цикл приведен в таблице (3,3; 3,4; 2,4; 2,3; ).

Оценка свободной клетки равна Д₃₃ = (19) - (10) + (12) - (6) = 15.

Опорный план является неоптимальным, поскольку имеются отрицательны оценки клеток (1,5;) равные: (-7).

Переход от неоптимального опорного плана к лучшему.

Поскольку в исходном опорном плане рассматриваемой задачи свободная клетка (1;5) имеет отрицательную оценку, то для получения плана, обеспечивающего меньшее значение целевой функции, эту клетку следует занять возможно большей поставкой, не нарушающей при этом условий допустимости плана.

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 4) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	B1	B2	B3	B4	B5	Запасы
A1	5[180]	8[40]	15[0]	20	9[20]	240
A2	8	7	6[160]	12	14	160
A3	16	11	19	10[120]	5[80]	200
Потребности	180	40	160	120	100

5*180 + 8*40 + 9*20 + 6*160 + 10*120 + 5*80 = 3960

Шаг 2. Определяем оценку для каждой свободной клетки.

(1;4): В свободную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	B5	Запасы
A1	5[180]	8[40]	15[0]	20[+]	9[20][-]	240
A2	8	7	6[160]	12	14	160
A3	16	11	19	10[120][-]	5[80][+]	200
Потребности	180	40	160	120	100

Цикл приведен в таблице (1,4; 1,5; 3,5; 3,4; ).

Оценка свободной клетки равна Д₁₄ = (20) - (9) + (5) - (10) = 6.

(2;1): В свободную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	B5	Запасы
A1	5[180][-]	8[40]	15[0][+]	20	9[20]	240
A2	8[+]	7	6[160][-]	12	14	160
A3	16	11	19	10[120]	5[80]	200
Потребности	180	40	160	120	100

Цикл приведен в таблице (2,1; 2,3; 1,3; 1,1; ).

Оценка свободной клетки равна Д₂₁ = (8) - (6) + (15) - (5) = 12.

(2;2): В свободную клетку (2;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	B5	Запасы
A1	5[180]	8[40][-]	15[0][+]	20	9[20]	240
A2	8	7[+]	6[160][-]	12	14	160
A3	16	11	19	10[120]	5[80]	200
Потребности	180	40	160	120	100

Цикл приведен в таблице (2,2; 2,3; 1,3; 1,2; ).

Оценка свободной клетки равна Д₂₂ = (7) - (6) + (15) - (8) = 8.

(2;4): В свободную клетку (2;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	B5	Запасы
A1	5[180]	8[40]	15[0][+]	20	9[20][-]	240
A2	8	7	6[160][-]	12[+]	14	160
A3	16	11	19	10[120][-]	5[80][+]	200
Потребности	180	40	160	120	100

Цикл приведен в таблице (2,4; 2,3; 1,3; 1,5; 3,5; 3,4; ).

Оценка свободной клетки равна Д₂₄ = (12) - (6) + (15) - (9) + (5) - (10) = 7.

(2;5): В свободную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	B5	Запасы
A1	5[180]	8[40]	15[0][+]	20	9[20][-]	240
A2	8	7	6[160][-]	12	14[+]	160
A3	16	11	19	10[120]	5[80]	200
Потребности	180	40	160	120	100

Цикл приведен в таблице (2,5; 2,3; 1,3; 1,5; ).

Оценка свободной клетки равна Д₂₅ = (14) - (6) + (15) - (9) = 14.

(3;1): В свободную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	B5	Запасы
A1	5[180][-]	8[40]	15[0]	20	9[20][+]	240
A2	8	7	6[160]	12	14	160
A3	16[+]	11	19	10[120]	5[80][-]	200
Потребности	180	40	160	120	100

Цикл приведен в таблице (3,1; 3,5; 1,5; 1,1; ).

Оценка свободной клетки равна Д₃₁ = (16) - (5) + (9) - (5) = 15.

(3;2): В свободную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	B5	Запасы
A1	5[180]	8[40][-]	15[0]	20	9[20][+]	240
A2	8	7	6[160]	12	14	160
A3	16	11[+]	19	10[120]	5[80][-]	200
Потребности	180	40	160	120	100

Цикл приведен в таблице (3,2; 3,5; 1,5; 1,2; ).

Оценка свободной клетки равна Д₃₂ = (11) - (5) + (9) - (8) = 7.

(3;3): В свободную клетку (3;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	B5	Запасы
A1	5[180]	8[40]	15[0][-]	20	9[20][+]	240
A2	8	7	6[160]	12	14	160
A3	16	11	19[+]	10[120]	5[80][-]	200
Потребности	180	40	160	120	100

Цикл приведен в таблице (3,3; 3,5; 1,5; 1,3; ).

Оценка свободной клетки равна Д₃₃ = (19) - (5) + (9) - (15) = 8.

Из приведенного расчета видно, что ни одна свободная клетка не имеет отрицательной оценки, следовательно, дальнейшее снижение целевой функции Fx невозможно, поскольку она достигла минимального значения.

Таким образом, последний опорный план является оптимальным.

Минимальные затраты составят:

5*180 + 8*40 + 9*20 + 6*160 + 10*120 + 5*80 = 3960

Если в оптимальном решении задачи имеется несколько оценок равных нулю, то это является свидетельством того, что среди бесчисленного множества решений этой задачи существуют еще решения, являющиеся также оптимальными, поскольку значение целевой функции остается одинаковым -- минимальным. Их принято называть альтернативными.

Примечание. Основной алгоритм распределительного метода является не лучшим методом решения транспортных задач, так как на каждой итерации для проверки опорного плана на оптимальность приходилось строить [mп--(m+n--1)] циклов пересчета, что при больших размерах матрицы оказывается очень громоздким и трудоемким делом. Так, для расчетов по матрице 10х10 на каждой итерации надо строить 81 цикл, а по матрице 20x20 -- 361 цикл.

Решение транспортной задачи встроенными функциями Excel

Решение с помощью EXCEL начинается с создания чистого листа и ввода условий задачи. (рис.1)

Рис. 1

Далее выбирается ячейка В15 для последующего занесения в неё суммы стоимости перевозок.

Чтобы в ячейке появилась сумма, нужно нажать на кнопку мастер функций, далее в окне категория выбрать математические, в окне функции выбрать СУММПРОИЗВ, нажать ОК. (рис.2)

Рис. 2

Рис. 3

В появившемся окне аргументы функции в массив 1 необходимо ввести B3:F5, в массив 2 ввести B10:F12, нажать ОК. (рис.3)

Далее необходимо выделить ячейки В3-В5, нажать на кнопку ?, и в ячейке В6 появится сумма ячеек В3-В5 - 3. Проделать эти действия для ячеек C3-C5, D3-D5, E3-E5, F3-F5. (рис.4)

Рис.4

Далее выбрать ячейку А3, вызвать мастер функций, выбрать функцию СУММ, нажать ОК, в появившемся окне аргументов выбрать ячейки

В3-F3, ОК, в ячейке А3 появилось значение 5. Скопируем значение ячейки А3 в ячейки А4 и А5, сумма также равна 5.

Далее следует выбрать команду поиск решения из меню сервис. В появившемся окне заполнить поле «установить целевую ячейку» - $B$15, ввести направление целевой функции - «минимальному значению», в поле «изменяя ячейки» ввести адреса «$B$3:$F$5. (рис.5)

Рис. 5

Далее следует ввести ограничения.

В окне поиск решения нужно нажать кнопку «добавить», появилось окно добавления ограничений, в поле «ссылка на ячейку» ввести $A$3:$A$5, знак ограничения «=» в следующее окно ввести адрес $A$10:$A$12, ОК. (рис.6)

Рис. 6

Ввод параметров для решения ЗЛП

В окне поиск решения нажать кнопку «параметры», установить флажки возле параметров «линейная модель» и «неотрицательные значения», ОК (Рис.7)

Рис. 7

Далее в окне поиск решений нажать кнопку выполнить, в ячейках А3-F6, B15 появится решение задачи.

Можно также привести таблицу к более удобному виду, переместив ячейки нужным образом, все функции автоматически поменяют свои значения на нужные с учётом своего нового положения. (Рис.8)

Рис. 8

Программный код

Private Sub about_autor_Click()

Load about_me

about_me.Show

End Sub

Private Sub about_programm_Click()

Load programm

programm.Show

End Sub

Private Sub Clean_Click()

Call Clear

End Sub

Private Sub clean_it_Click()

Call Clear

End Sub

Private Sub exit_Click()

End

End Sub

Private Sub Fill_Click()

Text19.Text = 180

Text20.Text = 40

Text21.Text = 160

Text22.Text = 120

Text23.Text = 100

Text24.Text = " "

Text16.Text = 240

Text17.Text = 160

Text18.Text = 200

Call Error_clean

End Sub

Private Sub fill_it_Click()

Call Fill_Click

End Sub

Private Sub Form_Load()

Call Error_clean

End Sub

Private Sub help_Click()

Load hlp

hlp.Show

End Sub

Private Sub Solve_Click()

Dim Mtr(4, 6) As Double 'Матрица,в которой производятся все действия

Dim S1 As Double 'Cумма товара всех заказов

Dim S2 As Double 'Сумма товара всех складов

Dim ost1 As Double 'Остаток 1

Dim ost2 As Double 'Остаток 2

Dim ost3 As Double 'Остаток 3

Dim ost4 As Double 'Остаток 4

Dim ost5 As Double 'Остаток 5

'Очищаем консоль ошибок

Call Error_clean

'Очищаем ячейки

Text1.Text = ""

Text2.Text = ""

Text3.Text = ""

Text4.Text = ""

Text5.Text = ""

Text6.Text = ""

Text7.Text = ""

Text8.Text = ""

Text9.Text = ""

Text10.Text = ""

Text11.Text = ""

Text12.Text = ""

Text13.Text = ""

Text14.Text = ""

Text15.Text = ""

Text24.Text = ""

'Проверяем вводимые поля на правильность вводимого типа данных

If Not IsNumeric(Text16.Text) Then

Text25.Text = "Вводить буквы - Нельзя! Введите цифру!"

Text16.BackColor = &H8080FF

' Msgbox "Для корректной работы программы введите в окрашенную бледно-красным цветом ячейку неотрицательное число"

'

Else

Mtr(1, 6) = Val(Text16.Text)

If Not IsNumeric(Text17.Text) Then

Text25.Text = "Вводить буквы - Нельзя! Введите цифру!"

Text17.BackColor = &H8080FF

MsgBox "Для корректной работы программы введите в окрашенную бледно-красным цветом ячейку неотрицательное число"

Else

Mtr(2, 6) = Val(Text17.Text)

If Not IsNumeric(Text18.Text) Then

Text25.Text = "Вводить буквы - Нельзя! Введите цифру!"

Text18.BackColor = &H8080FF

MsgBox "Для корректной работы программы введите в окрашенную бледно-красным цветом ячейку неотрицательное число"

Else

Mtr(3, 6) = Val(Text18.Text)

If Not IsNumeric(Text19.Text) Then

Text25.Text = "Вводить буквы - Нельзя! Введите цифру!"

Text19.BackColor = &H8080FF

MsgBox "Для корректной работы программы введите в окрашенную бледно-красным цветом ячейку неотрицательное число"

Else

Mtr(4, 1) = Val(Text19.Text)

If Not IsNumeric(Text20.Text) Then

Text25.Text = "Вводить буквы - Нельзя! Введите цифру!"

Text20.BackColor = &H8080FF

MsgBox "Для корректной работы программы введите в окрашенную бледно-красным цветом ячейку неотрицательное число"

Else

Mtr(4, 2) = Val(Text20.Text)

If Not IsNumeric(Text21.Text) Then

Text25.Text = "Вводить буквы - Нельзя! Введите цифру!"

Text21.BackColor = &H8080FF

MsgBox "Для корректной работы программы введите в окрашенную бледно-красным цветом ячейку неотрицательное число"

Else

Mtr(4, 3) = Val(Text21.Text)

If Not IsNumeric(Text22.Text) Then

Text25.Text = "Вводить буквы - Нельзя! Введите цифру!"

Text22.BackColor = &H8080FF

MsgBox "Для корректной работы программы введите в окрашенную бледно-красным цветом ячейку неотрицательное число"

Else

Mtr(4, 4) = Val(Text22.Text)

If Not IsNumeric(Text23.Text) Then

Text25.Text = "Вводить буквы - Нельзя! Введите цифру!"

Text23.BackColor = &H8080FF

MsgBox "Для корректной работы программы введите в окрашенную бледно-красным цветом ячейку неотрицательное число"

Else

Mtr(4, 5) = Val(Text23.Text)

'Подсчитываем сумму товара всех заказов

S1 = Mtr(4, 1) + Mtr(4, 2) + Mtr(4, 3) + Mtr(4, 4) + Mtr(4, 5)

'Подсчитываем сумму товара всех складов

S2 = Mtr(1, 6) + Mtr(2, 6) + Mtr(3, 6)

'Проверяем,равна ли сумма товаров в заказах ,суммме товара на складе

If S1 <> S2 Then

Text25.Text = "Сумма заявок не равна сумме запасов. Проверьте введенные данные!"

Else

'Заносим сумму в ячейку

Text24.Text = S1

If Mtr(1, 6) >= Mtr(4, 1) Then

Mtr(1, 1) = Mtr(4, 1)

ost1 = Mtr(1, 6) - Mtr(4, 1)

'Движемся вправо

If ost1 >= Mtr(4, 2) Then

Mtr(1, 2) = Mtr(4, 2)

ost2 = ost1 - Mtr(4, 2)

'Движемся вправо

If ost2 >= Mtr(4, 3) Then

Mtr(1, 3) = Mtr(4, 3)

ost3 = ost2 - Mtr(4, 3)

'Движемся вправо

If ost3 >= Mtr(4, 4) Then

Mtr(1, 4) = Mtr(4, 4)

ost4 = ost3 - Mtr(4, 4)

Mtr(1, 5) = ost4

Mtr(2, 5) = Mtr(2, 6)

Mtr(3, 5) = Mtr(3, 6)

Else

Mtr(1, 4) = ost3

ost4 = Mtr(4, 4) - ost3

'Движемся вниз

If Mtr(2, 6) >= ost4 Then

Mtr(2, 4) = ost4

ost5 = Mtr(2, 6) - ost4

Mtr(2, 5) = ost5

Mtr(3, 5) = Mtr(3, 6)

Else

Mtr(2, 4) = Mtr(2, 6)

'Движемся вниз

Mtr(3, 4) = Mtr(4, 4) - Mtr(1, 4) - Mtr(2, 4)

Mtr(3, 5) = Mtr(4, 5)

End If

End If

Else

'Движемся вниз

Mtr(1, 3) = ost2

ost3 = Mtr(4, 3) - ost2

'Движемся вправо

If Mtr(2, 6) >= ost3 Then

Mtr(2, 3) = ost3

ost4 = Mtr(2, 6) - ost3

'Движемся вправо

If ost4 >= Mtr(4, 4) Then

Mtr(2, 4) = Mtr(4, 4)

'Движемся вправо

Mtr(2, 5) = Mtr(2, 6) - ost3 - Mtr(2, 4)

Mtr(3, 5) = Mtr(3, 6)

Else

Mtr(2, 4) = ost4

'Движемся вниз

Mtr(3, 4) = Mtr(4, 4) - ost4

Mtr(3, 5) = Mtr(4, 5)

End If

Else

Mtr(2, 3) = Mtr(2, 6)

'Движемся вниз

ost4 = ost3 - Mtr(2, 6)

Mtr(3, 3) = ost4

Mtr(3, 4) = Mtr(4, 4)

Mtr(3, 5) = Mtr(4, 5)

End If

End If

Else

Mtr(1, 2) = ost1

ost2 = Mtr(4, 2) - ost1

'Движемся вниз

If Mtr(2, 6) >= ost2 Then

Mtr(2, 2) = ost2

ost3 = Mtr(2, 6) - ost2

'Движемся вправо

If ost3 >= Mtr(4, 3) Then

Mtr(2, 3) = Mtr(4, 3)

ost4 = ost3 - Mtr(4, 3)

'Движемся вправо

If ost4 >= Mtr(4, 4) Then

Mtr(2, 4) = Mtr(4, 4)

ost5 = ost4 - Mtr(4, 4)

'Движемся вправо

Mtr(2, 5) = ost5

Mtr(3, 5) = Mtr(3, 6)

Else

'Движемся вниз

Mtr(2, 4) = ost4

Mtr(3, 4) = Mtr(4, 4) - ost4

Mtr(3, 5) = Mtr(4, 5)

End If

Else

Mtr(2, 3) = ost3

'Движемся вниз

ost4 = Mtr(4, 3) - Mtr(2, 3)

Mtr(3, 3) = ost4

Mtr(3, 4) = Mtr(4, 4)

Mtr(3, 5) = Mtr(4, 5)

End If

Else

Mtr(2, 2) = Mtr(2, 6)

Mtr(3, 2) = Mtr(4, 2) - ost1 - Mtr(2, 6)

Mtr(3, 3) = Mtr(4, 3)

Mtr(3, 4) = Mtr(4, 4)

Mtr(3, 5) = Mtr(4, 5)

End If

End If

Else

'Движемся вниз

Mtr(1, 1) = Mtr(1, 6)

ost1 = Mtr(4, 1) - Mtr(1, 6)

If Mtr(2, 6) >= ost1 Then

Mtr(2, 1) = ost1

ost2 = Mtr(2, 6) - ost1

'Движемся вправо

If ost2 >= Mtr(4, 2) Then

Mtr(2, 2) = Mtr(4, 2)

ost3 = ost2 - Mtr(4, 2)

'Движемся вправо

If ost3 >= Mtr(4, 3) Then

Mtr(2, 3) = Mtr(4, 3)

ost4 = ost3 - Mtr(4, 3)

'Движемся вправо

If ost4 >= Mtr(4, 4) Then

Mtr(2, 4) = Mtr(4, 4)

ost5 = ost4 - Mtr(2, 4)

'Движемся вправо

Mtr(2, 5) = ost5

Mtr(3, 5) = Mtr(3, 6)

Else

Mtr(2, 4) = ost4

Mtr(3, 4) = Mtr(4, 4) - ost4

Mtr(3, 5) = Mtr(4, 5)

End If

Else

Mtr(2, 3) = ost3

Mtr(3, 3) = Mtr(4, 3) - ost3

Mtr(3, 4) = Mtr(4, 4)

Mtr(3, 5) = Mtr(4, 5)

End If

Else

'Движемся вниз

Mtr(2, 2) = ost2

ost3 = Mtr(4, 2) - Mtr(2, 2)

Mtr(3, 2) = ost3

Mtr(3, 3) = Mtr(4, 3)

Mtr(3, 4) = Mtr(4, 4)

Mtr(5, 3) = Mtr(4, 5)

End If

Else

'Движемся вниз

Mtr(2, 1) = Mtr(2, 5)

ost2 = ost1 - Mtr(2, 6)

Mtr(3, 1) = ost2

Mtr(3, 2) = Mtr(4, 2)

Mtr(3, 3) = Mtr(4, 3)

Mtr(3, 4) = Mtr(4, 4)

Mtr(3, 5) = Mtr(4, 5)

End If

End If

End If

'Заканчиваем проверку на верные ввод.поля

End If

End If

End If

End If

End If

End If

End If

End If

'Выводим полученные данные

Text1.Text = Mtr(1, 1)

Text2.Text = Mtr(1, 2)

Text3.Text = Mtr(1, 3)

Text4.Text = Mtr(1, 4)

Text5.Text = Mtr(1, 5)

Text6.Text = Mtr(2, 1)

Text7.Text = Mtr(2, 2)

Text8.Text = Mtr(2, 3)

Text9.Text = Mtr(2, 4)

Text10.Text = Mtr(2, 5)

Text11.Text = Mtr(3, 1)

Text12.Text = Mtr(3, 2)

Text13.Text = Mtr(3, 3)

Text14.Text = Mtr(3, 4)

Text15.Text = Mtr(3, 5)

'Если в какой то ячейки матрицы получился ноль,заменяем его на пустое поле

If Mtr(1, 1) = 0 Then

Text1.Text = ""

Else

Text1.Text = Mtr(1, 1)

End If

If Mtr(1, 2) = 0 Then

Text2.Text = ""

Else

Text2.Text = Mtr(1, 2)

End If

If Mtr(1, 3) = 0 Then

Text3.Text = ""

Else

Text3.Text = Mtr(1, 3)

End If

If Mtr(1, 4) = 0 Then

Text4.Text = ""

Else

Text4.Text = Mtr(1, 4)

End If

If Mtr(1, 5) = 0 Then

Text5.Text = ""

Else

Text5.Text = Mtr(1, 5)

End If

If Mtr(2, 1) = 0 Then

Text6.Text = ""

Else

Text6.Text = Mtr(2, 1)

End If

If Mtr(2, 2) = 0 Then

Text7.Text = ""

Else

Text7.Text = Mtr(2, 2)

End If

If Mtr(2, 3) = 0 Then

Text8.Text = ""

Else

Text8.Text = Mtr(2, 3)

End If

If Mtr(2, 4) = 0 Then

Text9.Text = ""

Else

Text9.Text = Mtr(2, 4)

End If

If Mtr(2, 5) = 0 Then

Text10.Text = ""

Else

Text10.Text = Mtr(2, 5)

End If

If Mtr(3, 1) = 0 Then

Text11.Text = ""

Else

Text11.Text = Mtr(3, 1)

End If

If Mtr(3, 2) = 0 Then

Text12.Text = ""

Else

Text12.Text = Mtr(3, 2)

End If

If Mtr(3, 3) = 0 Then

Text13.Text = ""

Else

Text13.Text = Mtr(3, 3)

End If

If Mtr(3, 4) = 0 Then

Text14.Text = ""

Else

Text14.Text = Mtr(3, 4)

End If

If Mtr(3, 5) = 0 Then

Text15.Text = ""

Else

Text15.Text = Mtr(3, 5)

End If

If Len(Text25.Text) > 1 Then

Text25.BackColor = &H808080

End If

End Sub

Public Static Sub Error_clean()

Text25.BackColor = &HFFFFFF

Text25.Text = ""

Text16.BackColor = &HFFFFFF

Text17.BackColor = &HFFFFFF

Text18.BackColor = &HFFFFFF

Text19.BackColor = &HFFFFFF

Text20.BackColor = &HFFFFFF

Text21.BackColor = &HFFFFFF

Text22.BackColor = &HFFFFFF

Text23.BackColor = &HFFFFFF

Text24.BackColor = &HFFFFFF

End Sub

Public Static Sub Clear()

Text1.Text = ""

Text2.Text = ""

Text3.Text = ""

Text4.Text = ""

Text5.Text = ""

Text6.Text = ""

Text7.Text = ""

Text8.Text = ""

Text9.Text = ""

Text10.Text = ""

Text11.Text = ""

Text12.Text = ""

Text13.Text = ""

Text14.Text = ""

Text15.Text = ""

Text16.Text = ""

Text17.Text = ""

Text18.Text = ""

Text19.Text = ""

Text20.Text = ""

Text21.Text = ""

Text22.Text = ""

Text23.Text = ""

Text24.Text = ""

Text25.Text = ""

Call Error_clean

End Sub

Private Sub solve_it_Click()

Call Solve_Click

End Sub

Private Sub that_is_Click()

Load trzd

trzd.Show

End Sub

Заключение

В курсовой работе изложены основные подходы и методы решения транспортной задачи, являющейся одной из наиболее распространенных задач линейного программирования. Решение данной задачи позволяет разработать наиболее рациональные пути и способы транспортирования товаров, устранить чрезмерно дальние, встречные, повторные перевозки. Все это сокращает время продвижения товаров, уменьшает затраты предприятий и фирм, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д.

Алгоритм и методы решения транспортной задачи могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с транспортировкой груза. В этом случае величины тарифов cij имеют различный смысл в зависимости от конкретной экономической задачи. К таким задачам относятся следующие: оптимальное закрепление за станками операций по обработке деталей. В них cij является таким экономическим показателем, как производительность. Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения cij берутся с отрицательным знаком; оптимальные назначения, или проблема выбора. Имеется m механизмов, которые могут выполнять m различных работ с производительностью cij. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности; задача о сокращении производства с учетом суммарных расходов на изготовление и транспортировку продукции; увеличение производительности автомобильного транспорта за счет минимизации порожнего пробега. Уменьшение порожнего пробега сократит количество автомобилей для перевозок, увеличив их производительность; решение задач с помощью метода запрещения перевозок. Используется в том случае, если груз от некоторого поставщика по каким-то причинам не может быть отправлен одному из потребителей. Данное ограничение можно учесть, присвоив соответствующей клетке достаточно большое значение стоимости, тем самым в эту клетку не будут производиться перевозки. Таким образом, важность решения данной задачи для экономики несомненна. Приятно осознавать, что у истоков создания теории линейного программирования и решения, в том числе и транспортной задачи, стоял русский ученый - Леонид Витальевич Канторович.

Список используемой литературы

математический вычислительный транспортная задача

1. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования М.; Наука, 1976 г.

2. Карманов В.Г. Математическое программирование. - М.; Наука, 1986г.

3. Моисеев Н.Н., Иванов Ю.П., Столярова Е.М. Методы оптимизации. - М.; Наука, 1978г.

4. Иванов Ю.П., Лотов А.В. Математические модели в экономике. - М.; Наука, 1979г.

5. Бронштейн И.Н., Семендяев К.А. Справочник по математике. - М.; Наука, 1986г

6. http://ru.wikipedia.org/wiki/Транспортная_задача

7. http://math.semestr.ru/

Размещено на Allbest.ru