Математическая модель транспортной задачи
Контрольная работа, 20 Марта 2012, автор: пользователь скрыл имя
Описание работы
Однородный груз сосредоточен у m поставщиков в объемах a1, a2, ... am.
Данный груз необходимо доставить n потребителям в объемах b1, b2 ... bn.
Известны Cij , i=1,2,...m; j=1,2,...n — стоимости перевозки единиц груза от каждого i-го поставщика каждому j-му потребителю.
Требуется составить такой план перевозок, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью, и суммарные затраты на перевозку всех грузов являются минимальными.
Работа содержит 1 файл
Документ Microsoft Word (2).docx
— 338.77 Кб (Скачать)
3) |
Минимальный элемент матрицы тарифов находится в ячейке A3B1 и равен 2, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A3 к потребителю B1 наиболее рентабельный. |
Запасы поставщика A3 составляют 15 единиц продукции. Потребность потребителя B1 составляет 20 единиц продукции. (см. таблицу пункта 2) |
От поставщика A3 к потребителю B1 будем доставлять min = { 15 , 20 } = 15 единиц продукции. |
Разместим в ячейку A3B1 значение равное 15 |
Мы полностью израсходoвали запасы поставщика A3. Вычеркиваем строку 3 таблицы, т.е исключаем ее из дальнейшего рассмотрения. |
Поставщик |
Потребитель |
Запас | ||||||||||||||
B 1 |
B 2 |
B 3 | ||||||||||||||
|
A 1 |
|
|
|
30 | ||||||||||||
A 2 |
|
|
|
25 | ||||||||||||
A 3 |
|
|
|
15 | ||||||||||||
Потребность |
20 |
35 |
15 |
|||||||||||||
4) |
Минимальный элемент матрицы тарифов находится в ячейке A2B1 и равен 4, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A2 к потребителю B1 наиболее рентабельный. |
Запасы поставщика A2 составляют 25 единиц продукции. Потребность потребителя B1 составляет 5 единиц продукции. (см. таблицу пункта 3) |
От поставщика A2 к потребителю B1 будем доставлять min = { 25 , 5 } = 5 единиц продукции. |
Разместим в ячейку A2B1 значение равное 5 |
Мы полностью
удовлетворили потребность |
Поставщик |
Потребитель |
Запас | ||||||||||||||
B 1 |
B 2 |
B 3 | ||||||||||||||
|
A 1 |
|
|
|
30 | ||||||||||||
A 2 |
|
|
|
25 | ||||||||||||
A 3 |
|
|
|
15 | ||||||||||||
Потребность |
20 |
35 |
15 |
|||||||||||||
5) |
Минимальный элемент матрицы тарифов находится в ячейке A2B3 и равен 4, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A2 к потребителю B3 наиболее рентабельный. |
Запасы поставщика A2 составляют 20 единиц продукции. Потребность потребителя B3 составляет 15 единиц продукции. (см. таблицу пункта 4) |
От поставщика A2 к потребителю B3 будем доставлять min = { 20 , 15 } = 15 единиц продукции. |
Разместим в ячейку A2B3 значение равное 15 |
Мы полностью
удовлетворили потребность |
Поставщик |
Потребитель |
Запас | ||||||||||||||
B 1 |
B 2 |
B 3 | ||||||||||||||
|
A 1 |
|
|
|
30 | ||||||||||||
A 2 |
|
|
|
25 | ||||||||||||
A 3 |
|
|
|
15 | ||||||||||||
Потребность |
20 |
35 |
15 |
|||||||||||||
6) |
Минимальный элемент матрицы тарифов находится в ячейке A2B2 и равен 5, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A2 к потребителю B2 наиболее рентабельный. |
Запасы поставщика A2 составляют 5 единиц продукции. Потребность потребителя B2 составляет 5 единиц продукции. (см. таблицу пункта 5) |
От поставщика A2 к потребителю B2 будем доставлять 5 единиц продукции. |
Разместим в ячейку A2B2 значение равное 5 |
Мы полностью израсходoвали запасы поставщика A2. Вычеркиваем строку 2 таблицы, т.е исключаем ее из дальнейшего рассмотрения. |
Поставщик |
Потребитель |
Запас | ||||||||||||||
B 1 |
B 2 |
B 3 | ||||||||||||||
|
A 1 |
|
|
|
30 | ||||||||||||
A 2 |
|
|
|
25 | ||||||||||||
A 3 |
|
|
|
15 | ||||||||||||
Потребность |
20 |
35 |
15 |
|||||||||||||
Заполненные нами ячейки будем называть базисными, остальные - свободными. |
Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице. |
Количество базисных ячеек (задействованных маршрутов) равно 5, что и требовалось. |
Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей. |
S0 = 1 * 30 + 4 * 5 + 5 * 5 + 4 * 15 + 2 * 15 = 165 ден. ед. |
Общие затраты на доставку всей продукции, для начального решения , составляют 165 ден. ед. . |
Дальнейшие наши действия будут состоять из шагов, каждый из которых состоит в следующем: |
· Находим потенциалы поставщиков и потребителей для имеющегося решения. |
· Находим оценки свободных ячеек. Если все оценки окажутся неотрицательными - задача решена. |
· Выбираем свободную ячейку (с отрицательной оценкой), выбор которой, позволяет максимально снизить общую стоимость доставки всей продукции на данном шаге решения. |
· Находим новое решение, как минимум, не хуже предыдущего. |
· Вычисляем общую стоимость доставки всей продукции для нового решения. |
Шаг 1
ПРОИЗВЕДЕМ ОЦЕНКУ ПОЛУЧЕННОГО РЕШЕНИЯ. |
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||