Решение. Получение нового опорного плана

Получение нового опорного плана.

После того, как поставки перераспределены по контуру, получаем новый опорный план и по нему вычисляем значение целевой функции (6.6). Затем переходим к 3 этапу.

Пример 6.1. На три базы поступили ящики с заготовками деталей, которые необходимо доставить на четыре завода. Исходные данные представлены в нижеследующей транспортной таблице.

Таблица 6.3

Таблица поставок

Заводы-потребители Базы-поставщики	B1	B2	B3	B4	Запасы баз-поставщиков
A1
A2
A3
Потребности заводов-потребителей

Определите оптимальный план доставки заготовок на заводы с учетом минимизации совокупных транспортных затрат.

Обозначим искомые объемы поставок от i -ой базы-поставщика к j -му заводу-потребителю через .

Математическая модель данной задачи будет иметь вид:

I итерация:

1 этап: проверка сбалансированности запасов и потребностей.

Представленная транспортная задача является открытой, т.к. суммарная мощность баз-поставщиков меньше суммарной потребности заводов-потребителей на 200 ящиков:

,

,

.

Сведем данную транспортную задачу к закрытой: введем фиктивную базу А₄ с недостающей мощностью а₄ = 200 ящиков:

.

Зададим значения условных транспортных затрат на единицу груза от данной базы к заводам-потребителям равными нулю, результаты занесем в следующую таблицу.

Таблица 6.4

Таблица поставок

Заводы-потребители Базы-поставщики	B1	B2	B3	B4	Запасы баз-поставщиков
A1
A2
A3
A4
Потребности заводов-потребителей

С учетом фиктивного поставщика математическая модель будет иметь вид:

2 этап: разработка исходного опорного плана.

Для отыскания исходного опорного плана воспользуемся методом минимальной стоимости. Согласно таблице поставок (таблица 6.4) минимальная стоимость соответствует клеткам строки фиктивного поставщика. Рассмотрим, к примеру, клетку «4-3». Объем поставок для данной пары поставщик-потребитель составит:

Запишем в клетку «4-3» объем поставок x₄₃ =200 (таблица 6.5). Запасы фиктивного поставщика исчерпаны (зачеркиваем остальные клетки данной строки, они в дальнейших рассмотрениях не участвуют).

Таблица 6.5

Таблица поставок

Заводы-потребители Базы-поставщики	B1	B2	B3	B4	Запасы баз-поставщиков
A1
A2
A3
A4	0				200-200 = 0
Потребности заводов-потребителей			300-200 =100

Из свободных клеток минимальная стоимость соответствует клеткам «1-1» и «1-4» (c_ij =1), выберем, к примеру, клетку «1-4». Вписываем в данную клетку объем поставок x₁₄ =100 (таблица 6.6). Запасы первого поставщика исчерпаны (зачеркиваем остальные клетки данной строки, они в дальнейших рассмотрениях не участвуют).

Таблица 6.6

Таблица поставок

Заводы-потребители Базы-поставщики	B1	B2	B3	B4	Запасы баз-поставщиков
A1	1				100-100=0
A2
A3
A4
Потребности заводов-потребителей				300-100 = 200

Следующая свободная клетка с наименьшей стоимостью поставок единицы груза – клетка «2-1» (c₂₁ =2). Объем поставок для данной пары поставщик-потребитель составит:

Запишем в клетку «2-1» объем поставок x₂₁ =100 (таблица 6.7). Потребность первого завода-потребителя полностью удовлетворена (зачеркиваем незадействованную клетку данной колонки – «3-1», она в дальнейших рассмотрениях не участвуют).

Таблица 6.7

Таблица поставок

Заводы-потребители Базы-поставщики	B1	B2	B3	B4	Запасы баз-поставщиков
A1	1
A2					200-100 = 100
A3
A4
Потребности заводов-потребителей	100-100 = 0

Оставшиеся запасы второго поставщика целесообразно направить для удовлетворения потребностей второго завода-потребителя, так как стоимость доставки единицы груза здесь наименьшая (c₂₂ =3). Вписываем в соответствующую клетку объем поставок x₂₂ =100 (таблица 6.8).

Таблица 6.8

Таблица поставок

Заводы-потребители Базы-поставщики	B1	B2	B3	B4	Запасы баз-поставщиков
A1	1
A2					100-100 = 0
A3
A4
Потребности заводов-потребителей		100-100 = 0

Таким образом, потребность второго завода-потребителя полностью удовлетворена и мощность второго поставщика полностью задействована, поэтому вычеркиваем незадействованные клетки «2-3», «2-4» и «3-2», в дальнейших рассмотрениях они не участвуют.

Продолжая данные рассуждения, в результате получим следующее распределение поставок:

Таблица 6.9

Таблица поставок

Заводы-потребители Базы-поставщики	B1	B2	B3	B4	Запасы баз-поставщиков
A1	1
A2
A3
A4
Потребности заводов-потребителей

