Промежуточные вычислении 7 страница

Теперь можно сделать уравнение г/, + 2у₂ + у₃ = 2 однородным, умножив его правую часть на (г/, + у₂ + у₃ + у₄)/5, поскольку последнее соотношение равно 1. Таким обра­зом, после приведения подобных членов получаем

3_У1+8у₂ + 3_Уз-2у₄ = 0.

Чтобы преобразовать равенство у_х + у₂ + у₃ + у₄=Ъ в уравнение, определяющее симплекс, введем новые переменные х_х = yjb, / = 1,2, 3, 4. Получаем следующую задачу ЛП.

Максимизировать z = 5дг, + 5дг₂

при ограничениях

3^ + 8х₂ + Злг₃ - 2х₄ = О, х, + х₂ + х₃ + х₄ = 1, х>0, i = l,2, 3, 4.

Теперь обеспечим выполнение условия, что точка Х = (1/л, 1/п, 1/п), являю­щаяся центром (барицентром) симплекса, будет удовлетворять однородному урав­нению. Для этого от левой части каждого однородного уравнения отнимем искусст­венную переменную с коэффициентом, равным алгебраической сумме всех коэффициентов левой части уравнения (в данном случае имеем 3+8+3-2 = 12). Эта искусственная переменная также прибавляется к уравнению симплекса и в ви­де штрафа появляется в выражении целевой функции. В нашем примере искусст­венная переменная х_ь войдет в задачу ЛП следующим образом.

Максимизировать z = Ьх, + Ьх₂ - Мх_ь

при ограничениях

Зх_х + 8х_г + Злг₃ - 2х₄ - 12х_ъ = О, *,>(),/= 1,2.....5.

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

Глава 7. Теория линейного программирования

Последний пример показывает, что любую задачу ЛП можно с помощью преоб­разований привести к виду, который необходим для выполнения алгоритма Кар­маркара. Но эти преобразования громоздкие и неочевидные, поэтому их редко ис­пользуют на практике. Существуют различные модификации алгоритма, которые не требуют обязательного выполнения второго условия (min г = 0).

Пример 7.7.2

Рассмотрим еще раз задачу из примера 7.7.1.

Максимизировать г=у_х+у₂

при ограничениях

Уг + 2у_г<2,

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

Прямая задача Двойственная задача

Максимизировать Уо = /1 + уг при ограничениях yi + 2у₂ < 2,

Уь Уг 2 0.

Ограничения этих задач в стандартной форме запишутся так:

</, + 2</₂ + 1/₃ = 2,</з>0.

ш,-ш₂ = 1,ш₂>0. (1) Из условия оптимума у₀ = w₀ вытекает, что

y_x+y₂-2w_x = 0. (2) Выбираем достаточно большое число М, чтобы выполнялось неравенство

y.+y^y. + w. + w^M. (3)

Теперь путем введения дополнительной переменной преобразуем неравенство (3) в равенство:

yi+y₂ + y₃ + ^wi ^{+ w}2 ^{+ s}i=^M<^si*⁰- (⁴) Далее введем новую переменную s₂ такую, что следующие два равенства, вытекаю­щие из равенства (4), будут выполняться тогда и только тогда, когда s₂ = 1.

</i + У г + Уз + ^wi + ^w2 + ^si ^{- S}2^M = °>

y₁ + y₁ + y_a + w_l+w₂ + s_l+s₂ = M + 1. (5)

При условии s₂ = 1, что обусловливают равенства (5), ограничения (1) можно запи­сать как

У, + 2у₂ + у_г-2з₂ = 0.

w_x-w₂- ls₂ = 0. (6)

Минимизировать щ = 2щ при ограничениях

w,>\ 1 2*,>lj

w, > 0.

7.7. Метод Кармаркара

Теперь определим новые переменные x_v х₂, х₇ на основе соотношений

jf₍ = (M + l)i_/,i=l₁2,3,

w

i-з

■ (М + 1)*., j = 4, 5,

_Sl = (M+l)x₆, s₂ = (M + l)x₇.

Подставляя последние выражения в равенства (2), (5) и (6), получим новые ограни­чения в виде равенств.

