Бережная_Матметоды моделирования эк cистем

	Управляемые	Оптимальные
	переменные	значения
	^ 1	2,4
	Х2	1,4
1	7	12,8

Таблица 7.19 Решение

Объем производства продук­ ции IJi должен быть равен 2,4 ед. в сутки Объем производства продук­

ции Яг должен быть равен 1,4 ед. в сутки

Доход от реализации продук­ ции будет равен 12,8 д. е.

в сутки

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

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

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

Положительное значение выравнивающей переменной указы­ вает на неполное использование соответствующего ресурса, т. е. данный ресурс является недефицитным. Если же выравнивающая переменная равна О, то это свидетельствует о полном потреблении соответствующего ресурса. Из сводной табл. 7.20 видно, что ресур­ сы 2 и 4 связаны с запасами сырья В и возможностями сбыта про­ дукции IT2. Поэтому любое увеличение их запасов сверх установ-

230

Ресурс

Сырье А Сырье В

Превышение объема производ­ ства продукции Щ по отноше­ нию к объему производства продукции ITj

Спрос на продукцию Яг

		Таблица 7.20
	Выравнивающая	Статус ресурса
	переменная
	У1 = 0	Дефицитный
		Недефицитный
		Дефицитный
	У, = 0,6	Недефицитный

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

Ресурсы, увеличение запасов которых позволяет улучшить ре­ шение (увеличить доход), — это сырье А и возможности по сбыту продукции III, поскольку из оптимальной симплекс-таблицы (табл. 7.18) видно, что они дефицитные. В связи с этим логично поставить вопрос: какому из дефицитных ресурсов следует отдать предпочтение при вложении дополнительных средств на увеличе­ ние их запасов, с тем чтобы получить от них максимальную отда­ чу? Ответ на этот вопрос будет дан в следующем разделе этой гла­ вы, где рассматривается ценность различных ресурсов.

Ценность ресурса. Ценность ресурса характеризуется величиной улучшения оптимального значения Z, приходящегося на единицу прироста объема данного ресурса. Графическая интерпретация это­ го определения применительно к условиям задачи об ассортименте продукции была дана в подразд. 7.4 (вторая задача на чувствитель­ ность). Графический анализ показывает, что ценность ресурсов 1, 2, 3 и 4 равна:

С/] = 1,4 д. е. на единицу прироста запасов ресурса сырья А;

U2 = О, f/4 = 0;

f/3 = 0,2 д. е. на единицу прироста превышения производства продукции Я^ по отношению к объему производства про­ дукции П2.

Эта информация представлена в оптимальной таблице (табл. 7.18). Обратим внимание на значения коэффициентов Z-уравне- ния, стоящих при переменных начального базиса у^, У2, у^ и у^. Значения указанных коэффициентов (1,4; 0; 0,2; 0) в точности со­ ответствуют значениям t/i; Ui, Uy, U^.

231

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

Рассмотрим Z-уравнение оптимальной симплекс-таблицы ре­ шения задачи об ассортименте продукции:

