![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Исходные данные к задаче 17.1
Пашня Пастбище улучшенное Пастбище Сенокос Площадь угодий, пригодных для трансформации, га
Пастбища 1юлота Чистый доход, руб. с 1 га Чатраты труда, чел.-дней Затраты денежно-материальных средств, руб. на 1 га Коэффициенты эффективности капиталовложений
-9, 5 Задача формулируется следующим образом. Целевая функция: 2" = 164x1 + 49х2 + 36х3 + 40х4 -> пгах. Ограничения: по общей площади существующих пастбищ: Х! + х2< 592, 8; по площади пастбищ, пригодных для вовлечения в пашню: х, < 54, 8; по общей площади болот: х3+ х4< 6, 6; по трудовым ресурсам: 2х, + 2х2 + 20х3 + Юх4 < 2500; по затратам денежно-материальных средств: 40Х] + 27х2 + 450х3 + 115х4 < 25 000; по эффективности капиталовложений: -97х! + 9х2+14х3-9, 5х4< 0. Условия неотрицательности переменных: Х! > 0; х2> 0; х3> 0; х4> 0. Перейдем к канонической форме записи задачи и составим по правилам определения первоначального базисного плана исходную сокращенную симплекс-таблицу (табл. 123): 164х, + 49х2 + 36х3 + 40х4 + 0х5 + 0х6 + 0х7 + 0х8 + 0х9 + 0х10 -»шах. х± + х2 +х5 =592, 8; х( +Хб = 54, 8; х3 +х4 +Х7 = 6, 6; 2x1 + 2х2 + 20х3 + 10х4 +х8 =2500; 40х[ + 27х2 + 450х3 + 115х4 +х9 = 25 000; -97х! + 9х2 + 14х3 - 9, 5х4 +х]0 = 0; 123. Исходная симплекс-таблица задачи 17.1
В данной таблице отсутствуют столбцы небазисных переменных и контрольные столбцы сумм а/5,..., апо; %ау. Она содержит следующие сведения: 1 / — номер строки; Ъ1 — базисные переменные (в первоначальном плане базисными являются дополнительные переменные); с, - — коэффициенты, с которыми базисные переменные входят в целевую функцию; аю — свободные члены системы ограничений; ау — коэффициенты системы ограничений при небазисных переменных ху В самой верхней ненумерованной строке таблицы записывают коэффициенты су целевой функции при соответствующих переменных Ху В индексной строке в столбце аю записывают значение целевой функции, соответствующее исходному плану: т ^0=ЕсЛ=0-592, 8+0-54, 8+0-6, 6+0-2500+0-25000+0-0=0, /=1 где при суммировании учитываются только базисные переменные. В остальных столбцах индексной строки записывают величины т Ау - Су = 2и С; С1у — Су / = 1 т Так как в исходной симплекс-таблице значения Хс/%=^ (так как с(- = 0), то в индексной строке по столбцам базисных переменных записывают коэффициенты целевой функции с обратным знаком (—с;). Например, для столбца ап: 21-С1 = [1-0+1-0 + 0-0 + 2-0 + 40-0 + (-97) • 0] - 164 = -164. Далее принимают следующий алгоритм. 1. Определяют ключевой столбец к; при решении задачи на максимум это столбец, который содержит в индексной строке наименьший отрицательный (то есть наибольший по модулю из отрицательных) коэффициент. В нашем примере это столбец ап (7, -С, = -164). 2. Выбирают ключевую строку / и ключевой элемент а1к: тт^=^-(оЛ> 0). ' % а1к В нашем примере ключевой является вторая строка таблицы 123. Элемент, находящийся на пересечении ключевых столбца и строки, называют ключевым элементом. В нашем примере это коэффициент а/к = я21 = 1. 3. Заполняют следующую симплекс-таблицу (табл. 124). 124. Первая расчетная симплекс-таблица 17.1
Переменная хь соответствующая ключевому столбцу предыдущей таблицы, становится базисной и ее записывают в столбце Ь{ вместо переменной х6, соответствующей бывшей ключевой строке. Остальные элементы столбца Ь: остаются прежними. В столбце с, - записывают значения коэффициентов целевой функции при новых базисных переменных (при х{ — значение 164, остальные равны 0). В верхней ненумерованной строке бывшего ключевого столбца (в нашем примере 1-го) записывают коэффициент целевой функции (0) при переменной, выведенной из базиса (х6), а в следующей строке — обозначение коэффициента при этой переменной (й/б). Остальные компоненты двух верхних ненумерованных строк переписывают из предыдущей таблицы. Все остальные элементы новой таблицы вычисляют по обычным формулам симплекс-метода. Сначала определяют элемент а\к, соответствующий ключевому элементу предыдущей таблицы: В нашем случае он равен 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; х2 = 538, 0; х3 = 0; х4 = 6, 6; х5 = х6 = х7 = 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. По формуле целевой функции: т ^опт=Хс/аю=49-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. При вычислениях с помощью как полных, так и сокращен т т Ес/^о=±Х°|-оУ|. где я('0 — значения базисных переменных в контролируемой таблице; с, - — коэффициенты целевой функции при базисных переменных; аю — свободные члены исходной системы условий (компоненты столбца оя исходной таблицы); ул — элементы, находящиеся в индексной строке контролируемой таблицы в столбцах, соответствующих /-м дополнительным переменным, то есть в столбцах а, „ +, -, где п — число основных переменных задачи. т Например, значение 20ПТ- Е^оЗ7/ будет вычисляться так: (= 1 ^опт =115- 54, 8 + 49 ■ 592, 8 + 40 • 6, 6 = 35613, 2. Таким образом, значение целевой функции определено правильно. Решение землеустроительных задач симплексным методом по сокращенным таблицам с использованием искусственного базиса осуществляется по аналогичной методике (Задания и методические указания по применению вычислительной техники для решения инженерно-экономических задач /Е. Г. Ларченко, М. И. Ко-робочкин, В. С. Бережнов. — М.: Недра, 1967. —С. 66—69). 17.2. ПРОБЛЕМА ВЫРОЖДЕННЫХ РЕШЕНИЙ Как и при решении транспортных задач, при использовании симплексного метода могут возникать вырожденные решения. В невырожденных задачах каждое базисное решение содержит ровно т положительных компонентов. Любая задача при наличии хотя бы одного нуля в правых частях ограничений будет вырожденной. В вырожденных задачах возникает опасность после некоторых итераций вновь вернуться к набору базисных переменных, который уже встречался. Тогда все планы, рассмотренные после этого, будут повторением последовательности предыдущих, что приведет к зацикливанию алгоритма, и оптимальное решение никогда не будет достигнуто. Несмотря на то что такая ситуация встречается редко, полезно знать способ преодоления вырожденности симплексной задачи. Следует учитывать, что даже если в исходных ограничениях задачи все свободные члены положительны (6, - > 0 для всех /), нельзя гарантировать, что последующие базисные решения не будут вырожденными. Не исключена возможность, что на некоторой итерации /-й элемент столбца аю окажется равным нулю. Если одновременно с этим /-Й элемент столбца а! к, подлежащего вводу в базис, окажется положительным, то минимальное из отношений элементов столбца о/0 к соответствующим положительным элементам столбца а1к будет равно нулю. Тогда, хотя набор базисных переменных будет другим, целевая функция после преобразования сохранит прежнее значение. Нули в столбце аю также образуются в случае, если на предыдущей итерации имела место неоднозначность при выборе переменной, которую предстояло исключить из числа базисных. Она возникает там, где минимум соотношений а^а1к достигается сразу для нескольких (по крайней мере, двух) строк. Способ преодоления вырожденности при решении землеустроительных задач симплексным методом описан Е. Г. Ларченко; по его методике, когда указанный минимум достигается для нескольких значений индекса /, исключается та переменная, для которой достигается минимум соотношений ал/а1к, где /—индексы строк переменных, которые участвуют в выборе. Пусть, например, при базисных переменных хь х2,..., хт> 0 имеем д10 = а20 а\к а2к ' В этом случае неизвестно, какую из базисных переменных (х^ или х2) следует сделать на следующем шаге небазисной. Для выхода из неопределенности сопоставим величины 41 „ «21 а\к а1к Если минимальна по модулю первая из них, исключаем переменную х1; если вторая —то х2. Если же и они одинаковы, сравниваем отношения «12 и «22 «1А; «2Аг и выбираем из них наименьшее. Такое сравнение проводится до тех пор, пока не будут получены неравные величины. 17.3. РОЛЬ ОГРАНИЧЕНИЙ В ФОРМИРОВАНИИ ОБЛИКА ПРОИЗВОДСТВЕННЫХ ФУНКЦИЙ (НА ПРИМЕРЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ) Выше мы специально оговаривали тот факт, что функциональная зависимость результата производства у от производственных факторов хь Х2,..., х^ может применяться только в определенной области допустимых значений факторов. В действительности ограничения, характерные для землеустроительных задач, играют существенно более фундаментальную роль — они фактически формируют облик производственной функции внутри области допустимых значений производственных факторов. Проиллюстрируем это утверждение на примере анализа уже рассматривавшейся в главе 14 упрощенной демонстрационной задачи линейного программирования, заменив в ней фиксированные ресурсные ограничения на варьируемые и несколько изменив принятые там исходные данные и обозначения. Задача 17.2. В хозяйстве производятся молоко и зерно. Все молоко идет на продажу; 40 % зерна используется на корм скоту, 60 % идет на продажу. Ресурсы хозяйства (варьируемые): х\ — площадь пашни, га; х2 — трудовые ресурсы, чел.-ч; х3 — запас кормов на пастбищах и сенокосах, ц корм, ед.; х4 — количество мест для содержания коров, гол. Нормы трудозатрат: 5 чел.-ч на 1 га; 50 чел.-ч на 1 гол. Норма кормления животных 80 ц корм. ед. на 1 гол. Урожайность зерновых 25 ц корм. ед. с 1 га. Продуктивность коров 4000 кг на 1 гол. Цена на зерно 10 руб. за 1 ц, молоко — 0, 2 руб. за 1 кг. При любых фиксированных ресурсах хозяйства необходимо определить максимальный валовой годовой продукт в денежном выражении. Введем основные переменные симплексной модели задачи 17.2: ^1 — площадь пашни под зерновыми, га; %1 — поголовье коров, гол. Тогда модель будет иметь вид %\ ^хъ 5^+50^ < х2; -10^ + 80^2 ^*з; г < * (17Л) ^=0, 15^1+0, 8^2-*тах; ^> 0, ^2> 0. Напомним, что здесь 2Г— целевая функция (валовой продукт хозяйства в денежном выражении, тыс. руб.), а ограничения имеют следующий смысл: 1-е — по площади пашни; 2-е — по трудовым ресурсам; 3-е — по кормам; 4-е — по количеству мест для содержания коров. Зафиксировав ресурсы Х\,..., х4 и решив задачу симплекс-методом, получим определенное оптимальное решение; 2 = 2опАхЬ~-> х4)> ^1=^1 (ХЬ-; Х4УЛ2=^> 2 (ХЬ--> Х4)- Предположим теперь, что цель анализа задачи (17.1) —установление зависимости оптимального значения целевой функции от обеспеченности хозяйства ресурсами, то есть определение вида производственной функции у=2от(хи..., х4). (17.2) Рассмотрим сначала случай фиксированных трудовых ресурсов, запасов кормов на пастбищах и сенокосах и количества мест для содержания коров: х2 = 12 000 чел.-ч; х3 = 2000 ц корм, ед.; х4 = 110 гол., то есть ситуацию, когда переменным является только ресурс пашни (х,).
У1
О 500 х{ 1000 х/ 1500 2000 х] Рис. 20. Зависимость оптимального значения целевой функции задачи от обеспеченности хозяйства пашней Зависимость у=2от{хх)\ Х2, х^, х^-сотХ > (17.3) полученная в результате решения серии задач линейного программирования вида (17.1), каждая из которых соответствует определенному значению хь приведена на рисунке 20. Обращает на себя внимание кусочно-линейный характер представленной зависимости. Это не следствие приближенного описания результата, а точное отражение зависимости решения симплексной задачи от ресурса х{. Причем на каждом линейном отрезке зависимости у(х\) производная ду/дхь то есть дополнительный продукт фактора хь совпадает с его скрытой ценой. Проиллюстрируем это утверждение для случая, когда ресурс пашни х{ находится в интервале от 1300 до 2400 га, например при X) = 1500 га. Для таких условий (с учетом зафиксированных ранее значений ресурсов хъ хъ х4) область допустимых значений, соответствующая модели (17.1), изображена на рисунке 21. Ресурс Х[ = 1500 га формирует в области допустимых значений грань ЕР. Линии уровня целевой функции Д^ь ^2) задачи линейного программирования, показанные на рисунке штриховыми прямыми, ориентированы так, что оптимальной является вершина Е. Таким образом, сдерживающими ограничениями являются 1-е и 2-е и соответственно дефицитными ресурсами — пашня и трудовые ресурсы. Увеличение ресурса пашни должно приводить к сдвигу вершины Е вправо-вниз, а значит, к увеличе- нию целевой функции. В то же время известно, что увеличение ресурса эквивалентно введению в план отрицательного значения остаточной переменной, связанной с этим ресурсом (в данном случае это переменная ^ — см. табл. 127). При таком введении ^3 в план оптимальное значение целевой функции будет меняться в соответствии с двойственной оценкой этой переменной (скрытой ценой ресурса пашни): ■ ^опт =-2опт ~(%3 ~Сз)^3 =2опт -0, 07^з- Учитывая, что |^3| — это и есть приращение ресурса пашни, получим следующую формулу: у=у3+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 при х1 = 1500 га, хг = 12 000 чел.-ч, х, = 2000 ц корм, ед., х4 = 110 гол.
1 г, 6(ост.) 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 га, х2 = = 12 000 чел.-ч, х4= ПО гол. ресурс кормов на пастбищах и сено-
Рис. 22. Область допустимых значений задачи при лг, < 680 косах (х3) никак не влияет на валовой продукт хозяйства. Это ясно из геометрического представления задачи (см., например, рис. 21). Поскольку при указанных значениях хь х2, х4 оптимальной является вершина Е, то даже при уменьшении х3 до нуля соответствующая третьему ограничению грань области допустимых значений (ВС) сдвинется вправо незначительно (пройдет через точку А), что не поменяет характер оптимального решения — ресурс х3 не станет дефицитным и, следовательно, бу- 128. Последняя симплекс-таблица задачи 17.1 при х1 = 600 га, хг хг = 2000 ц корм, ед., х4 = ПО гол.
|