+ х₀ - 2х_а = О,

, + х₂ + х₃ + х₄ + х_ь + х_е - Мх₇ = О, _[ + х_г + х₃ + х₄ + х₅ + х₆ + х₇ = 1, + 2х₂ + х₃ - 2х₇ = О, ■ х₅ —~ х₇ О,,£0,у«1,2, 7.

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

х-(- 1111111

удовлетворяла системе АХ = 0. Это условие можно выполнить для однородной сис­темы (т.е. для системы, у которой правые части уравнений равны нулю), если соот­ветствующий коэффициент при искусственной переменной х_е в любом уравнении систем будет равен сумме всех остальных коэффициентов этого уравнения. С уче­том этого замечания получаем следующую преобразованную задачу ЛП.

Минимизировать z = x_s

при ограничениях

х, + х₂ - 2х₄ - 0х_а = О, х

+ 2х₂ + х₃ - 2х₇ - 2x_s =

- Мх₇ - (6 - M)x_g = О, х, + ^%гх, + х, - ^%гх_ч - zx_s = О,

ОС ^ OCrj I ^) у

х, + х, + я, + х, + ли + X* + X, + х_а = 1, *,><), у-1,2,...,8.

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

Теперь опишем основные этапы алгоритма Кармаркара. На рис. 7.7, а показано ти­пичное трехмерное пространство решений, определяемое однородной системой ограни­чений АХ = 0, состоящей из одного уравнения. В данном случае пространство решений совпадает с отрезком прямой АВ, лежащим внутри симплекса IX = 1, причем точка (1/3,1/3,1/3) является допустимой внутренней точкой пространства решений. Анало­гично на рис. 7.7, б показано четырехмерное пространство решений (треугольник ABC), определяемое однородной системой ограничений, также состоящей из одного уравнения. В этом случае центром симплекса является точка (1/4, 1/4, 1/4, 1/4).

Глава 7. Теория линейного программирования

а) Трехмерное пространство решений

(О, 0, 0, 1)

(0,1,0,0)

б) Четырехмерное пространство решений Рис. 7.7. Трех- и четырехмерный симплексы

7.7. Метод Кармаркара

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

Чтобы новая точка решения была внутренней, она не должна выходить за преде­лы симплекса. (Это значит, что на рис. 7.7, а новая точка не может быть точкой А или В, а на рис. 7.7, б— не может совпадать с точками отрезков АВ, ВС и АС.) Для того чтобы определить такую точку, построим сферу, вписанную в симплекс. В л-мерном пространстве в правильный симплекс можно вписать сферу с максимальным радиу­сом г, равным \lsjn(n -1).⁵ Тогда пересечение сферы радиуса от (0 < а < 1) и простран­ства решений, определяемого системой АХ = 0, будет содержать только внутренние точки пространства решений с положительными координатами. В таком случае для определения новой точки решения можно перемещаться вдоль проекции градиента до тех пор, пока будем находиться внутри ограниченного пространства, являющегося пересечением шара радиуса аг и пространства, определяемого системой АХ = 0.

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

x_t

v,= ——, 1 = 1,2.....л,

где x_kl — i-й элемент текущего решения, т.е. г-я координата текущей точки реше­ния X_t. Такое преобразование правомерно, поскольку все x_ki > 0. Также отметим,

что по определению 1",у, = 1 (т.е. 1Y= 1). Это преобразование можно записать в

матричном виде

_Y_ Р.'Х 1D/X'

где D,. — диагональная матрица, у которой i-й диагональный элемент равен х_к1. Это преобразование осуществляет взаимно-однозначное отображение Х-пространства в У-пространство, поскольку нетрудно проверить, что из последней формулы следует

Х = ^

По определению min СХ = 0. Отсюда следует, что значение lD_tY должно быть положительным. В таком случае исходная задача ЛП преобразуется в следующую.

Минимизировать z = CD_tY

при ограничениях

AD_kY = 0, 1Y-1, Y>0.

⁵ Здесь надо уточнить, что центр этой сферы находится в барицентре симплекса. Далее в этом разделе, не оговаривая этого явно, везде предполагается, что центры всех сфер совпа­дают с барицентром симплекса. — Прим. ред.

