Транспортная задача и ее решение методом потенциалов

Размещено на http://www.allbest.ru/

Транспортная задача и ее решение методом потенциалов

Транспортная задача (Т.З.) является одной из распространенных задач линейного программирования специального вида. Эта задача такого наиболее рационального прикрепления пунктов отправления грузов (поставщиков) к пунктам их назначения (потребителям), чтобы общая стоимость транспортировки грузов была минимальной. Первая строгая постановка задачи была дана Хичкоком, а точный универсальный метод ее решения разработан советскими учеными Л.В. Конторовичем и М.К. Гавуриным.

§1.1 Постановка задачи и ее математическая модель

Пусть в пунктах A1, A2, ..., Am производят некоторый однородный продукт в количествах a1, a2, …, am соответственно. Этот продукт следует перевезти в пункты B1, B2, ..., Bn, потребляющие его соответственно в количествах b1, b2, ..., bn..

Пункты Ai () называются пунктами отправления или поставщиками, а пункты Bj () - пунктами назначения или потребителями. Рассмотрим сначала случай, когда суммарный объем производства равен суммарному объему потребления, т.е.

Предположим, что из каждого пункта производства возможна транспортировка продукта в любой пункт потребления. Транспортные издержки по перевозке из пункта Ai в пункт Bj единицы продукции равны cij (,). Значения cij будем называть тарифами. Пусть xij - количество продукта, перевозимого из пункта Ai в пункт Bj. Переменные xij будем называть перевозками.

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

Условия T.З. удобно записывать в таблице следующего вида:

Таблица 1.1

Потребители	B1	B2	…	Bj	…	Bn
Постав- щики	bj ai	b1	b2	…	bj	…	bn
A1	a1	c11 x11	c12 x12	…	c1j x1j	…	c1n x1n
A2	a2	c21 x21	c22 x22	…	c2j x2j	…	c2n x2n
…	…	…	…	…	…	…	…
Ai	ai	ci1 xi1	ci2 xi2	…	cij xij	…	cin xin
…	…	…	…	…	…	…
Am	am	cm1 xm1	cm2 xm2	…	cmj xmj	…	cmn xmn

В таблице 1.1 каждая клетка (i, j), соответствующая паре i-й поставщик - j-й потребитель, условно делится диагональю пополам и в правом верхнем углу записывается значение тарифа cij, а в левом нижнем - значение перевозки xij.

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

xij ? 0, ;

Z = c11x11 + c12x12 + … + c1nx1n + c21x21 + c22x22 + … + c2nx2n + … + cm1xm1 + cm2xm2 + … + cmnxmn > min.

С помощью индексов суммирования эта модель запишется так:

xij ? 0, ; (1.1)

(1.2)

> min. (1.3)

Условия (1.1) - условия неотрицательности перевозок (обратная транспортировка груза от потребителя к поставщикам запрещена).

Условия (1.2а) характеризируют полный вывоз продукта от поставщиков, а условия (1.2б) - полное удовлетворение запросов потребителей.

Суммарная стоимость Z транспортировки продукта согласно условию (1.3) должна быть минимальной.

Совокупность переменных xij, удовлетворяющих условиям (1.1) и (1.2), будем называть планом перевозок T.З. и записывать его в виде матрицы:

.

Совокупность тарифов сij будем записывать в виде матрицы, которую назовем матрицей тарифов:

.

Запишем систему ограничений T.З. в векторной форме. Обозначим столбец коэффициентов при xij через , а столбец сводных членов - через , тогда:

У вектора i-я и (m + j)-я компоненты равны единице, остальные компоненты равны нулю.

Система ограничений (1.2) T.З. в векторной форме будет иметь вид:

(1.4)

§1.2 Условие разрешимости транспортной задачи

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

(1.5)

Доказательство:

Необходимость. Пусть транспортная задача разрешима, т.е. система ограничений (1.1) - (1.2) задачи совместна, тогда существуют значения xij (; ), удовлетворяющие этим условиям. Необходимо доказать, что

.

Просуммировав условия (1.2а) по i, а условия (1.2б) - по j, получим:

и .

Т.к. левые стороны этих выражений равны, то равны и правые, т.е. , что и требовалось доказать.

Достаточность. Пусть. Необходимо доказать, что существуют значения xij (; ), удовлетворяющие условиям (1.1) - (1.2). Положим

, ;

и покажем, что является планом T.З.

Действительно,

;

Очевидно также, что

> 0.

Таким образом, условия (1.1) - (1.2) удовлетворяются. Достаточность условий (1.5) доказана.