Совокупные транспортные издержки для данного плана поставок составят (усл. ден. ед.):

.

3 этап: проверка вырожденности опорного плана.

Количество задействованных клеток в таблице поставок (таблица 6.9): N =6. Ранг r системы ограничений транспортной задачи равен:

.

Так как, , следовательно, опорный план транспортной задачи вырожденный. Определим количество фиктивных поставок:

.

В любой свободной клетке таблицы поставок проектному параметру x_ij присвоим нулевое значение. Выберем, к примеру, клетку «3-2» (клетки для фиктивных поставок необходимо выбирать таким образом, чтобы в дальнейшем можно было корректно построить контур перераспределения поставок).

Таблица 6.10

Таблица поставок

Заводы-потребители Базы-поставщики	B1	B2	B3	B4	Запасы баз-поставщиков
A1
A2
A3
A4
Потребности заводов-потребителей

4 этап: расчет потенциалов.

Для первой строки принимаем α ₁=0. Рассмотрим загруженную клетку «1-4»:

.

Для загруженной клетки «3-4»: .

Аналогично последовательно находим потенциалы строк и колонок по остальным загруженным клеткам, результаты расчетов представлены в таблице 6.11.

Таблица 6.11

Таблица поставок

Потребители Поставщики	B1	B2	B3	B4	Запасы поставщиков	αi
A1
A2
A3
A4
Потребности потребителей
βj	–8	–7	–4

5 этап: проверка плана на оптимальность.

По таблице 6.11 для незагруженных клеток проверим условие оптимальности ():

«1-1»: ,

«1-2»: ,

«1-3»: ,

«2-3»: ,

«2-4»: ,

«3-1»: ,

«4-1»: ,

«4-2»: ,

«4-4»: .

Опорный план не оптимальный, так как имеются клетки, для которых условие оптимальности не выполняется: «2-3», «2-4», «4-4».

6 этап: поиск «вершины максимальной неоптимальности» (ВМН).

Для клеток «2-3», «2-4», «4-4» рассчитаем оценки: .

,

,

.

.

Выбор ВМН неоднозначен (можно выбрать любую), примем клетку «4-4» в качестве ВМН. Пометим ее в таблице поставок знаком (таблица 6.12).

Таблица 6.12

Таблица поставок

Потребители Поставщики	B1	B2	B3	B4	Запасы поставщиков	αi
A1
A2
A3
A4
Потребности потребителей
βj	–8	–7	–4

7 этап: построение контура перераспределения поставок.

Построим контур перераспределения поставок (таблица 6.13).

Таблица 6.13

Таблица поставок

Потребители Поставщики	B1	B2	B3	B4	Запасы поставщиков	αi
A1
A2
A3			7
A4
Потребности потребителей
βj	–8	–7	–4

В таблице 6.13 начиная с ВМН разделим вершины на загружаемые

и разгружаемые.

8 этап: определение минимального элемента в контуре перераспределения и перераспределение поставок по контуру.

В рамках построенного контура из клеток со статусом «разгружаемые» выберем клетку с наименьшим объемом поставок (полностью разгружаемую клетку):

.

Выбор неоднозначен, полностью разгружаем, к примеру, клетку x ₃₄ и загружаем ВМН (x ₄₄=200). Для обеспечения соответствия объемов запасов и потребностей перераспределим поставки по контуру – разгрузим клетку «4-3» на 200 ящиков (x ₄₃=0) и загрузим на этот же объем клетку «3-3» (x ₃₃=100+200=300).

9 этап: получения нового опорного плана.

В результате перераспределения поставок по контуру получим новый опорный план (таблица 6.14).

Таблица 6.14

Таблица поставок

Потребители Поставщики	B1	B2	B3	B4	Запасы поставщиков
A1
A2
A3
A4
Потребности потребителей

Совокупные транспортные издержки для данного плана поставок составят (усл. ден. ед.):

.

II итерация:

1 этап: проверка вырожденности опорного плана.

Опорный план невырожденный.

2 этап: расчет потенциалов.

Результаты расчета потенциалов приведены в таблице 6.15.

Таблица 6.15

Таблица поставок

Потребители Поставщики	B1	B2	B3	B4	Запасы поставщиков	αi
A1
A2
A3
A4						–1
Потребности потребителей
βj	–3	–2

3 этап: проверка плана на оптимальность.

«1-1»: ,

«1-2»: ,

«1-3»: ,

«2-3»: ,

«2-4»: ,

«3-1»: ,

«3-4»: ,

«4-1»: ,

«4-2»: .

Опорный план не оптимальный, так как имеются клетка «2-3», для которой условие оптимальности не выполняется.

4 этап: поиск «вершины максимальной неоптимальности» (ВМН).

Клетку «2-3» примем в качестве ВМН. Пометим ее знаком (таблица 6.16).

Таблица 6.16

Таблица поставок

Потребители Поставщики	B1	B2	B3	B4	Запасы поставщиков	αi
A1
A2
A3
A4						–1
Потребности потребителей
βj	–3	–2