Глава 7. Теория линейного программирования

Преобразованная задача имеет тот же тип, что и исходная. Мы можем опять на­чать решение этой задачи с точки Y = (l/n, 1/п, 1/п), являющейся центром симплекса, и повторить действия, выполненные на предыдущем этапе. После каж­дой итерации на основании полученного Y-решения нетрудно вычислить значения исходных Х-переменных.

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

Минимизировать г = CD_tY

при ограничениях

AD,Y = 0,

Y лежит в шаре радиуса аг.

Поскольку шар радиуса аг является частью пространства допустимых решений, определяемого ограничениями IX = 1, X > О, эти ограничения можно исключить из рассмотрения. Можно показать, что решение последней задачи вычисляется по следующей формуле

^новое ^текущее

ы

лить так: = (1/п, 1/п, 1/п), с_р— проекция градиента, которую можно вычис-

с-р-рЧррУрксв/,

где Р = 1

Выбор параметра а — ключевой момент при построении алгоритма. Обычно а выбирается настолько большим, насколько это возможно, чтобы ускорить сходи­мость к оптимальному решению. Но при выборе слишком большого значения а можно "упереться" в запрещенную границу симплекса. В настоящее время не из­вестно оптимальное значение а. Кармаркар предлагал использовать а = (п - 1)/Зл. Итак, алгоритм Кармаркара требует выполнения следующих этапов.

Этап О. Алгоритм начинается с точки Х₀ = (1/п, 1/п, 1/п), вычисляют­ся параметры г = — 1) и а = (п - 1)/Зп.

Основной этап к. Определяем