§1.3 Особенности ограничений транспортной задачи

T.З. является задачей линейного программирования, и ее можно решить симплексным методом. Однако специфика ограничений T.З. позволяет применять для ее решения методы значительно менее громоздкие, чем симплексный метод. Один из них - метод потенциалов.

Особенности ограничений T.З. следующие:

а) ограничения заданы в виде уравнений;

б) каждая переменная xij встречается только в двух уравнениях;

в) коэффициенты при неизвестных, входящих в уравнение, равны единице (или нулю, если переменные не входят в уравнение).

Рассмотрим систему уравнений (1.2). Она содержит (m + n) уравнений с m · n неизвестными. Сложив почленно уравнения отдельно системы (1.2а) и отдельно - системы (1.2б), мы получим два одинаковых уравнения:

> 0;

> 0.

Это говорит о том, что система уравнений (1.2) Т.З. линейно зависима и, по крайней мере, одно из уравнений лишнее. Следовательно, максимальное число линейно независимых уравнений системы (1.2), т.е. ранг r системы, не более, чем (m + n - 1).

Можно показать, что ранг r в точности равен (m + n - 1), т.е. система ограничений T.З. содержит ровно (m + n - 1) линейно независимых уравнений. Это означает, что если систему уравнений (1.2) решить методом Жордана-Гаусса, то число базисных переменных будет равно (m + n - 1).

Одним из методов решения T.З., который учитывает специфику ее ограничений, является метод потенциалов. По существу, его можно рассматривать, как результат реализации симплексного метода в условиях транспортной задачи (1.1)-(1.3).

Метод потенциалов состоит из трех шагов.

Первый шаг - отыскание исходного опорного плана перевозок T.З..

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

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

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

§1.4 Методы отыскания исходного опорного плана перевозок транспортной задачи (первый шаг метода)

Ранг системы ограничений T.З. равен (m + n - 1), следовательно, невырожденный опорный план Т-задачи содержит (m + n - 1) положительных компонент или перевозок (соответствующих базисным переменным). Остальные компоненты этого плана (соответствующие свободным переменным) равны нулю. Допустим, что исходный невырожденный опорный план T.З. найден.

Запишем условия задачи и этот план в табл. 1.1, при этом значения перевозок, равные нулю, писать не будем. Клетки таблицы, соответствующие отличным от нуля перевозкам, будем называть занятыми или базисными, а остальные клетки - свободными или незанятыми. Число базисных (занятых) клеток равно (m + n - 1). Исходный опорный план T.З. можно находить с помощью различных методов. Рассмотрим один из них, так называемый метод «северо-западного угла».

Условимся задавать условия T.З. таблицей 1.2.

Таблица 1.2

bj ai	b1	b2	…	bn
a1	c11 x11	c12 x12	…	c1n x1n
a2	c21 x21	c22 x22	…	c2n x2n
…	…	…	…	…
am	cm1 xm1	cm2 xm2	…	cmn xmn

Строки таблицы условимся нумеровать сверху вниз в следующем порядке: 0-я, 1-я, 2-я, ..., m-я; а столбцы - слева направо: 0-й, 1-й, 2-й, …, n-й.

Каждая клетка (i, j) табл. 1.2 соответствует паре i-й поставщик - j-й потребитель для i = ; j = .

Нахождение значений xij начинаем с определения перевозки x11, т.е. с заполнения «северо-западной» клетки (1,1).

Полагаем x11 = min (a1, b1).

Если a1 < b1, то x11 = a1, первый поставщик вывозит весь свой груз (свою продукцию). Значение x11 = a1 заносим в клетку (1,1), а в остальных клетках первой строки ставим прочерки (-). Первую строку - поставщика - временно из рассмотрения исключаем, а первый столбец - потребителя - оставляем с потребностью:

= b1 - a1.

Если a1 > b1, то x11 = b1, потребности первого потребителя полностью удовлетворены, поэтому в клетку (1, 1) заносим значение x11 = b1, а в остальных клетках первого столбца ставим прочерк. Первый столбец - потребителя - временно из рассмотрения исключаем, а первую строку - поставщика - оставляем с запасом груза (продукции) = a1 - b1.

Если a1 = b1, то из рассмотрения надо исключить что-то одно: или строку, или столбец. Условимся исключать в таких случаях строку - поставщика, а столбец - потребителя - оставлять с потребностью, равной нулю: = 0.

