Читайте также:
|
В задачах с закрытой моделью запасы поставщиков совпадают с потребностями потребителей.
Пример 1
Требуется перевезти однородный груз от трех поставщиков А1, А2, А3 к пяти потребителям В1, В2, В3, В4, В5:
Данные по запасам, потребностям в продукте и стоимости перевозок (в правых верхних углах) приведены в таблице 1.
Таблица 1
| Пункт отправления | Пункт назначения | Запасы | ||||
| В1 | В2 | В3 | В4 | В5 | ||
| А1 | 2 х11 | 3 х12 | 4 х13 | 2 х14 | 4 х15 | |
| А2 | 8 х21 | 4 х22 | 1 х23 | 4 х24 | 1 х25 | |
| А3 | 9 х31 | 7 х32 | 3 х33 | 7 х34 | 2 х35 | |
| Потребности |
Построим опорный план методом северо-западного угла. При этом переменной х11 присваивается максимально допустимое значение в данном столбце (в нашем примере – 60). Затем, двигаясь вправо и вниз, заполняются другие клетки таблицы (таблица 2). По правилам, число заполненных клеток должно быть: m + n -1 = 3 + 5 - 1 = 7.
Таблица 2
| v1 | v2 | v3 | v4 | v5 | |
| u1 | 2 | 3 | 4 | 2 | 4 |
| u2 | 8 | 4 | 1 | 4 | 1 |
| u3 | 9 | 7 | 3 | 7 | 2 |
Стоимость этого плана равна:
2*60+3*70+4*10+1*110+4*70+7*60+2*100=1380.
Определяем оптимальный план методом потенциала. Введем потенциалы u1, u2, u3, v1, v2, v3, v4, v5 . Для заполненных клеток составляем систему уравнений для определения потенциалов:
ui +vj = Cij ,
то есть
u1 +v1 = 2;
u1 +v2 = 3;
u1 +v3 = 4;
u2 +v3 = 1; (3)
u2 +v4 = 4;
u3 +v4 = 7;
u3 +v5 = 2.
Так как число переменных равно 8, а уравнений 7, то задаем значение одной из переменных произвольно. Удобно принять u1= 0. Тогда из (3) получим значения потенциалов:
| u1 = 0; u2 = -3; u3 = 0; | v1 = 2; v2 = 3; v3 = 4; v4 = 7; v5 = 2. |
Проверяем условия ui +vj < Cij для незаполненных клеток:
u1 +v4 = 7 >2;
u1 +v5 = 2 <4;
u2 +v1 = -1 <8;
u2 +v2 = 0 <4;
u2 +v5 = -1 <1;
u3 +v2 = 3 <7;
u3 +v1 = 2 <9;
u3 +v3 = 4 >3,
то есть для клеток х14 и х33 условие не выполняется. Для одной из этих клеток необходимо произвести перераспределение плана по циклу (выбирается клетка, где разница наибольшая, то есть х14: 7-2=5). Циклом называется ломаная линия, три вершины которой расположены в занятых клетках, а одна в свободной клетке. В нашем примере вершинами в выделенном цикле будут: [ х13, х14, х24, х23 ]. В заполняемой клетке ставится знак «+», а рядом стоящим – «-». Знак «+/-» означает складывать или вычитать нужно переносимую величину со значением, стоящим в этой клетке (табл. 3). В заполняемую ячейку переносят меньшее значение из минусовых клеток. В данном примере это 10.
Таблица 3
| v1 =2 | v2 =3 | v3 =4 | v4 =7 | v5 =2 | |
| u1 =0 | 2 | 3 | 4
 10 -