Z = 12,8 - (1,4 • у^-^0^у2 + 0,2'Уг-^0- у^).

Положительное приращение переменной Ух относительно ее текущего нулевого значения приводит к пропорциональному уменьшению Z, причем коэффициент пропорциональности равен 1,4 д. е. Однако из первого ограничения модели следует

2x1 + 3^2 + 3^1 = 9,

т. е. увеличение Ух эквивалентно снижению запаса ресурса 1 (сырья А), Отсюда следует, что уменьшение запаса первого ресурса вызы­ вает пропорциональное уменьшение целевой функции Zc коэффи­ циентом пропорциональности, равным 1,4 д. е. Аналогичные рас­ суждения справедливы и для ресурса 3.

В отношении ресурсов 2 и 4 было установлено, что их ценность равна О (1/2= 1/4 = 0), Этого и следовало ожидать, так как ресурсы 2 и 4 оказались недефицитными. Такой результат получается вся­ кий раз, когда соответствующие выравнивающие переменные име­ ют положительное значение.

Несмотря на то что ценность различных ресурсов, определяемая значениями переменных U^y была представлена в стоимостном (д. е.) выражении, ее нельзя отождествлять с действительными ценами, по которым возможна закупка соответствующих ресурсов. На самом де­ ле речь идет о некоторой мере, имеющей экономическую природу и количественно характеризующей ценность ресурса только относи­ тельно полученного оптимального значения Z. При изменении огра­ ничений модели соответствующие экономические оценки будут ме­ няться даже тогда, когда оптимизируемый процесс предполагает при­ менение тех же ресурсов. Поэтому при характеристике ценности ре­ сурсов экономисты предпочитают использовать тaкиQ^ термины, как теневая цена или двойственная оценка. Заметим, что теневая цена характеризует интенсивность улучшения оптимального решения Z. Однако при этом не фиксируется интервал значений увеличения за­ пасов ресурсов, при которых интенсивность улучшения целевой функции остается постоянной. Для большинства практических ситу­ аций логично предположить наличие верхнего предела увеличения запасов, при превышении которого соответствующее ограничение становится избыточным, что в свою очередь приводит к новому ба-

232

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

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

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

Результаты вычислений элементов столбца «свободные члены» сведены в табл. 7.21:

				Таблица 7.21
	Уравнение	Значения элементов столбца «свободные члены»
		Начальная	Оптимальная
		симплекс-таблица	симплекс-таблица
	Z	0	12,8 + 1,4 • Ai
	1	9 + Ai	2,4 + 0,2 • Ai
	2	13	3 -	1 • А,
	3	1	0,6 -	0,2 . Ai
	4	2	1,4 -f- 0,2 . А,

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

1)постоянной;

2)члеца, линейно зависящего от Ai.

Постоянные соответствуют числам, которые фигурируют в оп­ тимальной симплекс-таблице до введения А^ в столбце «свободные члены». Коэффициенты при Aj во вторых слагаемых равны коэф­ фициентам при У1 в оптимальной симплекс-таблице.

233

Заметим, что при анализе изменений в правых частях второго, третьего и четвертого ограничений нужно пользоваться коэффици­ ентами при переменных У2, Уз^ УА соответственно.

Так как введение Aj сказывается лишь на правой части ограни­ чений (на элементах столбца «свободные члены»), изменение запа­ са ресурса может повлиять только на допустимость решения. По­ этому Aj не может принимать значений, при которых какая-либо из базисных переменных становится отрицательной. Из этого следует, что величина Aj должна быть ограничена таким интервалом значе­ ний, при котором выполняется условие неотрицательности правых частей ограничений в результирующей симплекс-таблице, т. е.:

jci = 2,4 + 0,2			• Ai > 0;	(7.51)
^2 =	3 -	1 . Ai > 0;		(7.52)
У4 =	0,6	- 0,2	• Ai > 0;	(7.53)
X2= 1,4		+ 0,2	• Ai>0.	(7.54)

Для определения допустимого интервала изменения Aj рассмо­ трим два случая.

Случай 7: А1 > 0.

Соотношения (7.51) и (7.54) всегда выполняются при Aj > 0. Соотношения (7.52) и (7.53) определяют следующие предельные значения Ai! Aj < 3; А] < 3. Таким образом, все четыре соотноше­ ния выполняются при Aj < 3.

Случай 2: Ai < 0.

Соотношения (7.52) и (7.53) выполняются при Aj < 0. Соотно­ шения (7.51) и (7.54) справедливы при Aj > — 12; Aj > ~7 соответ­ ственно.

Таким образом, оба соотношения справедливы при А] > —7. Объединяя результаты, полученные для обоих случаев, можно

сделать вывод, что при —7 < Aj < 3 решение рассматриваемой сис­ темы всегда будет допустимым. Любое значение Aj, выходящее за предел указанного интервала (т.е. уменьшение запаса сырья А бо­ лее чем на 7 единиц или увеличение более чем на 3 единицы), при­ ведет к недопустимости решения и новой совокупности базисных переменных.

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

