Оптимальное решение прямой задачи 16.1

№ п/п (О

Базисные переменные

Номера ограничений

(для дополнительных

переменных)

А_П

(значение

базисных

переменных)

(осн.)

Коэффициенты замещения

А_я (х_А) (изб. в огр. 4)

Индексная строка

115. Оптимальное решение двойственной задачи 16.1*

№п/п (/)

Базисные переменные

Номера ограничений

(для дополнительных

переменных)

(значение

базисных

переменных)

(осп.)

Коэффициенты замещения

(изб. в огр. 1)

(изб. в огр. 2)

1 у₂(осн.) 5000 -

2 у₇ (изб.) — 3

3 уц (изб.) - 4

4 у; (осн.) -24000 -Индексная строка (Щ — В^

80 150 1, 25

1, 25 770000

0, 04

-0, 8

-0, 0033

-0, 0033 -520

0, 4

-2

-0, 0021

-0, 0021 -920

0, 0042

0, 0042 -100

-0, 04

-0, 2

-0, 0008

-0, 0008 -380

*В соответствии с (16.15) и значениями у'₄, у% из таблицы получаем у₄ — -1, 25.

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

Примем во внимание следующие факты:

элементы индексной строки последней симплекс-таблицы прямой задачи, соответствующие базисным переменным (в табл. 114 не показаны), равны нулю;

значения небазисных переменных двойственной задачи также равны нулю;

в каждое ограничение прямой задачи в стандартной форме входит точно одна дополнительная переменная (остаточная или избыточная) и с этим же ограничением ассоциирована одна ос­новная переменная двойственной задачи (см. систему 16.12). Сле­довательно, существует попарное соответствие между дополни­тельными переменными прямой задачи и основными перемен­ными двойственной задачи: х₄—> у₄ (4-е ограничение прямой за­дачи); х₅-> У] (1-е ограничение); х₆ -> у₂ (2-е ограничение); х₇ -» у₃ (3-е ограничение);

значения целевых функций 7, (прямой) и Ж (двойственной) задач в оптимуме совпадают.

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

(2₄ - С₄) = -у₄ = 1, 25; (2Г₅ - С₅) = у, = 0;
(2₆-С₆)=у₂ = №, (2" ₇-С₇)=>; з = 0. (16.16)

Дальнейшие выводы строятся на анализе выражения для це­левой функции двойственной задачи. Запишем его для задачи 16.1 в общем виде:

У/= Ь_ху_{ + Ь₂у₂ + Ь_ъу_ъ + Ь₄у₄, (16.17)

где в качестве коэффициентов при основных переменных двой­ственной задачи используются правые части ограничений пря­мой задачи — Ь„ /'= 1,..., 4, то есть уровни ресурсов, которыми об­ладает хозяйство, и уровни плановых заданий по производству отдельных видов продукции.

Для того чтобы прямая и двойственная целевые функции со­впадали в оптимуме не только по численному значению, но и по единицам измерения, необходимо, чтобы в выражении (16.17) каждая двойственная переменная имела размерность [у, ] =

= [руб.]/[единица измерения соответствующего ресурса или пла­нового задания], то есть фактически являлась «ценой» данного ресурса или планового задания. Например, у₂ является «ценой» ресурса Ь₂, то есть органических удобрений, у₄ является «ценой» планового задания по производству зеленой массы многолетних трав (Ь₄).

В литературе такие «цены» получили название скрытых или теневых. Впервые они были исследованы Л. В. Канторовичем, который называл их объективно обусловленными оценками.

В целом с учетом (16.16) можно констатировать, что:

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

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

В соответствии с (16.16) элементы индексной строки прямой задачи часто называют двойственными оценками. Рассмотрим со­держание этих оценок более детально.

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

В рассматриваемой задаче 16.1 двойственная оценка ресурса органических удобрений составляет 80 руб. за 1 т, то есть при увеличении ресурса органических удобрений на 1 т прибылI, увеличивается на 80 руб. Это полностью согласуется с тем фак­том, что органические удобрения являются дефицитным ресур­сом, так как соответствующая остаточная переменная является небазисной. В то же время недефицитные ресурсы (пашня и трудовые ресурсы) имеют нулевые двойственные оценки, то л есть изменения в наличии этих ресурсов (в определенных пре­делах) не сказываются на значениях целевой функции. Двой­ственная оценка планового задания по производству зеленой массы многолетних трав составляет 1, 25 руб. за 1 ц, то есть уие личение их производства на 1 ц приведет к снижению прибыли на 1, 25 руб.

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

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

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

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

Принципиальная особенность любой двойственной оценки заключается в том, что она отражает влияние на процесс произ­водства не только данного ресурса, но и представляет собой ин­тегрированный показатель его влияния в комплексе со всеми ос­тальными. Фактически двойственные оценки формируются под влиянием всех факторов, определяющих постановку задачи, — типов ограничений, коэффициентов при неизвестных в целевой функции и в ограничениях, правых частей ограничений. Можно сказать, что реальные рыночные цены на данные виды ресурсов или производимую продукцию являются только одной — «види­мой» составной частью факторов формирования двойственных оценок. Это объясняет другое наименование двойственных оце­нок—«скрытые цены».

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

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

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

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

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

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

В заключение данного раздела дополнительно проанализиру­ем экономическое содержание двойственных оценок, основыва­ясь на теореме равновесия (Ларченко Е. Г. Вычислительная тех­ника и экономико-математические методы в землеустройстве. — М.: Недра, 1978.— С. 295). Рассмотрим случай, когда в задаче имеются только ресурсные ограничения (в соответствии с приня­тыми обозначениями заданные объемы ресурсов — это А,, /= \,..., т). Согласно теореме равновесия в оптимальных решени­ях прямой и двойственной задач соответствующие двойствен и 1.1 с оценки, то есть значения двойственных переменных у, по отно­шению к прямой задаче и значения переменных ху по отноше нию к двойственной задаче, равны нулю при выполнении следу ющих условий:

1) у(°)=0, как только X а»1 ° < А/, и наоборот;

2) х^=0, как только Ё %у^< с, -, и наоборот.

Символ (о) при переменных указывает на оптимальность ре­шений. Обратите внимание на то, что в неравенствах использо­ваны знаки строгого неравенства.

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

т..

2., ОуХу _ общий объем использования /-го ресурса во всех отраслях хозяйства;

Ь^иуУ_{ _ затраты на единицу продукции ву-и отрасли хозяи-

1=1

ства.

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

Во-первых, если по оптимальному плану имеется недоисполь-

т,.

чованный ресурс (X ^ау^х) < ^) и, значит, соответствующая оста­точная переменная находится в базисе, то цена на этот ресурс в < кшном хозяйстве падает до нуля. Расходование остатка этого ре­сурса может иметь смысл только при увеличении ресурсов, нахо­дящихся в дефиците. Положительные цены имеют лишь те ре­сурсы, которые лимитируют дальнейшее развитие производства. Например, если недоиспользуются пашня и трудовые ресурсы, а денежно-материальные средства израсходованы полностью, то положительную цену будет иметь только ресурс, указанный пос-иедним. В рассмотренном выше примере (см. задачу 16.1, табл. I 14) положительную цену имел только один ресурс — органичес­кие удобрения.

Во-вторых, если затраты на производство у'-го продукта пре-

пышают получаемый от него доход (Х⁰//), ^{> с}/)> то соответству-

/=1 „

ющаяу-я отрасль исключается из оптимального плана. В указан­ном примере такой отраслью является производство зеленого го­рошка (/'= 3, см. табл. 114).

Таким образом, использование двойственной задачи позволя­ет:

осуществить анализ и контроль решения прямой задачи;

оценить оптимальность любого базисного решения (по дан­ным индексной строки);

облегчить решение задачи при числе ограничений, значитель­но превышающем число переменных (заменив прямую задачу двойственной);

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

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

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

16.5. ПРЕДЕЛЫ УСТОЙЧИВОСТИ ОПТИМАЛЬНОГО РЕШЕНИЯ ПРИ ИЗМЕНЕНИИ КОЭФФИЦИЕНТОВ ЦЕЛЕВОЙ ФУНКЦИИ

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

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

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

Сначала рассмотрим изменение коэффициентов целевой функ­ции при переменных, входящих в базис оптимального решения пря­мой задачи. Допустим, например, что коэффициент при пере­менной х_{ в целевой функции I (16.11) изменяется следующим образом:

С[=С, +Д_С, (16.18)

где А_с — изменение коэффициента, которое может быть как положительным, так и отрицательным.

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

(4- С_}у = (3- С, -) + АуД_с, у > 0, (16.19)

где Л_4у—коэффициенты замещения, расположенные в симплекс-таблице (см. табл. 114) в строке, соответствующей базисной переменной х_ь то есть в 4-й строке.

Таким образом, формула (16.19) позволяет определить новые значения как целевой функции 2'₀^={2^-С^)', так и всех двой­ственных оценок небазисных переменных: {2_} — С])' при у > 1. При этом так как рассматриваемое изменение задачи не затраги­вает структуры последней симплекс-таблицы, элементы индекс­ной строки, соответствующие базисным переменным (в после­дней симплекс-таблице они не показаны), сохраняют нулевые тачения.

Схему рассуждений, приводящих к формуле (16.19), кратко поясним следующим образом.

Изменение коэффициента С_х в целевой функции 2 одновре­менно означает идентичное изменение правой части первого ог­раничения системы ограничений (16.14) двойственной задачи. Следовательно, вариацию А_сиз формулы (16.18) можно рассмат­ривать как изменение «планового задания» в двойственной зада-

че, соответствующего этому ограничению (тип ограничения — «>»). В то же время если решение двойственной задачи рассмат­ривать как обычное решение симплексной задачи (16.13)— (16.16), то результатом указанного изменения правой части пер­вого ограничения будет обычная корректировка оптимального решения двойственной задачи за счет введения в оптимальный план избыточной переменной у₅ = А_с (см. табл. 115). Как извест­но, в процессе такой корректировки будут меняться базисные переменные двойственной задачи и значение целевой функции Ж При этом новые значения базисных переменных и целевой функции будут определяться с использованием коэффициентов замещения и элемента индексной строки таблицы 115, соответ­ствующих избыточной переменной у₅. Теперь остается вспом­нить, что:

каждая базисная переменная двойственной задачи соответ­ствует определенной двойственной оценке прямой задачи;

в оптимуме значения целевых функций прямой и двойствен­ной задач совпадают.

Если учесть, что между множеством чисел столбца у₅ после­дней симплекс-таблицы двойственной задачи, включая элемент индексной строки, и числами 4-й строки последней симплекс-таблицы прямой задачи, включая элемент из столбца А®, суще­ствует взаимно однозначное соответствие с точностью до изме­нения знака на обратный (ср. табл. 114 и 115), то из формул (16.1) и (16.2) непосредственно вытекает формула (16.19).

Допустимые пределы изменений величины А_с (в рамках кото­рых структура симплекс-таблицы не меняется) можно опреде­лить из тех же соображений, воспользовавшись уже рассмотрен­ным выше алгоритмом ввода в оптимальный план избыточной переменной. Однако возможен и более прямой путь, которым мы и воспользуемся.

Из правила определения оптимальности симплекс-таблицы (и задачах на максимум — неотрицательность элементов индексной строки) следует, что при применении соотношения (16.19) новые значения (2} — С,)' приу> 1 не должны быть отрицательными. Та­ким образом, в случае максимизации целевой функции для любо­го/^ 1 должно выполняться условие

(2_} - С]) + М} А_с^ 0. (16.20)