| 2 + | 4 |
| u2 =-3 | 8 | 4 | 1 + | - 4 | 1 |
| u3 =0 | 9 | 7 | 3 | 7 | 2 |
После перемещения получаем новый план:
Таблица 4
| v1 =2 | v2 =3 | v3 =4 | v4 =7 | v5 =2 | |
| u1 =0 | 2 | 3 | 4 | 2 | 4 |
| u2 =-3 | 8 | 4 | 1 | 4 60 | 1 |
| u3 =0 | 9 | 7 | 3 | 7 | 2 |
Проверяем его на оптимальность и находим новые значения потенциалов.
| u1 +v1 = 2; u1 +v2 = 3; u1 +v4 = 2; u2 +v3 = 1; u2 +v4 = 4; u3 +v4 = 7; u3 +v5 = 2; |  u1 = 0;
u2 = 2;
u3 = 5;
| v1 = 2; v2 = 3; v3 = -1; v4 = 2; v5 = -3. |
Проверяем условие ui +vj < Cij для свободных клеток:
u1 +v3 = -1 < 4;
u1 +v5 = -3 < 4;
u2 +v1 = 4 < 8;
u2 +v2 = 5 > 4;
u2 +v5 = -1 < 1;
u3 +v1 = 7 < 9;
u3 +v2 = 8 >7;
u3 +v3 = 4 > 3.
Для ячеек х22 , х32 и х33 условие оптимальности не выполняется. Устанавливаем цикл с вершинами [ х12, х14, х24, х22 ]. Наименьшее из минусовых клеток – 60.
Таблица 5
| v1 =2 | v2 =3 | v3 =2 | v4 =-1 | v5 =-3 | |
| u1 =0 | 2 | 3
 70 -
| 4 | 2 +10 | 4 |
| u2 =2 | 8 | 4 + | 1 | 4 - 60 | 1 |
| u3 =5 | 9 | 7 | 3 | 7 | 2 |
Далее решаем по аналогии:
| u1 +v1 = 2; u1 +v2 = 3; u1 +v4 = 2; u2 +v4 = 4; u2 +v3 = 1; u3 +v4 = 7; u3 +v5 = 2; |  u1 = 0;
u2 = 1;
u3 = 5;
| v1 = 2; v2 = 3; v3 = 0; v4 = 2; v5 = -3. |
Новый план примет вид:
Таблица 6
| v1 =2 | v2 =3 | v3 =0 | v4 =2 | v5 = -3 | |
| u1 =0 | 2 | 3 | 4 | 2 | 4 |
| u2 =1 | 8 | 4 | 1 | 4 | 1 |
| u3 =5 | 9 | 7 | 3 | 7 | 2 |
Проверяем условие ui +vj < Cij для свободных клеток
u1 +v3 = 0 < 4;
u1 +v5 = -3 < 4;
u2 +v1 = 3 < 8;
u2 +v4 = 3 < 4;
u2 +v5 = -2 < 1;
u3 +v1 = 7 < 9;
u3 +v2 = 8 > 7;
u3 +v3 = 5 > 3.
Для клетки х32 и х33 условие оптимальности не выполняется. Выбираем цикл с вершинами [ х12, х14, х34, х32 ].
Таблица 7
| v1 =2 | v2 =3 | v3 =0 | v4 =2 | v5 = -3 | |
| u1 =0 | 2 | 3
 10 -
| 4 | 2 +70 | 4 |
| u2 =1 | 8 | 4 | 1 | 4 | 1 |
| u3 =5 | 9 | 7 + | 3 | - 7 | 2 |
После перемещения 10 получаем новую таблицу:
Таблица 8
| v1 =2 | v2 =3 | v3 = 0 | v4 =2 | v5 = -3 | |
| u1 =0 | 2 | 3 | 4 | 2 | 4 |
| u2 =1 | 8 | 4 | 1 | 4 | 1 |
| u3 =5 | 9 | 7 | 3 | 7 | 2 |
Решаем по аналогии:
| u1 +v1 = 2; u1 +v4 = 2; u2 +v2 = 4; u2 +v3 = 1; u3 +v2 = 7; u3 +v4 = 7; u3 +v5 = 2; |  u1 = 0;
u2 = 2;
u3 = 5;
| v1 = 2; v2 = 2; v3 = -1; v4 = 2; v5 = -3. |
Проверяем условие ui +vj < Cij:
u1 +v2 = 2 < 3;
u1 +v3 = -1 < 4;
u1 +v5 =- 3 < 4;
u2 +v1 = 4 < 8;
u2 +v4 = 4 = 4;
u2 +v5 = -1 < 1;
u3 +v1 = 7 < 9;
u3 +v3 = 4 > 3.
Для клетки х33 условие оптимальности не выполняется. Выбираем цикл с вершинами [ х22, х23, х33, х32 ]
Таблица 9
| v1 =2 | v2 =2 | v3 = -1 | v4 =2 | v5 = -3 | |
| u1 =0 | 2 | 3 | 4 | 2 | 4 |
| u2 =2 | 8 | 4
 60 +