Определив x11, получим новую таблицу, в которой на одну строку или на один столбец меньше, чем в исходной. Найдем в этой новой таблице «северо-западную» клетку и заполним ее аналогично тому, как заполняли клетку (1, 1).

Например, если из рассмотрения исключена строка, то очередной «северо-западной» клеткой будет (2, 1), и полагаем x21 = min (a2, ) и т.д. Можно показать, что метод «северо-западного» угла всегда приводит к опорному решению.

Рассмотрим метод «северо-западного» угла на примерах.

Пример 1.1. На трех станциях A1, A2, A3 находятся удобрения, которые следует отправить в четыре фермерских хозяйства B1, B2, B3, B4.

Потребности фермерских хозяйств, запасы удобрений (т) и стоимости перевозок 1 т (у.е.) записаны в таблице 1.3.

Таблица 1.3.

bj ai	300	500	100	200
100	3 x11	6 x12	5 x13	1 x14
400	1 x21	4 x22	3 x23	2 x24
600	4 x31	3 x32	1 x33	2 x34

Составить план перевозок, который обеспечит минимум суммарных затрат на транспортировку удобрений.

Строки таблицы 1.3 условимся нумеровать сверху вниз и в следующем порядке: 0-я, 1-я, 2-я, 3-я, а столбцы - слева направо: 0-й, 1-й, 2-й, 3-й, 4-й.

Проверим выполнение условия разрешимости T.З.:

,

.

.

Условие выполняется.

Математическая модель задачи:

Найдем исходный опорный план методом «северо-западного» угла. Заполнение клеток таблицы начинается с определения перевозки x11, т.е. с левого верхнего («северо-западного») угла.

Полагаем x11 = min (a1, b1) = min (100, 300) = 100.

Значение x11 = 100 заносим в клетку (1, 1) таблицы 1.4, и, поскольку весь груз от первого поставщика вывезен, то в остальных клетках первой строки ставим прочерки (соответствующие перевозки равны нулю). Временно из рассмотрения первую строку исключаем, а первый столбец оставляем с потребностью = 300 - 100 = 200.

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

Полагаем: x21 = min (a2, ) = min (400, 200) = 200.

Заносим значение x21 = 200 в таблицу 1.4, и, поскольку первый потребитель полностью удовлетворен, в клетке (3, 1) ставим прочерк. Первый столбец из рассмотрения исключаем, а вторую строку оставляем с запасом = 400 - 200 = 200.

Далее, полагаем x22 = min (, b2) = min (200, 500) = 200.

Заносим x22 = 200 в таблицу 1.4, ставим прочерки в клетках (2, 3) и (2, 4), исключаем из рассмотрения вторую строку, а второй столбец оставляем с потребностью = 500 - 200 = 300.

Остальные клетки таблицы 1.4 заполняем аналогично:

x32 = min (a3, ) = min (600, 300) = 300; = 600 - 300 = 300;

x33 = min (, b3) = min (300, 100) = 100; = 300 - 100 = 200;

x34 = min (, b4) = min (200, 200) = 200.

Таблица 1.4

	bj ai	300	500	100	200
	100	3 100	6 Ї	5 Ї	1 Ї
	400	1 200	4 200	3 Ї	2 Ї
	600	4 Ї	3 300	1 100	2 200

Выписываем исходный план перевозок T.З.:

.

Суммарная стоимость его транспортировки

Z(X1) = 3•100 + 1•200 + 4•200 + 3•300 + 1•100 + 2•200 = 2700 у.е.

План X1 является опорным, переменные x11, x21, x22, x32, x33, x34 - базисные, соответствующие им клетки в таблице 1.4 - базисные, остальные переменные (клетки) - небазисные (свободные).

Опорный план является невырожденным, так как значения всех базисных переменных - перевозок - в базисных клетках отличны от нуля. Число базисных клеток в таблице 1.4: m + n - 1 = 3 + 4 - 1 = 6.

Если при отыскании исходного опорного решения методом «северо-западного» угла хотя бы в одну из клеток будет записано нулевое значение перевозки, то найденное опорное решение будет вырожденным.

Ниже приводится T.З., для которой исходный опорный план, найденный методом «северо-западного» угла, является вырожденным.

Пример 1.2. Условия задачи и найденный план записаны в таблице 1.5.

Таблица 1.5

bj ai	30	20	50
	30	5 30	1	4
	70	3 0	2 20	10 50

Полагаем x11 = min (a1, b1) = min (30, 30) = 30.