234

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

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

Чтобы показать, как выполняются соответствующие вычисле­ ния, положим, что доход, получаемый с единицы продукции Я^, изменяется от 3 до 3 + 5i, где б^ может быть как положительным, так и отрицательным числом. Целевая функция в этом случае при­ нимает следующий вид:

2тах = (3 + 5i)Xi + 4X2.

Если воспользоваться данными начальной симплекс-таблицы и выполнить все вычисления, необходимые для получения оптималь­ ной симплекс-таблицы, то последнее Zjnax-УРавнение будет выгля­ деть следующим образом:

	Свободные	Свободные	У\	Уг
	переменные	члены
	7	12,8 + 2,4 5i	1,4 4- 0,2 5,	0,2 + 0,6 8i

Это уравнение (строка целевой функции) отличается от Z-урав- нения до введения Sj только наличием членов, содержащих Ь^, Ко­ эффициенты при 5i равны коэффициентам при соответствующих переменных в Xj-уравнении (jcj-строка) симплекс-таблицы для по­ лученного ранее оптимального решения:

["^•^^ Свободные
^^^^ременные	Свободные	У\	Уъ
Базисные^"\^^^	члены
переменные ^^\,,^^
X,	2,4	0,2	0,6

Мы рассматриваем Xj-уравнение, так как коэффициент именно при этой переменной в выражении для целевой функции в началь­ ной симплекс-таблице изменился на Sj.

235

Оптимальные значения переменных будут оставаться неизмен­ ными при значениях Sj, удовлетворяющих условию неотрицатель­ ности (задача на отыскание максимума) всех коэффициентов при свободных переменных в Z-уравнении. Таким образом, должны выполняться следующие неравенства:

1,4 + 0,2 5i > 0;

0,2 + 0,6 5i > 0.

Из первого неравенства получаем, что Sj > - 7, а из второго сле­

дует, что 6i >—. Эти результаты определяют пределы изменения

коэффициента - - < 5] < -ьоо.

Таким образом, при уменьшении коэффициента целевой функ­

ции при переменной Xj до значения, равного 3 +	1 = 2-, или
V	•")

при его увеличении до +оо оптимальные значения переменных ос­ таются неизменными. Этот вывод совпадает с результатом, полу­ ченным в подразд. 7.4.

Следует отметить, что оптимальное значение Z будет изменять­

ся в соответствии с выражением (12,8 + 2,4 5i), где - - ^ S j <+оо.

Мы рассмотрели случай изменения коэффициента при базис­ ной переменной Ху В случае изменения коэффициента при сво­ бодной переменной в целевой функции происходит изменение ко­ эффициента только при данной переменной в оптимальной симп­ лекс-таблице. Рассмотрим в качестве иллюстрации случай, когда коэффициент при свободной переменной у^ (первая выравниваю­ щая переменная) изменяется от О до 52Выполнение преобразова­ ний, необходимых для получения заключительной симплекс-таб­ лицы, приводит к следующему результирующему Z-уравнению:

	Свободные	Свободные	У\	Уг
	переменные	члены
	Z	12,8	1,4 - 52	0,2

Из приведенного фрагмента заключительной симплекс-табли­ цы видно, что единственное отличие от Z-уравнения до введения

236

52 состоит в том, что коэффициент при >'з уменьшился на 62. Таким образом, коэффициент при свободной переменной в результирую­ щем Z-уравнении нужно уменьшить на ту же величину, на которую он увеличивался в исходном Z-уравнении.

7.8. Двойственные задачи линейного программирования

Взаимодвойственные задачи. Рассмотрим задачу об использова­ нии ресурсов. Пусть предприятие № 1 производит п видов продук­ ции и использует т видов сырь5^. Известна прибыль, получаемая с единицы продукции Cuj = 1, п. Известны технологические коэффи­ циенты Qip i = l,m, J = I, п. Требуется организовать производство так, чтобы предприятию была обеспечена максимальная прибыль. Сведем все исходные данные в табл. 7.22:

				Таблица 7.22