| 1 -120 | 4 | 1 |
| u3 =5 | 9 | 7 - | + 3 | 7 | 2 |
Наименьшее отрицательное значение равно 10, после перемещения получаем таблицу:
Таблица 10
| v1 =2 | v2 =2 | v3 = -1 | v4 =2 | v5 = -3 | |
| u1 =0 | 2 | 3 | 4 | 2 | 4 |
| u2 =2 | 8 | 4 | 1 | 4 | 1 |
| u3 =5 | 9 | 7 | 3 | 7 | 2 |
Находим потенциалы:
| u1 +v1 = 2; u1 +v4 = 2; u2 +v2 = 4; u2 +v3 = 1; u3 +v3 = 3; u3 +v4 = 7; u3 +v5 = 2; |  u1 = 0;
u2 = 3;
u3 = 5;
| v1 = 2; v2 = 2; v3 = -2; v4 = 2; v5 = -3. |
Проверяем условие оптимальности ui +vj < Cij:
u1 +v2 = 2 < 3;
u1 +v3 = -2 < 4;
u1 +v5 =- 3 < 4;
u2 +v1 = 5 < 8;
u2 +v4 = 5 > 4;
u2 +v5 = 0 < 1;
u3 +v1 = 7 < 9;
u3 +v2 = 6 < 7.
Для клетки х24 условие оптимальности не выполняется. Выбираем цикл с вершинами [ х23, х24, х34, х33 ].
Таблица 11
| v1 =2 | v2 =2 | v3 = -2 | v4 =2 | v5 = -3 | |
| u1 =0 | 2 | 3 | 4 | 2 | 4 |
| u2 =3 | 8 | 4 |  1
110 -
| 4 + | 1 |
| u3 =5 | 9 | 7 | 3 + | - 7 | 2 |
Перемещаем 50. Новый план представлен в таблице 12. Находим новые потенциалы:
| u1 +v1 = 2; u1 +v4 = 2; u2 +v2 = 4; u2 +v3 = 1; u2 +v4 = 4; u3 +v3 = 3; u3 +v5 = 2; |  u1 = 0;
u2 = 2;
u3 = 4;
| v1 = 2; v2 = 2; v3 = -1; v4 = 2; v5 = -2. |
Таблица 12
| v1 =2 | v2 =2 | v3 = -1 | v4 =2 | v5 = -2 | |
| u1 =0 | 2 | 3 | 4 | 2 | 4 |
| u2 =2 | 8 | 4 | 1 | 4 | 1 |
| u3 =4 | 9 | 7 | 3 | 7 | 2 |
Проверяем условие оптимальности ui +vj < Cij:
u1 +v2 = 2 < 3;
u1 +v3 = -1 < 4;
u1 +v5 =- 2 < 4;
u2 +v1 = 4 < 8;
u2 +v5 = 0 < 1;
u3 +v1 = 6 < 9;
u3 +v2 = 6 < 7;
u3 +v4 = 6 < 7.
Условие оптимальности выполняется для всех клеток, значит и полученный план является оптимальным. Стоимость этого плана:
F = 2*60 +2*80 + 4*70 + 1*60 + 4*50 + 3*60 + 2*100 = 1000.
Дата добавления: 2015-10-13; просмотров: 61 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Постановка задачи и её математическая модель | | | Открытая транспортная задача |