Весь груз от первого поставщика полностью вывозится и запрос первого потребителя полностью удовлетворен. Однако исключить из рассмотрения одновременно и строку, и столбец нельзя. Исключим первую строку, а первый столбец оставим с потребностью = 0. На следующем шаге «северо-западной» будет клетка (2, 1).

Полагаем x21 = min (a2, ) = min(70, 0) = 0.

Аналогично найдем значения x22 = 20, x23 = 50. Найденный план

является вырожденным, так как базисная переменная x21 = 0 - это так называемый базисный нуль. Число базисных клеток: m + n - 1 = 2 + 3 - 1 = 4.

§1.5 Условия оптимальности плана перевозок транспортной задачи.

Признак оптимальности плана перевозок T.З. устанавливает теорема.

Теорема. Для того, чтобы некоторый допустимый план X = (xij)m•nT.З. был оптимальным, необходимо и достаточно, чтобы ему соответствовала система из (m + n) чисел U1, U2, …, Um ; V1, V2, …Vn, удовлетворяющих условиям:

Числа Ui и Vj называются соответственно потенциалами пунктов отправления и пунктов назначения или потенциалами поставщиков и потребителей. А условия (1.6), (1.7) условиями оптимальности или потенциальности плана перевозок T.З..

Доказательство.

T.З., т.е. задачу нахождения минимума функции Z:

xij ? 0, ; (1.1)

(1.2)

> min. (1.3)

можно рассматривать как двойственную задачу к некоторой исходной прямой задаче линейного программирования (з.л.п.), условия которой легко получить по правилам построения двойственных задач. [ ]

Каждому ограничению-равенству вида соответствует в прямой задаче свободная переменная Ui ёа каждому ограничению-равенству вида соответствует в прямой задаче свободная переменная Vj .

Каждой несвободной переменной xij ? 0, ; соответствует в прямой задаче ограничение-неравенство

Ui + Vj ? cij , ; (1.8)

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

(1.9)

Задача (1.8), (1.9) в свою очередь является двойственной к T.З.. Теперь используя 1-ю и 2-ю теоремы двойственности докажем сформулированную теорему.

Необходимость. Пусть X = (xij) - оптимальный план T.З.. Поскольку оптимальный план является всегда допустимым, следовательно, он удовлетворяет условиям (1.1) и (1.2) T.З., т.е.

xij ? 0, ; ;

Согласно 1-й теореме двойственности прямая задача (1.8), (1.9) также имеет оптимальное решение U1, U2, …, Um; V1, V2, …Vn; удовлетворяющее условиям (1.8), т.е. Ui + Vj ? cij , ; и следовательно, условия (1.7) выполняются. По 2-й теореме двойственности оптимальные решения обеих задач удовлетворяют условиям дополняющей нежесткости:

xij (Ui + Vj - cij) = 0.( ; )

Отсюда следует, что для xij > 0, Ui + Vj - cij = 0 или Ui + Vj = cij т.е. условия (1.6) выполняются.

Вторая группа условий

,

выполняется автоматически, в силу условий (1.2).

Достаточность. Пусть для некоторого допустимого плана существует система чисел ; , удовлетворяющая условиям (1.6), (1.7). Выполнение этих условий означает, что эта система чисел является допустимым решением прямой задачи (1.8), (1.9) (условия (1.8) при этом будут выполняться). Выполнение условий (1.7) означает, что допустимое решение U1, U2, …, Um; V1, V2, …Vn прямой задачи и допустимый план двойственной задачи (T.З.) удовлетворяют условиям дополняющей нежесткости:

xij (Ui + Vj - cij) = 0

(вторая группа условий; выполняется автоматически).

По 2-й теореме двойственности допустимый план является оптимальным. Теорема доказана.

Рассмотрим связь условий оптимальности (1.6) и (1.7) плана перевозок транспортной задачи с критерием оптимальности решения в симплексном методе.

Решим T.З. симплексным методом, одновременно найдем и оптимальное решение U1, U2, …, Um; V1, V2, …Vn задачи (1.8), (1.9). Вычислим оценки ?ij векторов :

?ij =Ui + Vj - cij, ; .

Транспортная задача является задачей на минимум и поэтому в симплекс-методе, критерий оптимальности решения для з.л.п. на минимум формируется так: если для данного опорного решения все оценки неположительны, то это опорное решение оптимально. Поэтому и для T.З. решение оптимально, если все оценки ?ij ? 0. При этом для всех базисных векторов :

?ij =Ui + Vj - cij,

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

xij: Ui + Vj = cij

т.е. получим условие (1.6).

Для небазисных векторов : ?ij =Ui + Vj - cij ? 0, т.е. для небазисных переменных xij:

Ui + Vj ? cij

т.е. получили условие (1.7).

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

- для каждой базисной клетки (i, j) сумма потенциалов должна быть равна соответствующему тарифу Cij: Ui + Vj = cij;

Если опорный план является вырожденным и какая-то из базисных переменных равна нулю, то для клетки, соответствующей этой переменной тоже должно выполняться условие Ui + Vj = cij;

- для каждой свободной клетки (i, j) сумма потенциалов должна быть меньше либо равна Cij: Ui + Vj ? cij или

Дij = Ui + Vj - cij ? 0.

Значения Дij являются оценками соответствующих свободных переменных xij; будем называть их оценками свободных клеток (i,j).

Для базисных клеток оценки Дij = Ui + Vj - cij = 0.

Вывод. Поскольку T.З. является задачей линейного программирования (з.л.п.) на минимум, то критерий оптимальности решения здесь формулируется так: если для данного опорного решения все оценки неположительны, то это решение оптимально. Если хотя бы одна из свободных клеток имеет положительную оценку, то опорный план оптимальным не является, и его можно улучшить, вводя в базис свободную переменную, соответствующую этой клетке.

§1.6 Исследование найденного опорного плана на оптимальность (2-й шаг метода)

транспортная задача оптимальность

Поставим в соответствие поставщикам потенциалы Ui, , а потребителям - Vj, . В оптимальном плане для всех базисных клеток должны выполняться условия: Ui + Vj = cij .

Очевидно, таких уравнений можно составить столько, сколько в таблице базисных переменных (клеток), т.е.: m + n - 1. Полученная система уравнений будет содержать: m + n неизвестных: Ui, i = ; Vj, . Решая эту систему уравнений, одну из переменных (любую) будем считать свободной. Условимся для определенности всегда считать свободной переменную U1. Положив U1 = 0, из этой системы уравнений определяем значения остальных неизвестных Ui и Vj.

Затем проверяем выполнение условий (1.7). Если найденный опорный план является оптимальным, то для всех свободных клеток должны выполняться условия Дij = Ui + Vj - cij ? 0, т.е. оценки свободных клеток неположительны.

Если условия выполняются, то найденный план оптимальный, если нет, - переходим к 3-му шагу метода потенциалов.

Вернемся к задаче об удобрениях. Исходный опорный план X1, найденный в табл.1.4, методом «северо-западного» угла, перепишем в табл.1.6. Поставим в соответствие поставщикам потенциалы Ui, а потребителям - Vj и добавим к табл.1.6 еще один столбец и одну строку, в которые будем записывать найденные позже значения потенциалов Ui и Vj.

Таблица 1.6

bj ai	300	500	100	200	Ui
100	3 100	6 Ї	5 Ї	1 Ї	U1= 0
400	1 200	4 200	3 Ї	2 Ї	U2 = -2
600	4 Ї	3 300	1 100	2 200	U3 = -3
Vj	V1 = 3	V2 = 6	V3 = 4	V4 = 5

Проверим, является ли план X1 оптимальным.

Составим для всех базисных клеток таблицы систему уравнений:

Ui + Vj = cij.

Получим:

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

Затем проверяем выполнение условий оптимальности (1.7) для свободных клеток.

Вычисляем значения оценок Дij = Ui + Vj - cij:

Д12 = U1 + V2 - c12 = 0 + 6 - 6 = 0;

Д13 = U1 + V3 - c13 = 0 + 4 - 5 = -1 < 0;

Д14 = U1 + V4 - c14 = 0 + 5 - 1 = 4 > 0;

Д23 = U2 + V3 - c23 = -2 + 4 - 3=-1 < 0;

Д24 = U2 + V4 - c24 = -2 + 5 - 2 =1 > 0;

Д31 = U3 + V1 - c31 = -3 + 3 - 4= -4 < 0.

Опорный план X1 оптимальным не является, условия оптимальности нарушаются для клеток (1,4) и (2,4). Следует перейти к следующему опорному решению, которому будет соответствовать меньшее значение целевой функции. На этом 2-й шаг окончен, и надо переходить к 3-му шагу.

§1.7 Определение нового, улучшенного опорного решения транспортной задачи (3-й шаг метода)