Цены	Запасы		Продукция
на ресурсы	сырья	Я,	Пг	Пп
^1	^1	^11	Д,2	0\п
		-	^22
	^2	^21
	От	От\	Cl	Сп
	Прибыль с	С\
	единицы
	продукции

Запишем в общем виде экономико-математическую модель задачи об использовании ресурсов. Для этого введем переменные Хр J = 1уП — количество продукции у-го вида. Тогда ограничения на сырье запишутся в виде

«11^1 + «12^2 + -	+ ^ 1 Л ^ «i;	(7.55)
^21X1 + ^22^2 + -	+^2/1^л ^ ^2;

Целевая функция, определяющая максимум прибыли, имеет

вид	+ С2Х2 + ... + с^„;	(7.56)
cjXi
Xj>QJ=	1,п.

237

По этим же исходным данным сформулируем задачу по пред­ приятию № 2.

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

1)общая стоимость ресурсов для предприятия № 2 должна быть минимальной;

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

Обозначим цены, по которым предприятие № 2 покупает ре­ сурсы у предприятия № 1, через «,-, / = \,т. Запишем экономикоматематическую модель для предприятия № 2 с учетом вышеука­ занных условий 1) и 2).

Целевая функция, определяюш;ая минимальную суммарную стоимость ресурсов, имеет вид

^min = ^\Щ + «2«2 + - + ^т^^т-

(7-57)

В соответствии с условием 2) запишем систему ограничений:

«11^1 +^21«2 +	-	+^ml«m^^i;
а^их + «22«2 +	-	+ ^ml^m ^ <^Ъ	(7.58)

Сравним математические модели задач (7.55), (7.56) и (7.57), (7.58):

1)число неизвестных одной задачи равно числу ограничений другой задачи;

2)матрица коэффициентов системы ограничений получается одна из другой путем транспонирования;

3)неравенства в системах ограничений имеют противополож­ ный смысл;

4)свободные члены системы ограничений одной из задач ста­ новятся коэффициентами целевой функции другой задачи, коэф­ фициенты целевой функции превращаются в свободные члены ог­ раничений;

5)целевые функции в задачах имеют противоположный смысл:

впервой - max, во второй - min.

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

238

в линейном программировании кроме симметричных двойст­ венных пар существуют несимметричные двойственные пары, ко­ торые имеют следующий вид:

основная задача

a^xi + «12X2 + ... + а^гР^п = *i;

			(7.59)
^max = CiXi + С2Х2 +		... + C^nl	(7.60)
Ху>0,у=Т7«;
двойственная задача
^max =	b^yi + *2V2 +	- + 1^тУт>	(7-61)
			(7.62)
^InVl +	^гпУг + - +	(^тпУт ^ ^д|-

Эти задачи отличаются от симметричной пары двумя особенно­ стями:

1) ограничения задачи (7.59)~-(7.60) выражены уравнениями вместо неравенств;

2) в задаче (7.61)-(7.62) отсутствуют условия неотрицательнос­ ти переменных ;;/, / = \,т.

Общее правило построения двойственной пары. К пяти призна­

кам, сформулированным ранее, необходимо добавить следующие: 1) в исходной задаче ограничения неравенства следует записы­ вать со знаком >, если целевая функция стремится к min, и со зна­

ком <, если целевая функция стремится к max;

2)каждому ограничению неравенства исходной задачи соответ­ ствует в двойственной задаче условие неотрицательности перемен­ ных У/ > 0;

3)каждому условию равенства соответствует переменная у^- без ограничения на знак, и наоборот: неотрицательным переменным х^ из основной задачи в двойственной задаче соответствуют ограниче­ ния неравенства, а неограниченным по знаку переменным соответ­ ствуют равенства.

239