5 этап: построение контура перераспределения поставок.

Построим контур перераспределения поставок (таблица 6.17).

Таблица 6.17

Таблица поставок

Потребители Поставщики	B1	B2	B3	B4	Запасы поставщиков	αi
A1
A2		3
A3
A4						–1
Потребности потребителей
βj	–3	–2

В таблице 6.17 начиная с ВМН разделим вершины на загружаемые

и разгружаемые.

6 этап: определение минимального элемента в контуре перераспределения и перераспределение поставок по контуру.

В рамках построенного контура из клеток со статусом «разгружаемые» выберем клетку с наименьшим объемом поставок (полностью разгружаемую клетку):

.

Полностью разгружаем клетку x ₂₂ и загружаем ВМН (x ₂₃=100). Для обеспечения соответствия объемов запасов и потребностей перераспределим поставки по контуру – разгрузим клетку «3-3» на 100 ящиков (x ₃₃=200) и загрузим на этот же объем клетку «3-2» (x ₃₂=100).

7 этап: получения нового опорного плана.

В результате перераспределения поставок по контуру получим новый опорный план (таблица 6.18).

Таблица 6.18

Таблица поставок

Потребители Поставщики	B1	B2	B3	B4	Запасы поставщиков
A1
A2
A3
A4
Потребности потребителей

Совокупные транспортные издержки для данного плана поставок составят (усл. ден. ед.):

.

III итерация:

1 этап: проверка вырожденности опорного плана.

Опорный план невырожденный.

2 этап: расчет потенциалов.

Результаты расчета потенциалов приведены в таблице 6.19.

Таблица 6.19

Таблица поставок

Потребители Поставщики	B1	B2	B3	B4	Запасы поставщиков	αi
A1
A2
A3
A4						–1
Потребности потребителей
βj	–1	–2

3 этап: проверка плана на оптимальность.

«1-1»: ,

«1-2»: ,

«1-3»: ,

«2-2»: ,

«2-4»: ,

«3-1»: ,

«3-4»: ,

«4-1»: ,

«4-2»: .

Опорный план не оптимальный, так как имеются клетка «3-1», для которой условие оптимальности не выполняется.

4 этап: поиск «вершины максимальной неоптимальности» (ВМН).

Клетку «3-1» примем в качестве ВМН. Пометим ее знаком (таблица 6.20).

Таблица 6.20

Таблица поставок

Потребители Поставщики	B1	B2	B3	B4	Запасы поставщиков	αi
A1
A2
A3
A4						–1
Потребности потребителей
βj	–1	–2

5 этап: построение контура перераспределения поставок.

Построим контур перераспределения поставок (таблица 6.21).

Таблица 6.21

Таблица поставок

Потребители Поставщики	B1	B2	B3	B4	Запасы поставщиков	αi
A1
A2	2
A3
A4						–1
Потребности потребителей
βj	–1	–2

В таблице 6.21 начиная с ВМН разделим вершины на загружаемые

и разгружаемые.

6 этап: определение минимального элемента в контуре перераспределения и перераспределение поставок по контуру.

В рамках построенного контура из клеток со статусом «разгружаемые» выберем клетку с наименьшим объемом поставок (полностью разгружаемую клетку):

.

Полностью разгружаем клетку x ₂₁ и загружаем ВМН (x ₃₁=100). Для обеспечения соответствия объемов запасов и потребностей перераспределим поставки по контуру – разгрузим клетку «3-3» на 100 ящиков (x ₃₃=100) и загрузим на этот же объем клетку «2-3» (x ₂₃=200).

7 этап: получения нового опорного плана.

В результате перераспределения поставок по контуру получим новый опорный план (таблица 6.22).

Таблица 6.22

Таблица поставок

Потребители Поставщики	B1	B2	B3	B4	Запасы поставщиков
A1
A2
A3
A4
Потребности потребителей

Совокупные транспортные издержки для данного плана поставок составят (усл. ден. ед.):

.

VI итерация:

1 этап: проверка вырожденности опорного плана.

Опорный план невырожденный.

2 этап: расчет потенциалов.

Результаты расчета потенциалов приведены в таблице 6.23.

Таблица 6.23

Таблица поставок

Потребители Поставщики	B1	B2	B3	B4	Запасы поставщиков	αi
A1
A2
A3
A4						–1
Потребности потребителей
βj	–3	–2

3 этап: проверка плана на оптимальность.

«1-1»: ,

«1-2»: ,

«1-3»: ,

«2-1»: ,

«2-2»: ,

«2-4»: ,

«3-4»: ,

«4-1»: ,

«4-2»: .

Найденный опорный план оптимальный, так как для всех незагруженных клеток выполняется условие оптимальности. Оптимальное решение является единственным, так как все неравенства строгие.

Ответ: оптимальное распределение поставок:

.

Данное распределение поставок обеспечит оптимальные транспортные издержки в размере 2300 усл. ден. ед.

Дата добавления: 2014-01-04