Специфика транспортной задачи позволяет находить новое опорное решение задачи и новый базис по правилу более простому, чем в симплекс-методе. Пусть найденное опорное решение является невырожденным и пусть для клетки (i0, j0) условие оптимальности нарушено и - одна из положительных оценок (например, наибольшая). Согласно теореме об улучшении опорного решения, мы получим лучшее опорное решение, если вектор введем в базис (в вырожденном случае может появиться прежнее решение). Тогда клетка (i0, j0) станет базисной. Обозначим объем перевозок по маршруту (i0, j0) в новом решении через Q > 0. В клетку (i0, j0) запишем значение перевозки . Теперь суммарный объем перевозок из i0-го пункта стал равен , что невозможно по условиям задачи т.к. нарушен баланс в строке i0 и в столбце j0. Чтобы восстановить баланс в строке i0 перевозку Q надо компенсировать, т.е. надо уменьшить на Q суммарный объем старых базисных перевозок в этой строке. Условимся восстанавливать баланс только за счет уменьшения одной базисной перевозки в строке i0. Пусть, например, мы уменьшаем на Q базисную перевозку, записанную в клетке (i0, j1), в эту клетку запишем «- Q ». Но теперь потребитель j1 получает груз на Q единиц меньше, чем ему требуется, т.е. нарушается баланс по столбцу j1. Чтобы его восстановить, надо увеличить на Q суммарный объем перевозок в этом столбце. Компенсируем это уменьшение за счет увеличения на Q одной только базисной перевозки в столбце j1. Пусть, например, мы увеличиваем на Q перевозку , в клетку (i1, j1) запишем «+ Q ». Тогда, поскольку, нарушается баланс по строке i1, необходимо компенсировать это увеличение за счет уменьшения на Q объема одной базисной перевозки в строке i1. Продолжаем этот процесс баланса по строкам и столбцам до тех пор, пока не восстановим баланс в столбце j0, за счет уменьшения одной базисной перевозки в этом столбце на величину Q. Последовательность клеток (i0, j0), (i0, j1), (i1, j1), … должна замкнуться на клетке (i0, j0). Будем называть эту цепочку клеток циклом пересчета свободной клетки (i0, j0). Соединяя отрезками прямой последовательные клетки цепочки, мы получим замкнутую ломаную линию, которую также будем называть циклом пересчета. Можно доказать, что если задан некоторый опорный план T.З., то для любой свободной клетки можно построить единственный цикл пересчета. Назовем клетки цепочки, в которые мы записываем «- Q » отрицательными, а в которые «+ Q » - положительными. Определим Q. Будем исходить из того, что значение Q надо взять как можно больше (как в симплекс-методе). Рассмотрим отрицательные клетки. Значение перевозок в таких клетках будет равно xijбаз - Q ? 0. Отсюда следует, что Q надо положить равным наименьшей из перевозок, записанных в отрицательных клетках. Новый опорный план T.З. определяем, увеличивая на Q перевозки, записанные в положительных клетках и уменьшая на Q перевозки, записанные в отрицательных. Клетка (i0, j0), для которой составлен цикл пересчета, становиться базисной. Очевидно, что при этом, по крайней мере, одна из старых базисных перевозок обращается в нулевую, соответствующий ей вектор выводится из базиса и соответствующая клетка становиться свободной.

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

В случае улучшения вырожденного опорного плана при построении цикла пересчета может оказаться, что в клетку с базисным нулем будет записано «- Q ». В этом случае значение Q = 0 и новый опорный план, который получим после пересчета не меняется, но меняется состав базисных клеток (переменных); отрицательная клетка с базисным нулем станет свободной, а в клетку, для которой составляли цикл перерасчета, запишем базисной ноль. Вероятность зацикливания в T.З. чрезвычайно мала, поэтому правило предупреждения зацикливания не рассматривается. Переход от одного опорного решения к другому, лучшему в методе потенциалов по существу происходит по правилам симплексного метода. Действительно, в базис вводится вектор , по правилам симплекс-метода (для задачи на минимум). Значение новой базисной переменной , где Q равно минимальному из значений перевозок (базисных переменных), записанных в отрицательных клетках:

(xijбаз из отрицательных клеток) =Q. (1.10)

При решении общей з.л.п. симплекс-методом [] значение новой базисной переменной xs (т.е. значение Q) определяется по формуле:

(1.11)

При решении T.З. симплекс-методом формула (1.11) будет иметь вид:

( xijбаз/) =Q.

Поскольку в T.З. положительные значения коэффициентов , то легко видно, что последняя формула совпадает с формулой (1.10). Таким образом, формула (1.10) является частным случаем формулы (1.11), т.е. последняя применительно к T.З. превращается в формулу (1.10).