D_t = diag{x„......xj,

P =

I 1 J

и вычисляем

Y_-|IA

n n

IV, c.

1ЫГ

x₄.,=

новое новое

где с= [I - Р^Г(РР^Г)'P](CD/

7.7. Метод Кармаркара

Пример 7.7.3

Рассмотрим следующую задачу ЛП, которая уже приведена к форме, необходимой для выполнения алгоритма Кармаркара.

Минимизировать z = 2х_х + 2х₂ - Зх₃

при ограничениях

*, - 2*2 + *з = °. х_г + х₂ + х₃ = 1,

х_х, х₂, х₃> 0.

Эта задача удовлетворяет всем условиям алгоритма Кармаркара, а именно точка X = (1/3, 1/3, 1/3) удовлетворяет уравнению х, - 2х₂ + х₃ = 0 и оптимальное значе­ние целевой функции равно нулю (оптимальным решением является вектор (О, 0,6, 0,4)).

Итерация 0

с = (2, 2,-3), А = (-1,-2,3),

V ^{1 1} Ч ^{1 2}

Мз'З'з} ' = ^а=9

= 0.33333,

D„ =

		ЗУ

Используя проективные преобразования, получаем У₀: Итерация 1

III 3' 3' 3

cD₀ = (2,2,-3)

'I 0 0^Л

0 i о о о

ч

AD₀= (-1,-2,3)

ЗУ

i О О

з

О I о

з

О 0 1

I _2

"з" 3'

			(-- Л
	(1	1 1
		-2 1
	ч 1	1 1)	I1 и
ч

i о

о

ч з/

	'10 0^	г
I - РГ(РРГ)'Р =	0 I 0	-
	,0 0 1,	ч

1 1

1 о

Г- - О

3 3

U 1 U

Глава 7. Теория линейного программирования

_1_ 42 ' 25 -20 -5^N -20 16 4 _ч -5 4 1,

Отсюда получаем

с =[I-P^r(PP') P](CD_k)⁷ = 42

25 -20 -5"l -20 16 4 -5 4 1

(i\ з

2 3 1

126 '25^ -20 V-5y

Далее находим

Hc„ll = J^25:+(-²⁰⁾;⁺⁽-⁵⁾Ao,257172. 126²

ill] -²x'x—!_x^-x(25.-2a-5)^r: 3 3 Ъ) 9 V6 0,257172 126 ^v '

= (0,263340, 0,389328, 0,347332)^г.

Теперь найдем X_t D Y i ^Hi

V — 0 hohoc _ _2_

ID Y

"'О ^д новое

^1d,^yho»«= -0,1,1X0,263340,0,389328,0,347332)^r =±

- = Y_H0BlK = (0,263340,0,389328,0,347332/,

z, =0,26334. Итерация 2

cD, =(2,2,-3)

AD, =(1,-2,

0,263340 0

0 0,389328 0 0 0 0,347332 = (0,526680,0,778656, -1,041996)

(0,263340 0

0 0.389328 0 0 0 0,347332 = (-0,263340, -0,778656,1,041996)

(^ppT =

I - Р^Г(РР^Г) 'p =

-0,26334 -0,778656 1,041996^ 1 1 1 J

'-0,263340 Л -0,778656 1 1,041996 1

0,567727 0 0 0,333333J

(\		0^	(
			-
,0		к	V

Г-0,263340 1 -0,778656 1 1,041996 1

0,567727 0 V-0.263340 -0,778656 1,041996^1

0 0,33333

I

7.7. Метод Кармаркара

(0,627296 -0,449746 -0,177550^ -0,449746 0,322451 0,127295 _ч -0,177550 0,127295 0,050254

Далее вычисляем

_C/l = [I-P^r(PPVP](CD/ =

' 0,627296	-0,449746	-0,177550'	' 0,526680^		' 0,165193 N
-0,449746	0,322451	0,127295	0,778556	=	-0,118435
v-0,177550	0,127295	0,050254 j	-1,041996		-0,046757,

Цс,, I = д/о, 165193- + (-0,118435)² + (-0,046757)² = 0,208571. Отсюда получаем

ч Т

1 1 IV 2

,3 З'З; 9 7б 0,208571 = (0,261479, 0,384849, 0,353671) Теперь для вычисления X, имеем

х (0,165193, -0,118435, -0,046757)⁷ =

	'0,263340		0 \	'0,261479s		'0,068858"
		0,389328		0,384849	=	0,149832
	ч 0		0,347332,	ч0,35367 1,		0,122841,

1D,Y„,

ID Y

^АЖЛ ¹ новое

= 0,341531,

(0,201616^ 0,438707 0,359677

2 = 0,201615.

Выполнив еще один этап алгоритма, получим решение, которое будет еще ближе к оптимальному (0,0,6,0,4). Кармаркар предлагает дополнительный этап, кото­рый позволяет перейти от полученного решения к оптимальной крайней точке. К сожалению, мы не имеем возможности рассмотреть его здесь.

УПРАЖНЕНИЯ 7.7

1. С помощью программы TORA покажите, что решение преобразованной зада­чи ЛП, приведенной в конце примера 7.7.2, дает оптимальное решение пря­мой и двойственной исходных задач. (Совет. Положите М=10 и задайте точность не менее 5 десятичных знаков.)

2. Преобразуйте следующую задачу ЛП к виду, необходимому для применения метода Кармаркара.

Максимизировать z = y_t + 2у₂

при ограничениях

у,-у,£2,

2j/₁+J/₂<4,

Глава 7. Теория линейного программирования

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

4. Выполните три итерации алгоритма Кармакара для решения следующей задачи.

Максимизировать z = 4x, + x₃+x_t

при ограничениях

-2х_х + 2х₂ + х₃ - х₄ = О,

+ х₂ + х₃ + х₄ = 1, х_х,х₂, х₃, х₄>0.

5. Выполните три итерации алгоритма Кармаркара для решения следующей задачи ЛП.

Максимизировать г = 2х_г + х₂

при ограничениях

х_х + х₂< 4, х„ х₂>0.

ЛИТЕРАТУРА

1. Bazaraa М., Jarvis J., Sherali М. Linear Programming and Network Flows, 2nd ed., Wiley, New York, 1990.

2. Hooker J. Karmarkar's Linear Programming Algorithm, Interfaces, Vol. 16, No. 4, pp. 75-90, 1986.

3. Nering E., Tucker A. Linear Programming and Related Problems, Academic Press, Boston, 1992.

Литература, добавленная при переводе

1. Ашманов С. А. Линейное программирование. — М.: Наука, 1981.

2. Голыитейн Е. Г. Теория двойственности в математическом программировании и ее приложения. — М.: Наука, 1971.

3. Голыитейн Е. Г., Юдин Д. Б. Линейное программирование: Теория, методы и приложения. — М.: Наука, 1969.

4. Крона Г. Исследование сложных систем по частям — диакоптика. — М.: Наука, 1972.

КОМПЛЕКСНЫЕ ЗАДАЧИ

7.1. Имеем координаты трех точек:

А - (6, 4, 6, -2), В = (4, 12, -4, 8) и С = (-4, 0, 8, 4).

Разработайте процедуру, которая позволяла бы определить, является ли данная точка выпуклой комбинацией заданных точек. С помощью этой процедуры проверьте, будут ли следующие точки выпуклыми комбинация­ми точек А, В и С.

а) (3,5,4,2),

б) (5,8,4,9).

Комплексные задачи

7.2. Рассмотрим следующую задачу ЛП.

Максимизировать г = Зх_х + 2х₂

при ограничениях

х, + 2х₂ < 6, 2х_х +х₂<8, -х_х+х₂<1, х_х, х₂>0.

Найдите оптимальное решение этой задачи (можно применить программу TORA). Затем, используя информацию, представленную в симплекс-таблице с оптимальным решением, определите второе (по отношению к "абсолютному" оптимуму) наилучшее решение (т.е. крайнюю точку про­странства решений). Проверьте ответ, решив эту задачу графически. (Подсказка. Искомая крайняя точка будет смежной с точкой, соответст­вующей оптимальному решению.)

7.3. Интервальное программирование. Рассмотрим следующую задачу ЛП.

Максимизировать z = {СХ | L < АХ < U, X > 0},

где L и U — вектор-столбцы констант. Определим вектор Y > 0, такой, что АХ + Y = U. Покажите, что исходная задача эквивалентна следующей.

Максимизировать z = {СХ |AX + Y= U,0<Y<U-L,X>0}. Используя показанный прием, решите следующую задачу ЛП.

Минимизировать z = 5х_х - 4х₂ + 6х,

при ограничениях

20 < х_х + 1х₂ + Зж₃ < 46, 10 < Зх, - х₂ + х₃ < 20, 18< 2х_х + Зх₂-х₃<35, х_х,х₂, х₃>0.

7.4. Рассмотрим следующую целочисленную задачу ЛП, где переменные при­нимают только значения 0 и 1.

Минимизировать z = {СХ | АХ < b, X = (0, 1)}.

Предположим, что известна верхняя граница целевой функции z_mili. Введем ограничение

min max {u(b - АХ) + (z,™ - СХ)} > О,

где ц> 0. Это ограничение не нарушает ни одного из ограничений исходной задачи. Покажите, что определение //из этого ограничения фактически сво­дится к решению исходной задачи ЛП. (Совет. В данном случае условие це­лочисленности X = [0, 1] эквивалентно "непрерывному" ограничению 0 < X < 1. Сформулируйте двойственную задачу.)

7.5. В задаче 7.2 оптимальным решением является х_х = 10/3, х₂ = 4/3 и г = 38/3. Как будет изменяться оптимальное значение целевой функции в зависимо­сти от параметра 0, если положить х_х = 10/3 + 0 (на параметр 0 не налагают­ся ограничения в знаке)?

Глава 7. Теория линейного программирования

Предположим, что оптимальное решение задачи ЛП представлено следую­щим образом.

Максимизировать z = с₀ - ^ (г, - с_;)х_;

при ограничениях

х, = х' - ^ ^a,,^x_li ^{1 =} 1. 2, т, все х. и х_: > О,

где — множество индексов небазисных переменных. Предположим, что на текущую базисную переменную х, = х' налагается ограничение х. > d_t, где

d_t — наименьшее целое, большее х]. После введения этого ограничения

оцените верхнюю границу оптимального значения целевой функции. По­вторите процедуру оценки верхней границы при наложении ограничения x_t < e_t, где е, — наибольшее целое, меньше х".

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

Минимизировать z = (10i - 4) x, + {At - 8) x₂ при ограничениях

2x_x + 2x₂ + x₃ = 8, Ax, + 2x₂ + x_t = 6-2t, x_x, x₂, х₃, х₄ ^ 0,

где -оо < t < оо. С помощью параметрического анализа получены следующие результаты:

при -оо < t < -5 оптимальный базис: В = (Р,, Р₄), при -5 < t < -1 оптимальный базис: В = (Р,, Р₂), при -1 < t < 2 оптимальный базис: В = (Р₂, Р₃).

Найдите все критические значения параметра t при t > 2.

ГЛАВА 8

ЦЕЛЕВОЕ ПРОГРАММИРОВАНИЕ

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

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

8.1. ФОРМУЛИРОВКА ЗАДАЧИ ЦЕЛЕВОГО ПРОГРАММИРОВАНИЯ

Рассмотрим пример, приводящий к задаче целевого программирования.

Пример 8.1.1

Файрвилл — небольшой городок, в котором проживает около 20 тысяч жителей. Предположим, городской совет разрабатывает ставки местного налогообложения. Ежегодная база налогообложения недвижимости составляет 550 миллионов долла­ров. Ежегодная база налогообложения розничных и оптовых продаж составляет 35 и 55 миллионов долларов соответственно. Ежегодное потребление городом бензина оценивается в 7,5 миллионов галлонов. Городской совет планирует разработать систему налоговых ставок, основанную на перечисленных базах налогообложения и учитывающую следующие ограничения и требования.

¹ Задачи целевого программирования являются только подклассом задач, решаемых ме­тодами многокритериальной оптимизации. Подходы и методы, применяемые в многокрите­риальной оптимизации, отнюдь не исчерпываются теми методами, которые описаны в этой главе (см. список литературы в конце главы). — Прим. ред.

Глава 8. Целевое программирование

1. Налоговые поступления должны составить не менее 16 миллионов долларов от всех баз налогообложения.

2. Налог с розничных продаж не может превышать 10% от суммы всех собирае­мых налогов.

3. Налог с оптовых продаж не может превышать 20% от суммы всех налогов.

4. Налог на бензин не может превышать 2 центов за галлон.

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

550а_д + 35х_р + 55л₀ + 0,075х_в > 16 (суммарные налоговые поступления) 35х_р < 0,1(550х_и + 35л_р + 55х₀ + 0,075*,,) (налог на розничную торговлю) 55х_с < 0,2(550х_н + 35х_р + ЬЪх_о + 0,075х„) (налог на оптовую торговлю) х_е < 2 (налог на бензин) *„> V х_о, х₆ > 0.

После упрощения получаем три ограничения.

550х„ + 35х_р + ЪЬх₀ + 0,075х_б > 16, о5х_н - 31,5х_р + 5,5л:,, + 0,0075*,, > 0, 110лг„ + 7х_р - 44*„ + 0,015дг₉ > 0. х_б<2,

*„> *_Р> ^Хо> ^Хб * °-

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

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

550х„ + 35х_р + ЬЬх₀ + 0,075х_е + 5,⁺ - j" = 16, 55х„ - 31,5х_р + 5,5х₀ + 0,0075х„ + - s; = 0, 110х„ + 7х_р - 44х_о + 0,015х_б + ^ - s'₃ = 0.

*6 ^{+ S}4 ~ ^S4 = ².

х_н,х_р,х_о,х_в>0, s*, s~ >0, i=l,2, 3,4.

Неотрицательные переменные s* и s. называются отклоняющими, поскольку они

показывают отклонение значений левых частей ограничений от соответствующих величин правых частей этих же ограничений.

8.1. Формулировка задачи целевого программирования

Отклоняющие переменные и s. зависимы по определению, поэтому они обе од­новременно не могут быть базисными. Это означает, что на любом этапе решения задачи одним из симплексных методов только одна из пары отклоняющих пере­менных может принимать положительное значение. Если исходное i-e ограничение является неравенством типа "<" и s* > 0, то это ограничение выполняется. Если же

s. > 0, то данное ограничение не выполняется. Таким образом, определенные зна­чения отклоняющих переменных s* и j~ либо соответствуют i-e ограничению, либо