Файл: Реферат по дисциплине Математическое моделирование на тему транспортная задача.docx

1.1 Определение опорного плана.

Опорный план транспортной задачи находится следующим образом. На каждом шаге в таблице условий задачи заполняется одна клетка, которая называется занятой. Обозначим через  клетку, где i-номер пункта отправления (строка),  j-номер пункта назначения (столбец). Клетку  заполняем так, чтобы удовлетворялись полностью потребности пункта назначения j, либо обеспечивался полный вывоз груза из пункта отправления i.

В первом случае временно исключаем из рассмотрения столбец j и изменяем запас груза пункта отправления i. Во втором случае временно исключаем из рассмотрения строку i и изменяем потребность груза пункта назначения j. Далее повторяем процедуру с таблицей условий с исключённой строкой или столбцом.

В  -ом шаге получаем задачу с одним пунктом отправления и одним пунктом назначения. Остаётся свободной одна клетка. Запасы оставшегося пункта отправления будут равны потребностям пункта назначения. Заполнив эту клетку заканчиваем  -ый шаг и получаем опорный план.

Если на некотором шаге (но не на последнем) потребности очередного пункта назначения равны запасам пункта отправления, то временно исключаем из рассмотрения либо столбец, либо строку (только одно из двух). Тогда либо запасы данного пункта отправления, либо потребности данного пункта назначения считаем равным нулю. Этот нуль при очередном шаге записываем в очередную заполняемую клетку. Данный подход обеспечивает ровно  занятых клеток, что обеспечивает возможность проверки полученного опорного плана на оптимальность и нахождение оптимального плана.

Глава 2. Методы решения транспортной задачи.

2.1 Метод северо-западного угла

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

---

При нахождении опорного плана транспортной задачи методом северо-западного угла, заполнение клеток таблицы условий начинают с верхней левой клетки K₁₁ поэтому метод и называется "метод северо-западного угла". Рассмотрим метод на конкретном примере.

Пример 1. На три базы A₁, A₂, A₃ поступил очередной груз в количествах равных 140, 160, 120 ед. Этот груз требуется перевезти в четыре пунктов назначения B₁, B₂, B₃, B₄ в количествах 150, 90, 100, 80. Тарифы перевозок представлены матрицей



Найти план перевозок данной транспортной задачи методом северо-западного угла.

Решение. Запишем все данные в таблицу условий:

Пункты отправления	Пункты назначения				Запасы
	B1	B2	B3	B4
A1	2	3	4	2	140
A2	8	4	1	4	160
A3	9	7	3	6	120
Потребности	150	90	100	80	0

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

---

Общая потребность в грузе в пунктах назначения равна:

Модель транспортной задачи является закрытой. Следовательно, она разрешима.

Найдём опорный план задачи методом северо-западного угла. . Следовательно в клетку (A₁, B₁) помещаем число Запасы пункта A₁ полностью исчерпаны. Поэтому, исключаем из рассмотрения строку A₁ и будем считать потребности пункта B₁ равными

Пункты отправления	Пункты назначения				Запасы
	B1	B2	B3	B4
A1	2 140	3	4	2	0 [ 140 ]
A2	8	4	1	4	160 [ 160 ]
A3	9	7	3	6	120 [ 120 ]
Потребности	10 [ 150 ]	90 [ 90 ]	100 [ 100 ]	80 [ 80 ]	420

. Следовательно, в клетку ( , ) помещаем число . Потребности пункта

---

полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B₁ и будем считать запасы пункта равными .

Пункты отправления	Пункты назначения				Запасы
	B1	B2	B3	B4
A1	2 140	3	4	2		0 [ 140 ]
A2	8 10	4	1	4		150 [ 160 ]
A3	9	7	3	6		120 [ 120 ]
Потребности	0 [ 150 ]	90 [ 90 ]	100 [ 100 ]	80 [ 80 ]		420

Таким образом, продолжая процедуру в -ом шаге получим:

Пункты отправления	Пункты назначения				Запасы
	B1	B2	B3	B4
A1	2 140	3	4	2		0 [ 140 ]
A2	8 10	4 90	1 60	4		0 [ 160 ]
A3	9	7	3 40	6 80		0 [ 120 ]
Потребности	0 [ 150 ]	0 [ 90 ]	0 [ 100 ]	0 [ 80 ]		420

---

Запишем полученный опорный план:



При этом плане стоимость перевозок вычисляется так: .

---