Автор: Пользователь скрыл имя, 16 Января 2013 в 08:13, задача
Задача :
У поставщиков A1 , A2 , A3 , A4 , находится соответственно 70 , 80 , 90 , 80 единиц однотипной продукции, которая должна быть доставлена потребителям B1 , B2 , B3 , B4 в количестве 60 , 40 , 120 , 100 единиц соответственно.
Стоимость доставки единицы продукции от поставщика A1 к указанным потребителям равна 4 , 8 , 1 , 6 ден.ед.
Стоимость доставки единицы продукции от поставщика A2 к указанным потребителям равна 3 , 5 , 3 , 4 ден.ед.
Стоимость доставки единицы продукции от поставщика A3 к указанным потребителям равна 2 , 6 , 4 , 3 ден.ед.
Стоимость доставки единицы продукции от поставщика A4 к указанным потребителям равна 1 , 4 , 5 , 3 ден.ед.
Требуется найти оптимальное решение доставки продукции от поставщиков к потребителям, минимизирующие стоимость доставки.
5) |
Минимальный элемент матрицы тарифов находится в ячейке A3B4 и равен 3, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A3 к потребителю B4 наиболее рентабельный. |
Запасы поставщика A3 составляют 90 единиц продукции. Потребность потребителя B4 составляет 100 единиц продукции. (см. таблицу пункта 4) |
От поставщика A3 к потребителю B4 будем доставлять min = { 90 , 100 } = 90 единиц продукции. |
Разместим в ячейку A3B4 значение равное 90 |
Мы полностью израсходoвали запасы поставщика A3. Вычеркиваем строку 3 таблицы, т.е исключаем ее из дальнейшего рассмотрения. |
Поставщик |
Потребитель |
Запас | |||||||||||||||||||
B 1 |
B 2 |
B 3 |
B 4 | ||||||||||||||||||
|
A 1 |
|
|
|
|
70 | ||||||||||||||||
A 2 |
|
|
|
|
80 | ||||||||||||||||
A 3 |
|
|
|
|
90 | ||||||||||||||||
A 4 |
|
|
|
|
80 | ||||||||||||||||
Потребность |
60 |
40 |
120 |
100 |
|||||||||||||||||
6) |
Минимальный элемент матрицы тарифов находится в ячейке A4B4 и равен 3, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A4 к потребителю B4 наиболее рентабельный. |
Запасы поставщика A4 составляют 20 единиц продукции. Потребность потребителя B4 составляет 10 единиц продукции. (см. таблицу пункта 5) |
От поставщика A4 к потребителю B4 будем доставлять min = { 20 , 10 } = 10 единиц продукции. |
Разместим в ячейку A4B4 значение равное 10 |
Мы полностью
удовлетворили потребность |
Поставщик |
Потребитель |
Запас | |||||||||||||||||||
B 1 |
B 2 |
B 3 |
B 4 | ||||||||||||||||||
|
A 1 |
|
|
|
|
70 | ||||||||||||||||
A 2 |
|
|
|
|
80 | ||||||||||||||||
A 3 |
|
|
|
|
90 | ||||||||||||||||
A 4 |
|
|
|
|
80 | ||||||||||||||||
Потребность |
60 |
40 |
120 |
100 |
|||||||||||||||||
7) |
Минимальный элемент матрицы тарифов находится в ячейке A4B2 и равен 4, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A4 к потребителю B2 наиболее рентабельный. |
Запасы поставщика A4 составляют 10 единиц продукции. Потребность потребителя B2 составляет 40 единиц продукции. (см. таблицу пункта 6) |
От поставщика A4 к потребителю B2 будем доставлять min = { 10 , 40 } = 10 единиц продукции. |
Разместим в ячейку A4B2 значение равное 10 |
Мы полностью израсходoвали запасы поставщика A4. Вычеркиваем строку 4 таблицы, т.е исключаем ее из дальнейшего рассмотрения. |
Поставщик |
Потребитель |
Запас | |||||||||||||||||||
B 1 |
B 2 |
B 3 |
B 4 | ||||||||||||||||||
|
A 1 |
|
|
|
|
70 | ||||||||||||||||
A 2 |
|
|
|
|
80 | ||||||||||||||||
A 3 |
|
|
|
|
90 | ||||||||||||||||
A 4 |
|
|
|
|
80 | ||||||||||||||||
Потребность |
60 |
40 |
120 |
100 |
|||||||||||||||||
8) |
Минимальный элемент матрицы тарифов находится в ячейке A2B2 и равен 5, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A2 к потребителю B2 наиболее рентабельный. |
Запасы поставщика A2 составляют 30 единиц продукции. Потребность потребителя B2 составляет 30 единиц продукции. (см. таблицу пункта 7) |
От поставщика A2 к потребителю B2 будем доставлять 30 единиц продукции. |
Разместим в ячейку A2B2 значение равное 30 |
Мы полностью израсходoвали запасы поставщика A2. Вычеркиваем строку 2 таблицы, т.е исключаем ее из дальнейшего рассмотрения. |
Поставщик |
Потребитель |
Запас | |||||||||||||||||||
B 1 |
B 2 |
B 3 |
B 4 | ||||||||||||||||||
|
A 1 |
|
|
|
|
70 | ||||||||||||||||
A 2 |
|
|
|
|
80 | ||||||||||||||||
A 3 |
|
|
|
|
90 | ||||||||||||||||
A 4 |
|
|
|
|
80 | ||||||||||||||||
Потребность |
60 |
40 |
120 |
100 |
|||||||||||||||||
Заполненные нами ячейки будем называть базисными, остальные - свободными. |
Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице. |
Количество базисных ячеек (задействованных маршрутов) равно 7, что и требовалось. |
Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей. |
S0 = 1 * 70 + 5 * 30 + 3 * 50 + 3 * 90 + 1 * 60 + 4 * 10 + 3 * 10 = 770 ден. ед. |
Общие затраты на доставку всей продукции, для начального решения , составляют 770 ден. ед. . |
Дальнейшие наши действия будут состоять из шагов, каждый из которых состоит в следующем: |
· Находим потенциалы поставщиков и потребителей для имеющегося решения. |
· Находим оценки свободных ячеек. Если все оценки окажутся неотрицательными - задача решена. |
· Выбираем свободную ячейку (с отрицательной оценкой), выбор которой, позволяет максимально снизить общую стоимость доставки всей продукции на данном шаге решения. |
· Находим новое решение, как минимум, не хуже предыдущего. |
· Вычисляем общую стоимость доставки всей продукции для нового решения. |
Шаг 1
ПРОИЗВЕДЕМ ОЦЕНКУ ПОЛУЧЕННОГО РЕШЕНИЯ. |
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||