На комбинатах ЖБК имеются Хi единиц железобетонных панелей, размешенных в i-х складских помещениях. Их необходимо доставить на j-е объекты с учетом их потребностей (Уj). Стоимость перевозки единицы продукции от i-ro поставщика к j-му потребителю известна для всех возможных вариантов доставки и равна Сij руб. Исходные данные по вариантам указаны в табл. 13 и 14.
Составьте план перевозки (Аij) железобетонных изделий так, чтобы общая стоимость этих перевозок была наименьшей и потребности всех потребителей были бы удовлетворены. Задачу решите двумя способами: методом северо-западного угла и методом наименьшей стоимости.
Исходные данные по стоимости и объемам поставок
1-я
цифра С31 С32 С33 2-я
цифра Х1
С34 С41 С42 С43 3-я
цифра С44 Х2
Х3
2 2 0 2 2 10 5 2 1 6 7 5 19 24
1-я
цифра С11 С12 У1
2-я
цифра С13 С14 С21 У2
3-я
цифра С22 С23 С24 У3 У4
2 5 1 5 2 4 1 3 12 7 4 1 2 30 28
Решение
Х4 = У1 + У2 + У3 + У4 - Х1 – Х2 – Х3 =5+12+30+28-10-19-24= 22
1) Распределение перевозок методом северо-западного угла:
Потреб
Постав. У1
У2
У3 У4
хi
Х1
5
5 1
5 4 1 10
Х2
3 4
7 1
12 2 19
Х3 2 0
2
18 5
6 24
Х4
2 1 6
5
22 22
уj
5 12 30 28
Распределение начинаем с клетки (1;1). В нее можем записать 5 ед. груза т.к. у поставщика Х1 есть в наличии 10 ед. груза, а потребитель У1 готов принять только 5 ед. груза.
Следующей заполняем клетку (1;2), в нее можем записать 5 ед. груза т.к. у поставщика Х1 осталось в наличии только 5 ед. груза, а потребитель У2 готов принять 12 ед. груза.
Следующей заполняем клетку (2;2), в нее можем записать 7 ед. груза т.к. у поставщика Х2 есть в наличии 19 ед. груза, а потребителю У2 осталось довезти 7 ед. груза.
Следующей заполняем клетку (2;3), в нее можем записать 12 ед. груза т.к. у поставщика Х2 осталось в наличии только 12 ед. груза, а потребитель У3 готов принять 30 ед. груза.
Следующей заполняем клетку (3;3), в нее можем записать 18 ед. груза т.к. у поставщика Х3 есть в наличии 24 ед. груза, а потребителю У3 осталось довезти 18 ед. груза.
Следующей заполняем клетку (3;4), в нее можем записать 6 ед. груза т.к. у поставщика Х3 осталось в наличии только 6 ед. груза, а потребитель У4 готов принять 28 ед. груза.
Следующей заполняем клетку (4;4), в нее можем записать 22 ед. груза т.к. у поставщика Х4 есть в наличии 22 ед. груза, а потребителю У4 осталось довезти 22 ед. груза. Все запасы распределены.
Ход заполнения клеток: (1;1), (1;2), (2;2), (2;3), (3;3), (3;4), (4;4).
Стоимость перевозки составит:
Z= 5×5+5×1+7×4+12×1+18×2+6×5+22×5=246 руб.
2) Распределение перевозок методом минимальной стоимости.
Потреб
Постав
. У1
У2
У3 У4
хi
Х1
5
1
4 1
10 10
Х2
3 4
1
19 2 19
Х3 2 0
12 2
11 5
1 24
Х4
2
5 1 6
5
17 22
уj
5 12 30 28
Заполнение начинаем с клетки с наименьшей стоимостью перевозки. Это клетка (3;2) со стоимостью перевозки 0. В эту клетку можем назначить поставку в 12 ед. груза, т.к. у поставщика Х3 есть в наличии 24 ед. груза, а потребитель У2 готов принять только 12 ед. груза. Столбец 2 исключается из рассмотрения, т.к. потребности У2 удовлетворены полностью.
Следующая наименьшая стоимость 1, находится в клетках (2;3) и (4;2). Выбираем ту, в которую можно назначить максимальную поставку. Это клетка (2;3), в нее можем назначить поставку в 19 ед. груза т.к. у поставщика Х2 есть в наличии только 19 ед. груза, а потребитель У3 готов принять 30 ед. груза. Вторую строку исключаем из рассмотрения.
Следующей заполняем клетку (1;4). В нее можем назначить поставку в 10 ед. груза, т.к. у поставщика Х1 есть в наличии только 10 ед. груза, а потребитель У4 готов принять 28 ед. груза. Первую строку исключаем из рассмотрения.
Следующая наименьшая стоимость 2, находится в клетках (3;1), (4;1) и (3;3). Заполняем клетку (3;3) т.к. в нее можно назначить наибольшую поставку. В эту клетку назначаем поставку в 11 ед. груза т.к. у поставщика Х3 осталось в наличии 12 ед. груза, а потребителю У3 осталось довезти только 11 ед