Аналитическое решение

Решение строится в два этапа:

1) отыскивается исходное опорное решение;

2) методом последовательных итераций ищется оптимальное решение.

Определение исходного опорного решения

Построим исходное опорное решение методом «северо-западного угла» (табл. 2). Поскольку потребности первого потребителя В1 (b₁=220 м³) больше, чем запасы первого глинзавода А1 (a₁=120 м³), то для удовлетворения этих потребностей будем использовать запасы первого и второго глинзавода; в первую ячейку записываем x₁₁=b₁=120 м³, в ячейку (2.1) записываем недостающие 100 м³. Далее перемещаемся в ячейку (2.2) и записываем здесь оставшиеся 40 м³. Для удовлетворения потребностей второго бурового участка нам не хватает 140 м³, поэтому воспользуемся запасами третьего глинзавода – в ячейке (3.2) записываем 140 м³. Таким образом, потребности второго потребителя В2 полностью удовлетворены.

Таблица 2. Транспортная таблица (исходное опорное решение)

Склады	Потребители	Запасы заданные
В1	В2	В3	В4
А1
А2
А3
А4
Потребности заданные					-

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

В результате имеем таблицу с заполненными семью ячейками, что соответствует теории: m+n-1=7, где m и n – число складов и буровых соответственно. Заметим, что суммарная стоимость перевозок исходного опорного решения равна:

Определение оптимального решения методом потенциалов

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

Для того, чтоб допустимый (опорный) план транспортной задачи X={ x_ij}_, был оптимальным, необходимо и достаточно, чтобы существовала система чисел ; , удовлетворяющих условиям:

(5)

(6)

Соотношения (5) и (6) называются условиями потенциальности оптимального плана транспортной задачи. Набор величин приписывается строкам (первой строке - U₁, второй – U₂ и т.д.), поэтому U₁ называется потенциалом первой строки, U₂ – потенциалом второй строки и т.д. Аналогично набор величин приписывается столбцам (первому столбцу - V₁, второму - V₂ и т.д.) и эти величины называются потенциалами соответствующих столбцов.

Соотношение (5) можно переписать в виде:

, где , если . (7)

Величины v_ij называют невязками, их вычисляют для всех ячеек без перевозок. Если хотя бы в одной ячейке невязка больше нуля, то план перевозок может быть улучшен. Если все невязки неположительные (или равны 0), то опорное решение является оптимальным.

Шаг 1 – определяем потенциалы исходного опорного решения (см. табл. 1). Строкам этого решения назначаем потенциалы U ₁, U ₂, U ₃, а столбцам – потенциалы V ₁, V ₂, V ₃, V ₄. Для их расчета составляем систему уравнений:

Имеем восемь неизвестных величин и семь уравнений. Значение любой неизвестной величины задаем произвольным числом, например, U ₃=0. Тогда, остальные величины потенциалов будут равны:

U ₁=-3; U ₂=-2;U₄=2; V ₁=-1; V ₂=2; V ₃=4; V ₄=3.

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

Таблица 3. Транспортная таблица с вычисленными значениями потенциалов

Склады	Потребители	Запасы заданные
В1	В2	В3	В4
А1										-3
А2										-2
А3		-2
А4		-6		-4
Потребности заданные					-	-
	-1				-	-

Шаг 2 – вычисляем значения невязок для всех ячеек без перевозок по соотношению (7). Запишем значения невязок в правый верхний угол каждой ячейки (значения невязок выделены полужирным шрифтом). В ряде клеток наблюдаются нарушения (невязки больше нуля): (1,2), (1,3), (1,4), (2,3), (2,4) и, следовательно, план может быть улучшен.

Шаг 3 – организуем замкнутый контур с началом в ячейке (2,3), имеющей максимальную положительную невязку v _max=5:

вершина 1 (2,3) ® вершина 2 (3,3) ® вершина 3 (3,2) ® вершина 4 (2,2).

Величинаперераспределения q равна наименьшему значению из перевозок, стоящих в четных вершинах цикла, т.е. q =min{90;40}=40 м³. Вычислим новые значения перевозок для вершин контура: в нечетных вершинах добавляем величину q, а в четных вершинах – вычитаем эту величину:

· в вершине 1 (2,3) х ₂₃=0+40=40 м³;

· в вершине 2 (3,3) х ₃₃=90–40=50 м³;

· в вершине 3 (3,2) х ₃₂=140+40=180 м³;

· в вершине 4 (2,2) х ₂₂=40–40=0 м³.

Получим новое, второе опорное решение (табл. 4). Вычислим суммарную стоимость перевозок для полученного опорного плана:

Таблица 4

Склады	Потребители	Запасы заданные
В1	В2	В3	В4
А1				-1		-1		-1
А2				-5				-2
А3
А4		-1		-4
Потребности заданные					-	-
					-	-

Уменьшение стоимости перевозок по отношению к исходному опорному плану составит:

Теоретически это уменьшение равно q×v _max=40×5=200 руб., что совпадает с рассчитанным выше значением.

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

Шаг 1 – составляем новую систему потенциалов:

Пусть U ₃=0. Тогда

U ₁=2; U ₂=3;U₄=2; V ₁=4; V ₂=2; V ₃=4; V ₄=3.

Занесем эти значения потенциалов в транспортную таблицу взамен старых (см. табл. 4).

Шаг 2 – определяем значения невязок для всех ячеек с «нулевыми» перевозками по соотношению (7). Значения невязок записаны в правом верхнем углу ячеек и выделены полужирным шрифтом.

В ячейке (3,1) наблюдается нарушение, следовательно, план может быть улучшен.

Шаг 3 – организуем замкнутый контур с началом в ячейке (3,1), имеющей максимальную положительную невязку v _max=3:

вершина 1 (3,1) ® вершина 2 (2,1) ® вершина 3 (2,3) ® вершина 4 (3,3).

q =min{100;50}=50 м³

Вычислим новые значения перевозок для вершин контура: в нечетных вершинах добавляем величину q, а в четных вершинах – вычитаем эту величину:

· в вершине 1 (3,1) х ₃₁=0+50=50 м³;

· в вершине 2 (2,1) х ₂₁=100–50=50 м³;

· в вершине 3 (2,3) х ₂₃=40+50=90 м³;

· в вершине 4 (3,3) х ₃₃=50–50=0 м³.

Получим новое, третье опорное решение (табл. 5). Вычислим суммарную стоимость перевозок для полученного опорного плана:

Таблица 5

Склады	Потребители	Запасы заданные
В1	В2	В3	В4
А1						-1		-1		-1
А2				-1				-2
А3						-3		-3
А4		-1								-1
Потребности заданные					-	-
					-	-

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

руб.,

что совпадает с теорией: q×v _max=50×3=150 руб.

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

Шаг 1 – рассчитаем очередную систему потенциалов:

..

Пусть U ₃=0. Тогда

U ₁=-1; U ₂=0;U₄=-1; V ₁=1; V ₂=3; V ₃=1; V ₄=0.

Занесем эти значения потенциалов в транспортную таблицу взамен старых (см. табл. 5).

Шаг 2 – определяем значения невязок для всех ячеек с «нулевыми» перевозками по соотношению (7). Значения невязок записаны в правом верхнем углу ячеек и выделены полужирным шрифтом.

В ячейке (1,2) наблюдается нарушение, следовательно, план может быть улучшен.

Шаг 3 – организуем замкнутый контур с началом в ячейке (1,2), имеющей максимальную положительную невязку v _max=3:

вершина 1 (1,2) ® вершина 2 (3,2) ® вершина 3 (3,1) ® вершина 4 (1,1).

q =min{180;120}=120 м³

Вычислим новые значения перевозок для вершин контура: в нечетных вершинах добавляем величину q, а в четных вершинах – вычитаем эту величину:

· в вершине 1 (1,2) х ₁₂=0+120=120 м³;

· в вершине 2 (3,2) х ₃₂=180–120=60 м³;

· в вершине 3 (3,1) х ₃₁=50+120=170 м³;

· в вершине 4 (1,1) х ₁₁=120–120=0 м³.

Получим новое, третье опорное решение (табл. 6). Вычислим суммарную стоимость перевозок для полученного опорного плана:

Таблица 6

Склады	Потребители	Запасы заданные
В1	В2	В3	В4
А1		-2				-3		-3
А2				-2				-2
А3						-3		-3
А4		-1		-1						-1
Потребности заданные					-	-
					-	-

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

руб.,

что не совпадает с теорией: q×v _max=120×3=360 руб.

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

Шаг 1 – рассчитаем очередную систему потенциалов:

..

Пусть U ₃=0. Тогда

U ₁=1; U ₂=0;U₄=-1; V ₁=1; V ₂=2; V ₃=1; V ₄=0.

Занесем эти значения потенциалов в транспортную таблицу взамен старых (см. табл. 6).

Шаг 2 – определяем значения невязок для всех ячеек с «нулевыми» перевозками по соотношению (7). Значения невязок записаны в правом верхнем углу ячеек и выделены полужирным шрифтом.

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

Дата добавления: 2015-11-16