Рассмотрим переход к новому опорному решению (3-й шаг метода) в задаче об удобрениях. В табл. 1.7 записано исходное опорное решение, которое следует улучшить. Среди клеток, для которых нарушаются условия оптимальности (1.7), выбираем клетку (1,4) с наибольшей оценкой Д14 = 4 >0. Соответствующую переменную x14 введем в базис, и клетку (1,4) сделаем базисной. Обозначим новый объем перевозок через x14 = Q > 0 и в клетку (1,4) табл. (1.7) запишем «+Q», т.е. перевозку x14 увеличим на «Q». Однако теперь от 1-го поставщика вывозится (100+Q) т. груза, что не возможно по условию задачи. Нарушился баланс в 1-й строке таблицы, одновременно он нарушился и в 4-ом столбце, так как теперь 4-й потребитель получает (200 + Q) т. груза.

Восстановим баланс сначала в т 1-й строке за счет одной базисной клетки и в клетку (1,1) запишем «-Q». т.е. перевозку x11 уменьшаем на Q. Теперь нарушен баланс в 1-ом столбце, восстановим его за счет одной базисной клетки (2,1), в которой запишем «+Q». Далее восстановим нарушенный баланс во 2-ой строке, записав «-Q» в клетку (2,2) и затем во 2-ом столбце, записав «+Q» в клетку (3,2). Затем одновременно восстановим нарушенный баланс в 3-й строке и в 4-ом столбце, записав «-Q» в клетку (3,4). Теперь баланс полностью восстановлен. В результате этих действий получим цепочку клеток (1,4); (1,1); (2,1); (2,2); (3,2); (3,4), которая называется циклом пересчета свободной клетки (1,4). Клетки этой цепочки называются вершинами цикла. Соединим эти клетки отрезками прямых, как показано в табл. 1.7, полученную замкнутую ломаную линию тоже будем называть циклом пересчета. Клетки (вершины) цикла, в которых записано «-Q» будем называть отрицательными, а в которых записано «+Q» - положительными.

При решении конкретных задач могут встретится различные формы циклов (рис.1.1).

Особенности цикла:

а) цикл единственный, замкнутый;

б) исходная клетка цикла - свободная её оценка Дij > 0, остальные - базисные;

в) если в строке (столбце) таблицы есть положительная (отрицательная) клетка, то в строке (столбце) должна быть отрицательная (положительная) клетка.

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

Размещено на http://www.allbest.ru/

Для этого приравниваем Q минимальной из перевозок, записанных в отрицательных клетках табл. 1.7. Отрицательными будут клетки (1,1), (2,2), (3,4), в них записаны перевозки: 100, 200 и 200 соответственно, следовательно,

Q = min(100, 200, 200) = 100.

Теперь пересчитаем план перевозок. Перевозки в положительных клетках увеличиваем на 100, в отрицательных - уменьшаем на 100. Клетку (1,1), в которой перевозка обращается в ноль, будем считать свободной, а клетка (1,4) станет базисной. Все остальные клетки таблицы оставляем без изменения. Новый план X2 получим в табл.1.8.

Число базисных клеток: m + n - 1 = 6. Покажем, что новый план лучше предыдущего и вычислим величину изменения целевой функции ?Z. Рассмотрим оценку

?14 = U1 + V4 - c14 .

Перемещая груз Q по циклу, мы изменяем величину целевой функции на следующую величину:

?Z = С14 · Q - c11 · Q + c21 · Q - c22 · Q + c32 · Q - c34 · Q =

= (c14 - c11 + c21 - c22 + c32 - c34 ) · Q . (1.12)

Запишем условия (1.6) для всех клеток цикла пересчета, кроме (1.4), получим:

U1 + V1 = c11

U2 + V1 = c21

U2 + V2 = c22

U3 + V2 = c32

U3 + V4 = c34

Первое, третье и пятое уравнение умножим на « - 1» и затем сложим со вторым и четвертым уравнениями, получим:

- U1 - V4 = - c11 + c21 - c22 + c32 - c34 (1.13)

Подставим (1.13) в (1.12), получим:

?Z = (c14 - U1 - V4) · Q.

Учитывая, что: ?14 = U1 + V4 - c14 , получим «- ?14 = - U1 - V4 + c14 » и тогда

?Z = - ?14 · Q . (1.14)

Так как ?14 > 0, Q > 0, то ?Z = - ?14 · Q < 0 и значение целевой функции уменьшается.

Таблица 1.8

