Методологический базис тпр (стр. 11 из 14)

северо-западного угла (СЗУ).

Название этого метода связано с особой разметкой транспортной таблицы: стороны таблицы называют по сторонам света (верхняя – северная, нижняя - южная), а углы соответственно помечают как промежуточные направления (левый верхний – северо-западный угол или СЗУ и т.д.)(табл.12) [2].

Составление опорного плана начинают с СЗУ таблицы – заполняют клетку А1В1 меньшим из чисел a1 и b1, т.е. х11=min{a1,b1}. От соотношения a1 и b1 зависит последовательность заполнения таблицы.

Если a1>b1, то х11=b1 – это значит, что заявка потребителя B1 удовлетворена полностью. В этом случае говорят, что столбец B1 «закрыт» и переходят к заполнению клетки A1B2(т.е. передвигаются по строке вправо, к следующему потребителю). При этом х12=min{a1-b1,b2}.

Если a1<b1, то запасы поставщика исчерпаны А1 исчерпаны (строка А1 «закрыта»), а заявка потребителя В1 удовлетворена, но не полностью. Поэтому, чтобы закончить обслуживание заявки В1, переходим к клетке А2В1(т.е. к следующему поставщику) и записываем в нее значение х21=min{a2,b1-a1} [2].

Если a1=b1,то закрываем строку А1 и строку В1, а затем переходим к клетке А2В2.

Таблица 12

Результат решения ТЗ по методу СЗУ

Пункт назначения						Запасы
В1	В2	В3	В4	В5	В6	аi
Пункт отправления	A1	8 20	1 11	5	3	7	7	31
	A2	5	8 6	8 20	4 9	2	8	35
	A3	3	1	1	1 1	1 7	1	8
	A4	4	7	6	2	9 12	3 19	31
Заявки	bi	20	17	20	10	19	19	105

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

3.2 Составление опорного плана ТЗ по методу минимума стоимостей перевозки.

Метод минимума стоимостей перевозок аналогичен методу СЗУ, только надо заполнять в первую очередь те клетки, для которых стоимости перевозок стоимости наименьшие. Если таких клеток несколько, целесообразнее сначала заполнить клетки, соответствующие наибольшим объёмам заявок. Результат решения транспортной задачи методом минимума стоимостей представлен в табл.13.

Таблица 13

Результат решения ТЗ по методу минимума стоимостей

Пункт назначения						Запасы
В1	В2	В3	В4	В5	В6	аi
Пункт отправления	A1	8	1 17	5 14	3	7	7	31
	A2	5 10	8	8 6	4	2 19	8	35
	A3	3	1	1	1 8	1	1	8
	A4	4 10	7	6	2 2	9	3 19	31
Заявки	bi	20	17	20	10	19	19	105

3.3 Сравнение планов по критерию стоимости.

Необходимо подсчитать суммарные затраты на транспортировку (значение целевой функции):

Для задач рассмотренных выше в табл. 12 и табл.13, получим:

- для плана, построенного по методу СЗУ:

WСЗУ=20*8+1*11+6*8+20*8+4*9+1*1+1*7+9*12+3*19=588;

- для плана, построенного по методу минимума стоимостей:

WМС=17*1+14*5+10*5+6*8+19*2+8*1+10*4+2*2+19*3=332;

Лучшим считается план с меньшей суммарной стоимостью перевозок.

WМС < WСЗУ.

3.4 Проверка лучшего опорного плана на оптимальность.

Для проверки плана на оптимальность можно применить метод потенциалов.

Для этого надо ввести так называемые псевдостоимости

Входящие в псевдостоимости величины и называют потенциалами. Псевдостоимости обладают следующими свойствами:

(1)

Для транспортной задачи 4х6 введём величины

соответствующие первым четырём ограничениям, и остальным ограничениям.

Согласно табл.13 запишем условия в виде:

Так как у нас восемь уравнений и десять неизвестных, то мы имеем восемь независимых переменных и две свободных – за свободные мы взяли

и и нашли величины.

Таблица 14

Проверка плана ТЗ на оптимальность и первый цикл пересчета

	2 8	1=1	5=5	0 3	-1 7	1 7
	17	14
	5=5	4 8	8=8	3 4	2=2	4 8
	10	6	19
	3 3	2 1	6 1	1=1	2 1	2 1
	8
	4=4	3 7	7 6	2=2	1 9	3=3
	10	2	19

Полученное решение не оптимально его необходимо улучшить.