Построение начального базисного решения

Начальное базисное решение строится в соответствии со следующей достаточно простой идей. Выбирается произвольная клетка таблицы Х и в нее заносятся максимально возможный по значению элемент. Так как каждое и , то максимально возможное значение .

Допустимое решение заносится в матрицу Х, в которой будет заполнено () клеток, так как ранг матрицы C равен ().

При этом должны выполняться условия:

1. сумма по строкам равна A _i,

2. сумма по столбцам равна B _j.

Алгоритм построения начального базисного решения

Шаг 0. k =0;

Шаг 1. Выбирается произвольная свободная клетка (i, j);

Шаг 2. Вычисляется ;

Шаг 3. Если , то i -ая строка вычеркивается, а ;

Шаг 4. Иначе вычеркивается j -ый столбец, а ;

Шаг 5. ;

Шаг 6: Если , то

Конец.

Иначе переход к шагу 1.

В алгоритме построения базисного решения не задается способ выбора клетки (i, j) для заполнения. Мы предлагаем два наиболее распространенных метода заполнения клеток при построении начального базисного решения:

1. Метод северо-западного угла. (В этом случае для заполнения выбирается левая верхняя клетка);

2. В методе северо-западного угла не учитывается стоимость перевозок вследствие чего полученное базисное решение может быть далеким от оптимального. Поэтому при заполнении клеток можно предложить в первую очередь заполнять клетки с наименьшей стоимостью перевозок. Этот метод называется методом минимального элемента.

Пример 4.2.1. Имеется транспортная задача.

B j

Рис. 3.

1) Используем при выборе клеток для заполнения метод северо-западного угла.

					7
					8	1
						10	7
							20	9
8	10	7	11	9
1	3	0

Рис. 4.

Невычеркнутых элементов осталось 8, так как ранг матрицы равен 8, то есть матица размера 5×4. 5+4–1=8 (m + n –1).

.

2) Метод минимального элемента.

 

								8
								10
							20
	10		11
			4

Рис. 5.

 

.

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

Однако, поскольку этот метод является эвристическим не следует надеяться, что с его помощью всегда будет получено хорошее решение.

Задание 1. Придумать пример транспортной задачи, при решении которой использование метода минимального элемента даст допустимое решение со значением целевой функции большим, чем при решении той же задачи, используя метод северо-западного угла.

Задание 2. Придумать собственный подход к выбору клеток для заполнения. И обосновать его целесообразность.

Замечание 3. При построении начального базисного решения на каждом шаге вычеркивается либо строка либо столбец, а на последнем шаге остается не вычеркнутой и заполняется ровно одна клетка, таким образом общее количество заполненных клеток (m + n –1). Так как число базисных компонент в транспортной задаче равно (m + n –1), то можно предположить, что мы получили базисное решение. (Доказательство этого факта будет приведено позже.)

 

Метод потенциалов

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

Основные этапы симплекс-метода:

Этап 1. Вычисление оценок. Проверка решения на оптимальность. Если решение оптимальное, то конец. Иначе переход к этапу 2.

Этап 2. Перестроение базисного решения. Переход к этапу 1.

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

Этап 1. Вычисление оценок и проверка решения на оптимальность.

Наша задача ориентирована на min, поэтому нужно учесть критерий оптимальности .

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

Переходим к вычислению оценок для транспортной задачи. Выпишем ограничения задачи двойственной к транспортной. Обозначим через двойственные переменные к первому блоку ограничений транспортной задачи и через - ко второму блоку ограничений.

	, где
	, где

.

.

Вектор коэффициентов при имеет вид:

.

Поэтому двойственное ограничение при переменной будет следующим:

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

( из матрицы Х)

Из этой системы найдем , .

Так как количество ограничений равно (m + n –1), а количество переменных равно (m + n), поэтому будем полагать, что всегда U ₁ = 0 и тогда:

,

.

Вычисляем для всех (i, j) небазисных оценки вычисляется по формуле

.

 

Алгоритм

Шаг 1. Для всех базисных записывается уравнение ,

Шаг 2. U ₁ = 0,

Шаг 3. Вычисление остальных потенциалов , по формулам:

,

,

Шаг 4. Для всех (i, j) небазисных вычисляются оценки :

,

Шаг 5. Если все , то вычисляется

.

Конец.

Иначе переход к этапу 2.

Этап 2. Перестроение базисного решения.

Пусть существует , как следует из теории симплекс-метода, если переменную сделать базисной, то значение целевой функции уменьшится.

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

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

Эти элементы можно определить с помощью правила вычеркивания.

Правило вычеркивания

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

1. все элементы вычеркнуты,

2. в каждой из невычеркнутых строк и столбцов содержатся не менее двух выделенных элементов.

Имеет место следующее утверждение.

Утверждение 1. Столбцы соответствующие вычеркнутым элементам линейно независимы. (Без доказательства.)

Утверждение 2. Допустимое решение транспортной задачи построенное с помощью метода северо-западного угла или метода минимального элемента является базисным.

Доказательство. В самом деле, при построении допустимого решения транспортной задачи после определения значения некоторого обязательно вычеркивается либо стока, либо столбец, то есть этот элемент является единственным в этой строке или столбце. Следовательно, столбцы коэффициентов соответственные найденным линейно независимы, то есть мы доказали, что найденное допустимое решение является базисным.

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

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