Исходные данные к задаче 17.1

Пашня

Пастбище улучшенное

Пастбище

Сенокос

Площадь

угодий,

пригодных

для трансфор­мации, га

Пастбища

1юлота

Чистый доход, руб. с 1 га

Чатраты труда, чел.-дней Затраты денежно-материаль­ных средств, руб. на 1 га Коэффициенты эффектив­ности капиталовложений

-9, 5

Задача формулируется следующим образом. Целевая функция:

2" = 164x1 + 49х₂ + 36х₃ + 40х₄ -> пгах.

Ограничения:

по общей площади существующих пастбищ:

Х! + х₂< 592, 8; по площади пастбищ, пригодных для вовлечения в пашню:

х, < 54, 8;

по общей площади болот:

х₃+ х₄< 6, 6;

по трудовым ресурсам:

2х, + 2х₂ + 20х₃ + Юх₄ < 2500;

по затратам денежно-материальных средств:

40Х] + 27х₂ + 450х₃ + 115х₄ < 25 000;

по эффективности капиталовложений:

-97х! + 9х₂+14х₃-9, 5х₄< 0.

Условия неотрицательности переменных:

Х! > 0; х₂> 0; х₃> 0; х₄> 0.

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

164х, + 49х₂ + 36х₃ + 40х₄ + 0х₅ + 0х₆ + 0х₇ + 0х₈ + 0х₉ + 0х₁₀ -»шах.

х± + х₂ +х₅ =592, 8;

х₍ +Хб = 54, 8;

х₃ +х₄ +Х7 = 6, 6;

2x1 + 2х₂ + 20х₃ + 10х₄ +х₈ =2500;

40х[ + 27х₂ + 450х₃ + 115х₄ +х₉ = 25 000;

-97х! + 9х₂ + 14х₃ - 9, 5х₄ +х_]0 = 0;

123. Исходная симплекс-таблица задачи 17.1

В данной таблице отсутствуют столбцы небазисных перемен­ных и контрольные столбцы сумм а_/5,..., а_по; %ау. Она содержит

следующие сведения: 1

/ — номер строки;

Ъ₁ — базисные переменные (в первоначальном плане базисны­ми являются дополнительные переменные);

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

а_ю — свободные члены системы ограничений;

ау — коэффициенты системы ограничений при небазисных переменных ху

В самой верхней ненумерованной строке таблицы записывают коэффициенты су целевой функции при соответствующих пере­менных Ху В индексной строке в столбце а_ю записывают значе­ние целевой функции, соответствующее исходному плану:

т

^0=Е^сЛ=0-592, 8+0-54, 8+0-6, 6+0-2500+0-25000+0-0=0,

/=1

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

т Ау - Су = 2и С; С1у — Су / = 1

т

Так как в исходной симплекс-таблице значения Х^с/%⁼^ (^так

как с₍- = 0), то в индексной строке по столбцам базисных пере­менных записывают коэффициенты целевой функции с обрат­ным знаком (—с;).

Например, для столбца а_п: 2₁-С₁ = [1-0+1-0 + 0-0 + 2-0 + 40-0 + (-97) • 0] - 164 = -164.

Далее принимают следующий алгоритм.

1. Определяют ключевой столбец к; при решении задачи на максимум это столбец, который содержит в индексной строке наименьший отрицательный (то есть наибольший по модулю из отрицательных) коэффициент. В нашем примере это столбец а_{п (}7, -С, = -164).

2. Выбирают ключевую строку / и ключевой элемент а_1к:

тт^=^-(о_Л> 0).

' % ^а1к

В нашем примере ключевой является вторая строка таблицы 123. Элемент, находящийся на пересечении ключевых столбца и строки, называют ключевым элементом. В нашем примере это коэффициент а_/к = я₂₁ = 1.

3. Заполняют следующую симплекс-таблицу (табл. 124).

124. Первая расчетная симплекс-таблица 17.1

