 |
Принятие решений в условиях определённости
|
|
|
|
Задача. Пусть имеется 3 магазина розничной торговли, расположенные в разных районах города (А, В, С). Поставки продукции в эти магазины осуществляются с четырёх складов (1, 2, 3, 4).
| Магазины | ||||
| А | В | С | ||
| № склада | ||||
Найти оптимальное распределение поставок, при котором суммарные затраты на перевозку были бы минимальными.
Решение:
Обозначим сji - поставки, доставляемого из i-го склада в j-магазин. Тогда модель имеет следующий вид:
V= 2с11 + 5с12 + 4с13 + 1с21 + 4с22 + 5с23 + 2с31 + 6с32 + 5с33+4с41 + 3с42 + 1с43 ® min
 |
 |
Определим начальный план поставок с помощью метода северо-западного угла, по которому транспортная матрица заполняется слева - направо и сверху - вниз.
Мы должны заполнить m+n-1 клеток, где m – число складов, a n- число магазинов. Если число заполненных клеток меньше m+n-1, то недостающие клетки выбираются произвольно и заполняются нулями. Число заполненных клеток должно быть 4+3-1=6
| Склады | Магазины | Запас | |||
| А | В | С | |||
| v1=2 | v2=5 | v3=4 | |||
| u1=0 | |||||
| u2=1 | |||||
| u3=-1 | |||||
| u4=3 | |||||
| спрос |
Суммарные затраты на перевозку рассчитываются по 6 заполненным клеткам:
L1=2*30+1*10+4*15+6*5+5*10+1*30=240 (ден.ед.)
Рассчитаем потенциалы на основе равенства:
Присвоим первому поставщику потенциал равный нулю. Значения потенциалов заносим в вышестоящую таблицу.
Проверим первоначальный план на оптимальность. План считается оптимальным, если для всех свободных клеток выполняется условие:
|
|
|
Осуществляем проверку:
Условие оптимальности не выполняется, так как имеются положительные оценки. Для улучшения плана необходимо переместить перевозку в клетку, где условие оптимальности нарушено больше всего. Такой клеткой является клетка с31.
Перемещение производится так, чтобы по отношению к выбранной клетке образовать связку. Для этого необходимо провести замкнутую ломаную линию, состоящую из горизонтальных и вертикальных линий, в которой одной из вершин полученного многоугольника является свободная клетка, а в остальных вершинах должны находиться занятые клетки.
| Склады | Магазины | Запас | |||
| А | В | С | |||
| v1=2 | v2=5 | v3=4 | |||
| u1=0 | |||||
| u2=1 |  1
| ||||
| u3=-1 | |||||
| u4=3 | |||||
| спрос |
Далее каждой клетке в связке поочередно присваиваются знаки плюс и минус, начиная со свободной. Из клеток со знаком минус перемещаем перевозки в клетки со знаком плюс.
| Склады | Магазины | Запас | |||
| А | В | С | |||
| v1=2 | v2=5 | v3=4 | |||
| u1=0 | |||||
 30
| |||||
| u2=1 | |||||
| u3=-1 | |||||
| u4=3 | |||||
| спрос |
Чтобы не получить отрицательных перевозок, перемещаем наименьшее количество продукта, которое находится в клетках связки со знаком минус, т.е. min {10;5}. Там где «+» прибавим 5, где «-» отнимем 5.
Последовательное улучшение плана представлено в таблице.
| Склады | Магазины | Запас | |||
| А | В | С | |||
| v1=2 | v2=5 | v3=5 | |||
| u1=0 | |||||
| u2=1 | |||||
| u3=0 | |||||
| u4=4 | |||||
| спрос |
Суммарные затраты на перевозку рассчитываются по 6 заполненным клеткам:
|
|
|
L2= 2*30+1*5+4*20+2*5+5*10+1*30=235 (ден.ед.)
Рассчитаем потенциалы на основе равенства:
Присвоим первому поставщику потенциал равный нулю. Значения потенциалов заносим в вышестоящую таблицу.
Проверим первоначальный план на оптимальность. План считается оптимальным, если для всех свободных клеток выполняется условие:
Осуществляем проверку:
Условие оптимальности не выполняется, так как имеется положительная оценка. Для улучшения плана необходимо переместить перевозку в клетку, где условие оптимальности нарушено. Такой клеткой является клетка с21.
По отношению к выбранной клетке образовываем связку.
| Склады | Магазины | Запас | |||
| А | В | С | |||
| v1=2 | v2=5 | v3=5 | |||
| u1=0 |  2
| ||||
| u2=1 | |||||
| u3=0 | |||||
| u4=4 | |||||
| спрос |
Чтобы не получить отрицательных перевозок, перемещаем наименьшее количество продукта, которое находится в клетках связки со знаком минус, т.е. min {10;30}. Там где «+» прибавим 10, где «-» отнимем 10.
Последовательное улучшение плана представлено в таблице.
| Склады | Магазины | Запас | |||
| А | В | С | |||
| v1=2 | v2=5 | v3=4 | |||
| u1=0 | |||||
| u2=1 | |||||
| u3=0 | |||||
| u4=3 | |||||
| спрос |
Суммарные затраты на перевозку рассчитываются по 6 заполненным клеткам:
L3= 2*20+4*10+1*5+4*20+2*15+1*30=225 (ден.ед.)
Рассчитаем потенциалы на основе равенства для занятых клеток:
Присвоим первому поставщику потенциал равный нулю. Значения потенциалов заносим в вышестоящую таблицу.
Проверим первоначальный план на оптимальность. План считается оптимальным, если для всех свободных клеток выполняется условие:
Осуществляем проверку:
Условие оптимальности выполняется. Равенство указывает на то, что данное оптимальное решение данной задачи не единственное.
Оптимальный план содержит шесть перевозок: перевозка из первого склада - 20ед. продукции в магазин А и 10ед. в магазин C; перевозка из второго склада - 5ед. продукции в магазин A и 20ед. в магазин В; перевозка из третьего склада 15 ед. продукции в магазин А; из 4 склада 30 ед. продукции в магазин С. При этом общая сумма транспортных расходов минимальна и составляет 225 (ден.ед.)
|
|
|
Ответ: Оптимальный план содержит шесть перевозок: перевозка из первого склада - 20ед. продукции в магазин А и 10ед. в магазин C; перевозка из второго склада - 5ед. продукции в магазин A и 20ед. в магазин В; перевозка из третьего склада 15 ед. продукции в магазин А; из 4 склада 30 ед. продукции в магазин С. При этом общая сумма транспортных расходов минимальна и составляет 225 (ден.ед.)
Данный оптимальный план перевозок продукции не единственный.
|
|
|
