Нахождение первоначального опорного плана

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

Метод северо-западного угла. Пусть условие транспортной задачи задано в следующей таблице.

Таблица 5.1

Пункты отправления	Пункты назначения	Предложение
В1	В2	В3	В4
А1	^5	^4	^2	^5
А2	^6	^1	^1	^3
А3	^2	^3	^1	^8
А4	^6	^3	^2	^1
Спрос					S250

Поскольку сумма запасов (предложения) равна сумме потребностей (спроса) – имеем задачу закрытого типа.

Матрицу перевозок начинаем заполнять с левого верхнего (северо-западного) угла, с клетки (1,1). Для этого сравниваем два значения а₁ = 30 и b₁= 20, т.е. попытаемся удовлетворить потребность первого пункта назначения за счет запасов первого пункта отправления. Запасы пункта А₁ больше потребности пункта В₁, следовательно, в качестве значения Х₁₁ выбираем меньшее число – b₁ и запишем это число в соответствующей клетке таблицы. Таким образом, потребность пункта В₁ в грузе удовлетворена, и поэтому все остальные числа этого столбца (Х₂₁, Х₃₁, Х₄₁) считаем равными нулю, а соответствующие им клетки оставляем свободными.

Получаем новую матрицу из трех столбцов (В₂, В₃, В₄) и четырех строк (А₁, А₂, А₃, А₄) и новое значение запаса у первого пункта отправления ( = 30 – 20 = 10). Далее сравниваем значения = 10 и b₂ = 90 и повторяем алгоритм. Меньшее из этих значений, равное 10, выбираем в качестве Х₁₂ и записываем в клетку (1,2) таблицы. Тогда запас пункта А₁ будет полностью исчерпан, следовательно, остальные значения перевозок из первой строки (Х₁₃, Х₁₄) принимаем равными нулю, а соответствующие клетки остаются свободными. Продолжая заполнять таблицу, таким образом дойдем до клетки (4,4). Построенный план является опорным. В рассматриваемой задаче число пунктов отправления m = 4 и число пунктов назначения n = 4, следовательно, невырожденный план задачи определяется числами, стоящими в m+n–1 = 4+4–1 = 7 заполненных клетках.

Таблица 5.2

Пункты отправления	Пункты назначения	Предложение
В1	В2	В3	В4
А1	^5 20	^4 10	^2	^5
А2	^6	^1 70	^1	^3
А3	^2	^3 10	^1 40	^8
А4	^6	^3	^2 30	^1 70
Спрос					-

Запишем первоначальный опорный план в виде матрицы Х:

Х = .

Согласно данному плану перевозок функция цели – общая стоимость перевозок всего груза - составляет

f(х) = 5 × 20 + 4 × 10 + 1 × 70 + 3 × 10 + 1 × 40 +

+ 2 × 30 + 1 × 70 = 410.

Вырожденный план. При построении опорного плана нужно следить, чтобы сумма перевозок по каждой строке была равна соответствующим запасам, а сумма перевозок по каждому столбцу – потребности. Количество заполненных клеток равно m + n – 1. Если план вырожденный, т.е. если на очередном шаге запас а_i равен потребности b_j, в этом случае необходимо считать одну из клеток (либо справа, либо под последней заполненной клеткой) базисной со значением, равным нулю. Этот нуль вписывают, и соответствующая клетка считается занятой.

Пусть условия задачи заданы следующей таблицей.

Таблица 5.3

Пункты отправления	Пункты назначения	Предложение
В1	В2	В3	В4
А1	^5 20	^4 10	^2	^5
А2	^6	^1 70	^1	^3
А3	^2	^3 0	^1 30	^8 20
А4	^6	^3	^2	^1 100
Спрос					S250

На первом шаге заполняем северо-западный угол, полагая Х₁₁ = 20, клетки (2,1), (3,1) и (4,1) остаются свободными. На втором шаге полагаем Х₁₂ = 10. Этим мы используем полностью запас пункта А₁. Остальные клетки первой строки (1,3) и (1,4) остаются свободными. На третьем шаге рассматриваем перевозку Х₂₂. Поскольку в этом случае запас пункта А₂, равный 70, совпадает с оставшейся неудовлетворенной потребностью пункта В₂, равной 70, то выбираем Х₂₂ = 70. Этим самым заполняется одновременно и вся вторая строка и весь второй столбец. В этом случае нужно считать одну из переменный Х₂₃ или Х₃₂ базисной со значением, равным нулю. Пусть Х₃₂ = 0. Проставив в соответствующей клетке базисный нуль, мы получаем при продолжении процесса заполнения таблицы m + n – 1 заполненную клетку. Если не проставить нулевую базисную переменную, окажется, что число занятых положительными перевозками клеток меньше, чем m + n – 1.

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

Этот метод позволяет найти первоначальный опорный план с меньшей стоимостью перевозок, чем план, полученный методом северо-западного угла.

Таблица 5.4

Пункты отправления	Пункты назначения	Предложение
В1	В2	В3	В4
А1	^5 10	^4	^2 20	^5
А2	^6	^1 70	^1	^3
А3	^2	^3	^1 50	^8
А4	^6 10	^3 20	^2	^1 70
Спрос					-

Порядок заполнения таблицы: находим клетки с наименьшим значением стоимости перевозки и рассмотрим величину потребности и запаса для соответствующих пунктов. Заполним клетки (2,2), (3,3), (4,4) и подсчитаем остатки неизрасходованных запасов и величины неудовлетворенной потребности. Так, запасы пункта А₂ полностью расходуются на удовлетворение потребности пункта В₂, поэтому при нахождении первоначального опорного плана клетки второй строки, кроме (2,2), должны остаться свободными. Потребности пункта В₂ остаются неудовлетворенными на 20 единиц груза, поэтому клетки второго столбца, кроме (2,2), могут быть заполнены перевозками. Аналогично рассматриваем заполнение клеток (3,3) и (4,4). Найдем свободные клетки с наименьшими стоимостями перевозок, которые могут быть заполнены, это, например, клетка (1,3) или (4,3). Заполним клетку (1,3) и подсчитаем остаток. Затем заполним клетку (4,2), на следующем шаге клетку (1,1) и, наконец, (4,1).

Значение функции цели для первоначального опорного плана

f(х) = 10 × 5 + 20 × 2 + 70 × 1 + 50 × 1 + 10 × 6 +

+ 20 × 3 + 70 × 1 = 400.

Дата добавления: 2014-12-27