Следовательно, для определения пределов допустимых изме­нений Д_с необходимо разделить (2} — С-) на соответствующие не­нулевые значения Л₄у и частные взять с обратным знаком. Среди положительных частных от такого деления нужно найти наи­меньшее (обозначим его 0^_т), а среди отрицательных — наи меньшее по модулю (обозначим его Цп\п)- Затем следует прове-

рить, не превышает ли значение В_тт по модулю коэффициент

С_ь и если так, положить Д~_{; п}=-С1. Такое действие необходимо, чтобы предотвратить появление отрицательного коэффициента удельной прибыли по отрасли хозяйства, соответствующей пере­менной х_{ (см. 16.18). В результате получим следующее ограниче­ние:

Очевидно, что если среди коэффициентов Ац нет отрицатель­ных, то вариация Д_с может быть сколь угодно большой положи­тельной, а если нет положительных — должно выполняться усло­вие Я_т1_П=-С,.

Пусть в задаче 16.1 чистый доход от реализации томатов уменьшается с 2000 до 1500 руб. с 1 га, то есть А_с= —500. Опреде­лить, как при этом изменяются оптимальное значение чистого дохода, двойственные оценки неэффективной отрасли (произ­водство зеленого горошка), дефицитного ресурса (органические удобрения) и критического планового задания (по выращиванию многолетних трав).

Учитывая, что меняется коэффициент С₂ при переменной х₂ (см. целевую функцию 16.11), для определения допустимых зна­чений А_с разделим элементы индексной строки на ненулевые ко­эффициенты замещения, стоящие в строке, соответствующей переменной х₂ (см. табл. 114). Используя полученные результаты, на основании рассмотренного выше алгоритма оценим допусти­мые пределы изменений С₂:

-2000 < Д_С< 750 (руб. с 1 га).

Таким образом, предполагаемое изменение чистого дохода от реализации томатов находится в допустимых пределах. Исполь­зуя формулу (16.19), получим:

чистый доход по хозяйству в целом уменьшится на 190 000 руб.;

скрытая цена (двойственная оценка) производства зеленого горошка уменьшится на 100 руб. с 1 га;

скрытая цена органических удобрений уменьшится на 20 руб. за 1 т;

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

Теперь следует рассмотреть случай, когда изменяется коэффи­циент в целевой функции при небазисной переменной — например, переменной хз в задаче 16.1 (см. табл. 114). Пусть

Сз=с₃+л_с,

(16.21)

где Дс— вариация коэффициента, которая может принимать как положительные, так и отрицательные значения.

В данном случае это приведет к изменению только элемента индексной строки, соответствующего рассматриваемой перемен­ной:

(2₃-С₃)' = (2₃-С₃)-Д_С. (16.22)

Потребовав, чтобы новое значение этого элемента не было отрицательным, получим следующее ограничение на допустимые изменения С₃ (для случая максимизации целевой функции):

-С₃< Д_с< (2з-С₃). (16.23)

Пусть в задаче 16.1 чистый доход от реализации зеленого го­рошка увеличивается с 250 до 350 руб. с 1 га, то есть Д_с= 100. Оп­ределить, как при этом изменится скрытая цена этой неэф­фективной отрасли.

Учитывая, что меняется коэффициент при небазисной пере­менной х₃ (см. целевую функцию 16.11), получим следующие до­пустимые пределы его вариации:

-250< Л_с< 150(руб. с 1га).

Таким образом, предполагаемое изменение чистого дохода от реализации зеленого горошка находится в допустимых пределах. Используя формулу (16.22), получим, что скрытая цена произ­водства зеленого горошка уменьшится на 100 руб. с 1 га. При этом другие двойственные оценки и чистый доход по хозяйству в целом не изменятся.

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

А_С> (7₃-С₃),

то есть если в данном конкретном примере коэффициент удель­ной прибыли по зеленому горошку (С₃) будет больше 400 руб. с 1 га. Для иллюстрации этого утверждения в таблице 116 приведс-

но оптимальное решение задачи 16.1 при значении коэффициен­та С₃ = 410.

116. Оптимальное решение задачи 16.1 при увеличении удельной прибыли по зеленому

горошку до 410 руб. с 1 га

№ п/п (/)

Базисные перемен­ные

С, -

Номера ограниче­ний (для дополни­тельных перемен­ных)

А® (значения базисных перемен­ных)

Коэффициенты замещения

Л (*й) (ост. в огр. 2)

1 х₅ (ост.) — 1

2 л:, (осн.) 2000 -

3 х₃(осн.) 410 -

4 х, (осн.) 100 -Индексная строка (2^— С,)

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

увеличился чистый доход хозяйства в целом на 4750 руб.;

более полно стала использоваться пашня (уменьшилась оста­точная переменная х$, соответствующая 1-му ограничению);

теперь полностью исчерпаны трудовые ресурсы (остаточная переменная х-], соответствующая 3-му ограничению, перешла в число небазисных);

уменьшилась площадь пашни под томатами (переменная х₂).

16.6. АЛЬТЕРНАТИВНЫЕ РЕШЕНИЯ РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ

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

Задача 16.2. В области имеется 5 сахарных заводов и 9 свекло­сеющих хозяйств, снабжающих эти заводы сырьем. Найти такой нариант закрепления хозяйств за сахарными заводами, при кото­ром общая стоимость доставки свеклы будет минимальной. Мощности заводов по переработке (т): 1—19 800, II — 8040, III — 5200, IV —2000, V—1000. Дополнительная исходная информа­ция дана в таблице 117.