Методические указания к решению типовых задач
На трех складах оптовой базы сосредоточен однородный груз в количествах 200, 300 и 500 ед. Этот груз необходимо перевезти в четыре магазина. Каждый из магазинов должен получить соответственно 200, 200, 300 и 400 ед. груза. Тарифы перевозок единицы груза из каждого из складов во все магазины задаются матрицей:
С=
Требуется:
1) составить экономико-математическую модель задачи;
2) найти первоначальное распределение поставок: а) методом северо-западного угла; б) методом минимальных затрат.
3) выбрать лучшее распределение поставок и найти такой план перевозок, при котором общая стоимость перевозок будет минимальной.
Решить транспортную задачу методом потенциалов.
Решение:
1) составление экономико-математической модели ТЗ
Искомый объем перевозки от i-ro поставщика к j-му потребителю обозначим xij и назовем поставкой клетки (i,j). Заданные объемы груза, имеющегося на базах, и спросы магазинов накладывают ограничения на значения неизвестных. Получаем следующую систему ограничений из уравнений баланса по строкам и столбцам.
Транспортная задача – задача на минимум. Поэтому целевая функция имеет вид:
2) найдем первоначальное распределение поставок (опорное решение)
Проверим выполнение необходимого и достаточного условия разрешимости задачи – условие закрытости модели.
Имеем открытую модель транспортной задачи, необходимо сбалансировать общие итоги. Вводим 4-го, фиктивного поставщика с запасами
a4 = 1100-1000 = 100
и нулевыми стоимостями перевозок единиц груза.
а) Построим первоначальное распределение поставок методом северо-западного угла:
Распределим запасы первой базы. Так как ее запасы а1=200 равны потребностям первого магазина b1=200, необходимо ввести условную нулевую поставку, например, по строке. Из дальнейшего рассмотрения исключаются первая строка и столбец (см.табл.2.2)
Т а б л и ц а 2.2
bj ai |
200 |
200 |
300 |
400 |
200 |
4 200 |
3 0 |
2 |
1 |
300 |
2
|
3 |
5 |
6 |
500 |
6
|
7 |
9 |
12 |
100 |
0
|
0 |
0 |
0 |
Распределим запасы второй базы. Так как ее запасы а2=300 больше потребностей второго магазина b2=200, в клетку (2,2) вносим число 200, вычеркиваем второй столбец и запоминаем, что остатки груза на второй базе составляют а2'=300-200=100 (см.табл.2.3)
Т а б л и ц а 2.3
bj ai |
200 |
200 |
300 |
400 |
200 |
4 200 |
3 0 |
2 |
1 |
300 |
2
|
3 200 |
5 |
6 |
500 |
6
|
7 |
9 |
12 |
100 |
0
|
0 |
0 |
0 |
Распределим остатки запасов второй базы. Так как ее запасы а2’=100 меньше потребностей третьего магазина b3=300, в клетку (2,3) вносим число 100, вычеркиваем вторую строку и запоминаем, что третьему магазину следует допоставить 200 ед.груза (b2’=300-100=200) (см.табл.2.4)
Т а б л и ц а 2.4
bj ai |
200 |
200 |
300 |
400 |
200 |
4 200 |
3 0 |
2 |
1 |
300 |
2
|
3 200 |
5 100 |
6 |
500 |
6
|
7 |
9 |
12 |
100 |
0
|
0 |
0 |
0 |
Последовательно выполняя такие действия, получаем первоначальное распределение поставок по методу северо-западного угла, приведенное в таблице 2.5.
Т а б л и ц а 2.5
bj ai |
200 |
200 |
300 |
400 |
200 |
4 200 |
3 0 |
2 |
1 |
300 |
2
|
3 200 |
5 100 |
6 |
500 |
6
|
7 |
9 200 |
12 300 |
100 |
0
|
0 |
0 |
0 100 |
Полученное решение является базисным, т.к. выполняется необходимое и достаточное условиеr=m+n-1=4+4-1=7. Найдем значение целевой функции для полученного решения
F=4200+3200+5100+9200+12300=7300 руб.
б) Построим первоначальное распределение поставок методом наименьших затрат (минимальной стоимости):
Среди элементов стоимостей выбираем наименьшую стоимость (без учета нулевых стоимостей условной, четвертой базы) с14=1. В соответствующую клетку записываем максимально возможную поставку х14=max {a1, b4}={200, 400}= 200. Потребности 4-го магазина уменьшаем на 400-200=200, вычеркиваем первую строку (табл.2.6).
Т а б л и ц а 2.6
bj ai |
200 |
200 |
300 |
400 |
200 |
4
|
3
|
2 |
1 200 |
300 |
2
|
3 |
5 |
6 |
500 |
6
|
7 |
9 |
12 |
100 |
0
|
0 |
0 |
0 |
В оставшейся части таблицы поставок также определяем элемент с наименьшим тарифом – это с21=2. Здесь наибольшая возможная поставка составит х21=max {a2, b1}={300, 200}= 200, запасы второй базы уменьшаем до 100 ед., вычеркиваем первый столбец – табл.2.7.
Т а б л и ц а 2.7
bj ai |
200 |
200 |
300 |
400 |
200 |
4
|
3
|
2 |
1 200 |
300 |
2 200 |
3 |
5 |
6 |
500 |
6
|
7 |
9 |
12 |
100 |
0
|
0 |
0 |
0 |
Продолжая таким же образом, получаем первоначальное распределение поставок методом минимальной стоимости, приведенное в таблице 2.8.
Т а б л и ц а 2.8
bj ai |
200 |
200 |
300 |
400 |
200 |
4
|
3
|
2 |
1 200 |
300 |
2 200 |
3 100 |
5 |
6 |
500 |
6
|
7 100 |
9 300 |
12 100 |
100 |
0
|
0 |
0 |
0 100 |
Полученное решение имеет r=m+n-1=4+4-1=7 базисных переменных. Вычислим значение целевой функции на этом опорном решении .
F=1200+2200+3100+7100+9300+12100=5500 руб.
Сравнивая значения целевых функций для опорных планов, полученных методами северо-западного угла и минимальной стоимости, делаем вывод, что целевая функция для второго случая ближе к минимуму.
3) проверка критерия оптимальности найденного решения
По признаку оптимальности в каждой занятой опорным решением таблицы ТЗ сумма потенциалов равна стоимости (ui+vj=cij при ). Составим систему уравнений для нахождения потенциалов строк и столбцов матрицы поставок
Система состоит из семи уравнений и имеет восемь переменных. Система неопределенная. Одной переменной задаем произвольное значение (пусть u1=0). Остальные значения потенциалов находятся однозначно:
u1 = 0 u2 =7 u3 = 11 u4 = -1 |
v1 =-5 v2 =-4 v3 = -2 v4 = 1 |
Вычислим оценки свободных клеток с учетом найденных потенциалов:
Критерий оптимальности не выполняется, т.к. d24=-2<0.
- переход к следующему опорному решению
Для перехода к следующему базисному решению построим цикл для клетки (2,4) – загрузим ее поставкой (см. табл. 2.9).
Т а б л и ц а 2.9
bj ai |
200 |
200 |
300 |
400 |
200 |
4
|
3
|
2 |
1 200 |
300 |
2 200 |
- 100 |
5 |
+ |
500 |
6
|
+ 100 |
9 300 |
- 100 |
100 |
0
|
0 |
0 |
0 100 |
Определим поставку, передаваемую по циклу γ=min {100, 100} (как наименьшее из чисел, находящихся в вершинах цикла со знаком «-»). Клетку (3,4) с тарифом с34=12 будем считать свободной. Следующее базисное распределение представлено в таблице 2.10
Т а б л и ц а 2.10
bj ai |
200 |
200 |
300 |
400 |
200 |
4
|
3
|
2 |
1 200 |
300 |
2 200 |
3 0 |
5 |
6 100 |
500 |
6
|
7 200 |
9 300 |
12
|
100 |
0
|
0 |
0 |
0 100 |
Проверим найденное решение на оптимальность. Составим систему уравнений для нахождения потенциалов строк и столбцов новой матрицы поставок
Пусть u1=0, тогда
u1 = 0 u2 = 5 u3 = 9 u4 = -1 |
v1 = -3 v2 = -2 v3 = 0 v4 = 1 |
Вычислим оценки свободных клеток с учетом найденных потенциалов и проверим выполнение критерия оптимальности:
Критерий оптимальности выполняется, следовательно, найденное опорное решение оптимально. Найдем минимальное значение стоимости перевозок:
Fmin=1200+2200+30+6100+7200+9300=4040 руб.
Ответ: Fmin= 4040 руб. при .