Решение задач линейного программирования транспортного типа: Методические указания к выполнению индивидуальных домашних заданий, страница 11

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

С2 =	0	8	2	5
	11	0	5	4
	2	3	0	0
	0	11	4	15

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

С2 =	0	8	2	5
	11	0	5	4
	2	3	0	0
	0	11	4	15

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

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

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

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

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

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

С2 =	0	8	2	5
	11	0	5	4
	2	3	0	0
	0	11	4	15

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

С3 =	0	6	0	3
	11	0	5	4
	2	3	0	0
	0	9	2	13

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

В новой матрице стоимостей С₃ можно построить допустимый план на базе нулевых клеток (1, 3), (2, 2), (3, 4) и (4, 1). Он является оптимальным и совпадает с решением, полученным ранее методом потенциалов.

Х* =			1
		1
				1
	1

Отметим, что минимальное значение целевой функции следует вычислять, используя исходную матрицу cтоимостей С₀.

 S^* = 9 + 4 + 11 + 4 = 28.

Замечание. Если в задаче о назначениях требуется максимизировать некоторый критерий эффективности назначений, то все элементы матрицы стоимостей следует умножить на -1 (тем самым перейти к минимизации исходной целевой функции) и сложить их с достаточно большим числом М так, чтобы вновь получившаяся матрица стоимости не содержала отрицательных элементов (М достаточно выбрать равным по модулю наименьшему отрицательному элементу в матрице стоимости). Теперь задачу можно решать как задачу минимизации.

ЛИТЕРАТУРА

1.  Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986.

2.  Барабаш С.Б., Воронович Н.В. Экономико-математические методы. Учебное пособие. – Новосибирск: НГУЭиУ, 2004.

3.  Бахтин А.Е., Высоцкий Л.Л., Савиных В.Н. Сборник задач по математическому программированию. – Новосибирск: НГАЭиУ, 1994.

4.  Исследование операций в экономике, под редакцией Н.Ш. Кремера. – М.: Банки и биржи, 1997.

5.  Шелобаев С.И. Математические методы и модели в экономике. – М.: ЮНИТИ, 2000.

6.  Шикин Е.В. Математические методы и модели в управлении. – М.: Дело, 2002.

7.  Таха Х. Введение в исследование операций. – М.: Вильямс, 2001.

8.  Экономико-математические методы и прикладные модели, под редакцией В.В. Федосеева. – М.: ЮНИТИ, 2000.

9.  Эддоус М., Стэнсфилд Р. Методы принятия решений. – М.: ЮНИТИ, 1997.

Решение задач линейного программирования
транспортного типа

Методические указания

к выполнению индивидуальных домашних заданий

Подписано к печати                                2005г.

НГУЭУ, ул. Каменская, 56.