bj ai	300	500	100	200	Ui
100	3 Ї	6 Ї	5 Ї	1 100	U1= 0
400	1 300	4 100	3 Ї	2 Ї	U2 = 2
600	4 Ї	3 400	1 100	2 100	U3 = 1
Vj	V1 = -1	V2 = 2	V3 = 0	V4 = 1

Из таблицы 1.8 выписываем новый план перевозок:

со стоимостью транспортировки:

Z(X2) = 1•100 + 1•300 + 4•100 + 3•400 + 1•100 + 2•200 = 2300 у.е.

Z(X2) = 2300 < Z(X1) = 2700.

Стоимость транспортировки уменьшилось на величину

ДZ = Z(X1) - Z(X2) = 2700 - 2300 = 400.

Для контроля вычислений величину ДZ можно вычислить по формуле

ДZ = Q •Д14, где Д14 = 4, а Q = 100.

Действительно, ДZ = 100•4 = 400, результат совпадает со значением ДZ, найденным выше, значит, вычисления проведены верно.

Новый опорный план X2 проверяем на оптимальность аналогично тому, как это делалось для плана X1, т.е. для плана X2 выполняем 2-й шаг метода. Для всех базисных клеток табл. 1.8 записываем систему уравнений:

Полагаем U1 = 0 и находим остальное значение потенциалов.

Запишем их в последних строке и столбце табл.1.8. Затем вычисляем значения оценок Дij для свободных оценок:

Д11 = -4 < 0,

Д12 = -4 < 0,

Д13 = -5 < 0,

Д23 = -1 < 0,

Д24 = 1 > 0,

Д31 = -4 < 0.

План X2 не оптимален, так как условия оптимальности нарушены для клетки (2,4). Клетку (2,4) будем считать базисной, и составим для нее цикл пересчета. Выполним это в табл.1.9.

Отрицательными являются клетки (2,2) и (3,4), в них записаны перевозки x22 = x34 = 100.

Вычисляем Q:

Q = min(100;100) = 100.

Аналогично тому, как это было сделано выше, пересчитаем план перевозок, перевозки в отрицательных клетках уменьшаем на Q = 100, а в положительных - увеличиваем на Q = 100.

Нулевые значения перевозок получают в клетках (2,2) и (3,4), поэтому одну из них, например, (2,2), будем считать свободной, а (3,4) - базисной, и запишем в нее базисный ноль, так как клетка (2,4) становится базисной и только одна из отрицательных клеток должна быть свободной. Число базисных клеток для нового плана X3 должно быть равно: m + n - 1 = 6.

В результате этих действий получаем новый план X3, записанный в табл. 1.10.

Таблица 1.10

bj ai	300	500	100	200	Ui
100	3 Ї	6 Ї	5 Ї	1 100	U1= 0
400	1 300	4 Ї	3 Ї	2 100	U2 = 1
600	4 Ї	3 500	1 100	2 0	U3 = 1
Vj	V1 = 0	V2 = 2	V3 = 0	V4 = 1

Вычисляем затраты на транспортировку:

Z(X3) = 1•100 + 1•300 + 2•100 + 3•500 + 1•100 = 2200 у.е.;

Z(X3) = 2200 < Z(X2) = 2300.

План X3 является вырожденным, базисная переменная x34 = 0, клетка (3,4) - базисная.

Проверим вычисления:

ДZ = Z(X2) - Z(X3) = 2300 - 2200 = 100.

С другой стороны,

ДZ = Q •Д24 = 100•1 = 100, т.е. расчеты проведены правильно.

План X3 проверяем на оптимальность. Для базисных клеток составляем систему уравнений:

Полагая U1 = 0, находим остальные значения потенциалов, которые записываем в табл.1.10 в соответствующих строке и столбце.

Вычисляем значения оценок Дij для свободных клеток:

Д11 = -3 < 0;

Д12 = -4 < 0;

Д13 = -5 < 0;

Д22 = -1 < 0;

Д23 = -2 < 0;

Д31 = -3 < 0.

Все оценки Дij < 0, значит, план X3 является оптимальным. Вспоминая смысловое содержание задачи, запишем ответ.

Ответ: Первому населенному пункту следует перевезти 300 т удобрений со 2-й станции; второму - 500 т с 3-й станции, третьему - 100 т с 3-й станции и четвертому - 100 т с 1-й и 100 т со 2-й станции. Суммарная минимальная стоимость транспортировки груза составляет 2200 у.е..

Замечание: Процесс пересчета циклов в T.З. всегда конечен, поскольку число способов выбора базисных переменных не более, чем число

- конечное число.

1. Размещено на www.allbest.ru