Переменная х_ь соответствующая ключевому столбцу преды­дущей таблицы, становится базисной и ее записывают в столбце Ь_{ вместо переменной х₆, соответствующей бывшей ключевой строке. Остальные элементы столбца Ь_: остаются прежними. В столбце с, - записывают значения коэффициентов целевой функ­ции при новых базисных переменных (при х_{ — значение 164, ос­тальные равны 0).

В верхней ненумерованной строке бывшего ключевого столб­ца (в нашем примере 1-го) записывают коэффициент целевой функции (0) при переменной, выведенной из базиса (х₆), а в сле­дующей строке — обозначение коэффициента при этой перемен­ной (й/б). Остальные компоненты двух верхних ненумерованных строк переписывают из предыдущей таблицы.

Все остальные элементы новой таблицы вычисляют по обыч­ным формулам симплекс-метода. Сначала определяют элемент

а\_к, соответствующий ключевому элементу предыдущей таблицы:

В нашем случае он равен 1.

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

Элементы а\_к столбца, соответствующего бывшему ключево­му, вычисляют согласно выражению

В этом заключается отличие от полного симплекс-метода. Остальные элементы новой таблицы вычисляют по формуле

а'ц=а1^а\_ка_1у

Пользуясь ею для получения каждого из элементов с§ некото­рой строки / (1Ф1) новой таблицы, достаточно прибавить к соот­ветствующему элементу а_у предыдущей таблицы произведение

уже вычисленного элемента а'у этой строки на соответствующий

элемент а у ключевой строки предыдущей таблицы. Значение а$ можно вычислить также по формуле

В результате указанных преобразований получают первую расчетную симплекс-таблицу (см. табл. 124).

Например, значение а_{1> 0} в этой таблице будет определено так:

а_{1; 0} = 592, 8-54, 8- 1 = 538, 0.

4. По той же методике вычисляются вторая и все последую­щие таблицы (табл. 125, 126).

125. Вторая расчетная симплекс-таблица задачи 17.1

126. Третья (последняя) расчетная симплекс-таблица задачи 17.1

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

Как известно, решение задачи на максимизацию заканчивает­ся, если в индексной строке отсутствуют отрицательные величи­ны. В данном случае получаем оптимальный план х_{ = 54, 8; х₂ = 538, 0; х₃ = 0; х₄ = 6, 6; х₅ = х₆ = х₇ = 0.

5. Осуществляют контроль решения (промежуточный и окон­чательный).

Промежуточный контроль состоит в следующем:

значение целевой функции задачи на максимум после каждой итерации должно, по крайней мере, не уменьшаться, что соблю­дается в таблицах 124—126;

в столбце < з_ю не должно возникать отрицательных значений, так как в противном случае нарушается условие неотрицательно­сти переменных (наличие отрицательных значений в столбце а_/0 обычно говорит о том, что при решении задачи неправильно выбран ключевой элемент);

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

условиям задачи; поэтому при подстановке значений базисных переменных в уравнения канонической формы модели должны получаться строгие равенства (некоторые ошибки могут возни- < -кать вследствие округления).

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

54, 8 + 538, 0 + 0 = 592, 8;

54, 8 + 0 = 54, 8;

0 + 6, 6 + 0 = 6, 6;

2 ■ 54, 8 + 2 • 538, 0 + 20 ■ 0 + 10 • 6, 6 + 1248 = 2499, 6;

40 • 54, 8 + 27 • 538, 0 + 450 • 0 + 115 ■ 6, 6 + 7523 = 25 000;

-97 ■ 54, 8 + 9 ■ 538, 0 + 14 ■ 0 - 9, 5 ■ 6, 6 + 536, 3 = 0.

Расчеты показывают, что все условия задачи выполняются, что подтверждает правильность решения.

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

1. По формуле целевой функции:

т

^опт=Хс/аю=⁴9-538, 0+164-54, 8+40-6, 6=35613, 2.

/=1

2. Как обычный элемент симплексной таблицы:

-2" опт = 2п_Ред -Ь2= 35349, 2 - 6, 6(-40) = 35349, 2 + 264 = 35613, 2.

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

т т

Ес/^о^=±Х°|-оУ|.

где я₍'₀ — значения базисных переменных в контролируемой таблице; с, - — коэффи­циенты целевой функции при базисных переменных; а_ю — свободные члены ис­ходной системы условий (компоненты столбца о_я исходной таблицы); у_л — элемен­ты, находящиеся в индексной строке контролируемой таблицы в столбцах, соответ­ствующих /-м дополнительным переменным, то есть в столбцах а, „ +, -, где п — число основных переменных задачи.

т

Например, значение 2_0ПТ- Е^оЗ⁷/ будет вычисляться так:

(= 1

^опт =115- 54, 8 + 49 ■ 592, 8 + 40 • 6, 6 = 35613, 2.

Таким образом, значение целевой функции определено пра­вильно.

Решение землеустроительных задач симплексным методом по сокращенным таблицам с использованием искусственного базиса осуществляется по аналогичной методике (Задания и методичес­кие указания по применению вычислительной техники для реше­ния инженерно-экономических задач /Е. Г. Ларченко, М. И. Ко-робочкин, В. С. Бережнов. — М.: Недра, 1967. —С. 66—69).

17.2. ПРОБЛЕМА ВЫРОЖДЕННЫХ РЕШЕНИЙ

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

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

Следует учитывать, что даже если в исходных ограничениях задачи все свободные члены положительны (6, - > 0 для всех /), нельзя гарантировать, что последующие базисные решения не будут вырожденными. Не исключена возможность, что на неко­торой итерации /-й элемент столбца а_ю окажется равным нулю. Если одновременно с этим /-Й элемент столбца а_{! к}, подлежащего вводу в базис, окажется положительным, то минимальное из от­ношений элементов столбца о_/0 к соответствующим положитель­ным элементам столбца а_1к будет равно нулю. Тогда, хотя набор базисных переменных будет другим, целевая функция после пре­образования сохранит прежнее значение.

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

Способ преодоления вырожденности при решении землеуст­роительных задач симплексным методом описан Е. Г. Ларченко; по его методике, когда указанный минимум достигается для не­скольких значений индекса /, исключается та переменная, для которой достигается минимум соотношений а_л/а_1к, где /—ин­дексы строк переменных, которые участвуют в выборе.

Пусть, например, при базисных переменных х_ь х₂,..., х_т> 0 имеем

^д10 ₌ ^а20

^а\к ^а2к '

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

41 „ «21

^а\к ^а1к

Если минимальна по модулю первая из них, исключаем пере­менную х_1; если вторая —то х₂. Если же и они одинаковы, срав­ниваем отношения

«12 _и «22 «1А; «2Аг

и выбираем из них наименьшее. Такое сравнение проводится до тех пор, пока не будут получены неравные величины.

17.3. РОЛЬ ОГРАНИЧЕНИЙ В ФОРМИРОВАНИИ ОБЛИКА

ПРОИЗВОДСТВЕННЫХ ФУНКЦИЙ (НА ПРИМЕРЕ ЗАДАЧИ

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ)

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

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

Задача 17.2. В хозяйстве производятся молоко и зерно. Все молоко идет на продажу; 40 % зерна используется на корм скоту, 60 % идет на продажу.

Ресурсы хозяйства (варьируемые): х\ — площадь пашни, га; х₂ — трудовые ресурсы, чел.-ч; х₃ — запас кормов на пастбищах и сенокосах, ц корм, ед.; х₄ — количество мест для содержания ко­ров, гол.

Нормы трудозатрат: 5 чел.-ч на 1 га; 50 чел.-ч на 1 гол. Норма

кормления животных 80 ц корм. ед. на 1 гол. Урожайность зерно­вых 25 ц корм. ед. с 1 га. Продуктивность коров 4000 кг на 1 гол. Цена на зерно 10 руб. за 1 ц, молоко — 0, 2 руб. за 1 кг.

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

Введем основные переменные симплексной модели задачи 17.2:

^1 — площадь пашни под зерновыми, га;

%1 — поголовье коров, гол.

Тогда модель будет иметь вид

%\ ^^хъ

5^+50^ < х₂;

-10^ + 80^2 ^*з;

г < * ^(17Л)

^=0, 15^1+0, 8^2-*тах; ^> 0, ^₂> 0.

Напомним, что здесь 2Г— целевая функция (валовой продукт хозяйства в денежном выражении, тыс. руб.), а ограничения име­ют следующий смысл: 1-е — по площади пашни; 2-е — по трудо­вым ресурсам; 3-е — по кормам; 4-е — по количеству мест для со­держания коров.

Зафиксировав ресурсы Х\,..., х₄ и решив задачу симплекс-мето­дом, получим определенное оптимальное решение;

2 ⁼ 2опА^хЬ~-> ^х4)> ^1⁼^1 (^ХЬ-; ^Х4УЛ2⁼^> 2 (^ХЬ--> ^Х4)-

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

у=2_от(х_и..., х₄). (17.2)

Рассмотрим сначала случай фиксированных трудовых ресур­сов, запасов кормов на пастбищах и сенокосах и количества мест для содержания коров:

х₂ = 12 000 чел.-ч; х₃ = 2000 ц корм, ед.; х₄ = 110 гол.,

то есть ситуацию, когда переменным является только ресурс пашни (х,).

У1

О 500 х{ 1000 х/ 1500 2000 х]

Рис. 20. Зависимость оптимального значения целевой функции задачи от обеспеченности хозяйства пашней

Зависимость

у=2_от{х_х)\

Х2, х^, х^-сотХ >

(17.3)

полученная в результате решения серии задач линейного про­граммирования вида (17.1), каждая из которых соответствует оп­ределенному значению х_ь приведена на рисунке 20.

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

Проиллюстрируем это утверждение для случая, когда ресурс пашни х_{ находится в интервале от 1300 до 2400 га, например при X) = 1500 га. Для таких условий (с учетом зафиксированных ранее значений ресурсов х_ъ х_ъ х₄) область допустимых значе­ний, соответствующая модели (17.1), изображена на рисунке 21. Ресурс Х[ = 1500 га формирует в области допустимых значений грань ЕР. Линии уровня целевой функции Д^ь ^2) задачи ли­нейного программирования, показанные на рисунке штриховы­ми прямыми, ориентированы так, что оптимальной является вершина Е. Таким образом, сдерживающими ограничениями яв­ляются 1-е и 2-е и соответственно дефицитными ресурсами — пашня и трудовые ресурсы. Увеличение ресурса пашни должно приводить к сдвигу вершины Е вправо-вниз, а значит, к увеличе-

нию целевой функции. В то же время известно, что увеличение ресурса эквивалентно введению в план отрицательного значения остаточной переменной, связанной с этим ресурсом (в данном случае это переменная ^ — см. табл. 127). При таком введении ^₃ в план оптимальное значение целевой функции будет меняться в соответствии с двойственной оценкой этой переменной (скрытой ценой ресурса пашни):

■ ^опт =-2опт ~(%3 ~Сз)^3 =2опт -0, 07^з-

Учитывая, что |^₃| — это и есть приращение ресурса пашни, получим следующую формулу:

у=у₃+0Щх_{-х^),

где х, е [1300, 2400], у_ъ = 283,

показанную на рисунке 20 и отражающую линейный характер рассматриваемой производственной функции на интервале XI е [1300, 2400].

Обратим внимание также на то, что в области х₍е[1300, 24001 увеличение ресурса пашни приводит к относительно слабому ро­сту валовой продукции у. «Ответственным» за этот эффект пол­ностью является второе ограничение: из-за него при увеличении X) оптимальная вершина Е сдвигается по направлению, сильно отличающемуся от направления нормали к линии уровня целе­вой функции, что и приводит к слабому сдвигу линии уровня.

О \ 500 1000 \1500 \\ \ ^

^2=20 2=190" ' 2=283" ^к2=297

Рис. 21. Область допустимых значений задачи при х1 — 1500

127. Последняя симплекс-таблица задачи 17.1 при х₁ = 1500 га, х_г = 12 000 чел.-ч, х, = 2000 ц корм, ед., х₄ = 110 гол.

1 г, ₆(ост.) 4 20 0 0 ОД -0, 02 0 1

2 уост.) 3 9800 0 0 10 -1, 6 1 0

3 ^(осн.) - 90 0 1 -0, 1 0, 02 0 0

4 ^(осн.) - 1500 10 1 0 0 0

(.2-9 297 0 0 0, 07* 0, 016** 0 0

* Скрытая цена ресурса пашни.

** Скрытая цена трудовых ресурсов.

Несколько иная ситуация складывается при х, е[0, 680]. В этом случае, например, при х_{ = 600 область допустимых значе­ний задается фигурой АВЕ'Т" (рис. 22), а оптимальной является вершина Е". Вторым связывающим ограничением (наряду с ог­раничением по площади пашни) является ограничение не по трудовым ресурсам, а по кормам, что приводит к более выгодно­му смещению оптимальной вершины Е" и соответственно к большей скорости роста целевой функции при увеличении пло­щади пашни. Скрытая цена пашни при этом составляет 0, 25 тыс. руб. на 1 га (см. табл. 128 и рис. 22, а также рис. 20 —участок х, е[0, 680]).

Анализ симплексной задачи объясняет и тот факт, что при X] > 2400 га рост рассматриваемой производственной функции прекращается — наблюдается эффект насыщения, характерный для реальных зависимостей обобщенных экономических показа­телей (валовой продукт и т. п.) от ресурсных факторов. Действи­тельно, при X] > 2400 га линия, соответствующая первому ограни­чению модели (17.1), вообще выходит за пределы области допус­тимых значений, которая превращается в фигуру АВСОР' (это нетрудно видеть, например, по рис. 21). В геометрической интер­претации оптимальной в этом случае будет вершина Г', причем сдерживающим будет только второе ограничение — по трудовым ресурсам, избыток же пашни (свыше 2400 га) нельзя использо­вать, что и определяет нулевое значение дополнительного про­дукта.

Подобным же образом на основе анализа симплексной задачи может быть установлена зависимость у от любого другого ресурса (производственного фактора).

Так, например, нетрудно видеть, что при х_{~ 1500 га, х₂ = = 12 000 чел.-ч, х₄= ПО гол. ресурс кормов на пастбищах и сено-

О \ 500 1000\ 1500
\
2=20 " -2=170

Рис. 22. Область допустимых значений задачи при лг, < 680

косах (х₃) никак не влияет на валовой продукт хозяйства. Это ясно из геометрического представления задачи (см., например, рис. 21).

Поскольку при указанных значениях х_ь х₂, х₄ оптимальной является вершина Е, то даже при уменьшении х₃ до нуля со­ответствующая третьему ограничению грань области допусти­мых значений (ВС) сдвинется вправо незначительно (пройдет через точку А), что не поменяет характер оптимального реше­ния — ресурс х₃ не станет дефицитным и, следовательно, бу-

128. Последняя симплекс-таблица задачи 17.1 при х₁ = 600 га, х_г х_г = 2000 ц корм, ед., х₄ = ПО гол.