Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

Скачать файл (16,20Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 159

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

64	ГЛ. 2. СИМПЛЕКС-МЕТОД

Каждой точке треугольной области рис. 2.2. соответствует точка области рис. 2.1. Соответствие можно установить, проекти руя эту треугольную область на плоскость х2. Если придать слабой переменной Sj постоянное значение с, то xi и х2 должны удовлетворять уравнению Xi + х2 = hi — с, которое является уравнением прямой, параллельной xi + х2 = Ь4. Если слабая переменная равна нулю, то + х2 = &i. Таким образом, значение

слабой переменной может служить мерой близости точки треуголь ной области к границе xi + х2 = Ъ\ полупространства, определяем мого исходным неравенством.

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

Z == С\Х\ -J- с2х2 -\|—. . .	-р спхп
при условиях	(1)

Ах ^ Ь (А есть (т X п)-матрица),

X > 0.

Векторы х лежат в n-мерном пространстве. Вводя слабые перемен ные si, . . ., sm и полагая х* = (х^, . . ., хп, slt . . s m), полу чаем

минимизировать

z = с* х*

(2)

при условиях

А*х* = Ь,

2.5. ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ	65
где А* = (А, —I) и с* = (ct, . . сп, 0, . .	0). Поскольку

теперь имеется т уравнений с п Ц- т переменными, размерность множества решений системы (2) равна п + т — т = п. Верши ной множества решений системы (1) является точка, в которой п неравенств из т + п неравенств (1) выполняются как равенства, т. е. п компонент вектора х* равны нулю. Эти компоненты являют ся небазисными переменными.

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

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

а В — базис; тогда х = В -1Ь. Если х ^ 0, то х — вершина мно

жества решений. Если х ^ 0, то эта точка является пересечением п гиперплоскостей вне множества решений.

Для того чтобы решить задачу (2) при помощи симплексметода, используется метод исключения Гаусса, в результате чего получается система, эквивалентная системе (2). Эта система имеет вид IxB + B ^ N x^ = B -1b, где В — базис, а целевая функция выражается через небазисные переменные. Для допусти мого базиса х в > 0, так что можно рассматривать х'в как слабые переменные. В пространстве небазисных переменных можно рас смотреть т неравенств B ^ N x^ ^ В _1Ь; точка \ N = 0 соответ ствует началу координат. Симплекс-метод начинает с допустимой вершины и затем переходит в соседнюю вершину так, чтобы значе ние целевой функции «улучшилось». Необходимыми условиями являются: .1) соседняя вершина должна быть допустимой; 2) значе ние целевой функции в соседней вершине должно быть «лучше», чем в предыдущей. В пространстве векторов х N возрастание от нуля одной из небазисных переменных, при котором остальные нвбазисные переменные остаются равными нулю, соответствует движению из начала координат по одной из координатных осей. При этом, поскольку п — 1 небазисных переменных равны нулю, п — 1 ограничений задачи выполняются как равенства. Другими словами, все соседние вершины начала координат (которые соот ветствуют текущему решению) связаны с началом координат п — 1 ребрами выпуклого многогранника. Возрастание от нуля некото рой небазисной переменной может привести к тому, что эта пере менная станет базисной. Для того чтобы получить в качестве реше ния вершину, необходимо заменить одну из базисных переменных на небазисную. Пусть xh — небазисная переменная и а* — соот ветствующий вектор-столбец. Если xh принимает значение 0,

то текущие базисные переменные х принимают значения х (0) = = В -1 (Ь — 0ад). Когда 0 возрастает от нуля, значение х (0) также меняется, подчиняясь при этом требованию х (0) ^ 0, т. в-

5 т. Ху

66	ГЛ. 2. СИМПЛЕКС-МЕТОД
0	меняется в границах 0 ^ 0 ^ 0тахКогда 0 = 0тах, одна из

компонент х (0) становится равной нулю.

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

вие x t ^ 0. (Заметим, что xt ^ 0 соответствует одному из нера венств B^Nxjy ^ В _1Ь.)

Поскольку целевая функция z выражается теперь через c Nx N, условие с* > 0 влечет за собой оптимальность таблицы. Если для

небазисной переменной Cj < 0, то возрастание от нуля этой пере менной улучшает значение целевой функции.

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

согласно критерию выбора min Cj < 0, то это соответствует спуску

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

цию равна min с3‘ ai0 для данного /.

гaii

2.6.Экономическая интерпретация симплекс-метода

Рассмотрим задачу 3 из § 1.1: минимизировать

z	=	сх
при условиях	Ь,	(1)
Ах =	Ь,	х ^ 0.

Пусть А = (В, N), где В является допустимым базисом. Тогда задачу (1) можно переписать следующим образом:

минимизировать

	Z — СдХд -(-		c Nx N
при условиях	Nxw = Ь,		хв, х я ^	(2)
В хв +	Nxw = Ь,		хв, х я ^	0.
Положив x N = 0 и х в =		В _1Ь,	получим допустимое решение
задачи (2). Величина	z =	с вХв =	свВ _1Ь	представляет собой

оценку затрат, а вектор х в — (xt , . .		.., хт) дает ненулевые интен
сивности	использования процессов,	соответствующих векторам
ai, • .	am.

2.6. ЭКОНОМИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ

Рассмотрим наряду с первым другое химическое производство с вектором ограничений Ь* (объемом выпуска продукции), где имеется тп процессов, каждый из которых представлен единичным вектором ег (г = 1, . . ., тп). Тогда i-й процесс необходимо осу ществлять с интенсивностью bf, поскольку только один процесс е,- производит i-й вид продукта. Общая стоимость работы тппроцессов при использовании технологий с интенсивностями х*, . . ., х* имеет следующий вид:

'2cfxf = '2]c*bt.

\г

Если с* = св В -1 и Ь* = Ь, то по отношению к производству с заданным выходом продукции Ь эксплуатационные расходы второго производства будут такими же, как и в предыдущем слу чае. Обозначим свВ -1 = я = (я^ . . ., ят ) = с*. Можно счи тать, что Я; является ценой, которую мы платим за единицу г-го продукта на первом производстве. Пусть а;- — любой небазисный вектор, представляющий ;'-й технологический процесс на первом производстве. При единичной интенсивности использования /-м процессом производится ац единиц i-ro продукта (г = 1, . . ., тп). Поскольку в рассматриваемой системе каждая единица i-ro веще ства стоит я г денежных единиц, стоимость продукта, произво дящегося технологическим процессом aj, составит яа^. Обозначим яау через Zj. Реальные эксплуатационные расходы /-го процесса составляют cj. Таким образом, если cj — Zj = Cj — яа;- ^ 0, то данный процесс использовать не следует. Если с7- — Zj < 0, то использование процесса aj принесет некоторую экономию. После того как вместо некоторого базисного вектора в базис вводится aj с максимально большой возможной интенсивностью, появляются новые цены я', отличные от старых я. Отсюда я ; называется

теневой ценой i-й строки относительно данного базиса. Вычисле ние Cj — яa^• в литературе называется операцией оценивания. Операция оценивания служит для выяснения, должен ли быть введен вектор aj в базис.

Заметим, что базис В является оптимальным, если В -1Ь ^ О и cj — свВ _1ау ^ 0 для всех j. Пусть Ь получит небольшое при

ращение АЬ, так чтобы	В -1 (Ь + АЬ)	0. Тогда Cj = Cj —
— свВ _1а7не изменится.	Отсюда следует,	что базис В останется

оптимальным базисом и для новой правой части b + АЬ. Посколь

ку я =		свВ -1,	я также не изменится. Но в § 2.4 было показано,
что z	=	т	т- е* новое оптимальное значение целевой функции
что z	=	2	т- е* новое оптимальное значение целевой функции
имеет		г — 1
имеет	вид
			Z ■— 2 я г (^i	Aftj) — Z-f- ^ Я; A
			i — l	г= 1

68	Т Л . 2. СИМПЛЕКС-МЕТОД

откуда

Таким образом, лг показывает, как изменяется z в зависимости от изменения bt. В задаче 1 § 1.1, если ограничение по к-му пита тельному веществу bh увеличится на единицу, а все остальные ограничения останутся без изменений, то минимальная общая стоимость рациона увеличится на iik. Подобным же образом, если bk уменьшится на единицу, а все остальные ограничения останутся без изменений, то минимальная общая стоимость рациона умень шится на л й.

Упражнения

1. Дана линейная программа: минимизировать

	z — 6a:i +	Зх2 + х3 +	lx k +	8х5
при условиях
	x i И- 2^2	7 х 3	= 9,	'
	6x2 + 3x3-{-xi —x6 = 9,
'	Х} > 0	(/ = 1, . . . , 5) .

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

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

3. Рассмотрим задачу: минимизировать

z = 10 — 2;г4 — Зх5

при условиях

X i	—Х 3 -)- #4 +3х5=3,
х2	х з “I- ~2 ■Г 4 2х 5 = 2, X j ^ z 0 (/ = 1, . . . » 5).
	4

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

ДОПОЛНЕНИЕ	69
значением величины z = яЬ. (Указание. При вычислении z =	яЬ
константа 10 не учитывается.)

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

5. Дайте математическое обоснование двух следующих утвер ждений.

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

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

6. Рассмотрим задачу:

найти	минимум
	z = 11 — х3 — xi — х5
при условиях
	+ х 3 — х4 + 2* 5 = 2,
х*£	х3 “I- 2д?4 —(- х3 1, Xj 0 ( / 1, . . ., 5).

Пусть Xi и хг — исходные базисные переменные. Выберите среди всех возможных векторов — кандидатов для ввода в базис, такой, с введением в базис которого целевая функция больше всего умень шится. Объясните правило выбора таких векторов, используя Cj,

&l j И

Дополнение

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

ГЛАВА 3

ДВОЙСТВЕННОСТЬ

3.1.Теорема двойственности (Гейл, Кун, Таккер [71])

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

М = {1, . . . , ти .. ., т},	Л/1 = {1,	. . . , шД,	M i = {mi + l ,		. . т};
N = {1, . . ., «!, . . . , п),	ЛД={1,	. . ., пД,	# ! = {/*! +	!,	-•
НАпример, запись j £ N t означает, что /			= 1, . . .,	щ.