Материалы сайта
Это интересно
Построение экономической модели с использованием симплекс-метода
Курсовая работа Тема: Построение экономической модели с использованием симплекс-метода . Работу выполнил студент УТФ-4-2 Кулаков О. А. Оглавление . Введение Моделирование как метод научного познания. Введение в симплекс-метод Словесное описание Математическое описание Ограничения Переменные Целевая функция Симплекс-метод . Представление пространства решений стандартной задачи линейного программирования Вычислительные процедуры симплекс-метода Анализ результатов . Оптимальное решение Статус ресурсов Ценность ресурса Максимальное изменение запаса ресурса Максимальное изменение коэффициентов удельной прибыли ( стоимости ) Моделирование как метод научного познания. Моделирование в научных исследованиях стало применяться еще в глубокой древности и постепенно захватывало все новые области научных знаний : техническое конструирование , строительство и архитектуру , астрономию , физику , химию , биологию и , наконец , общественные науки . Большие успехи и признание практически во всех отраслях современной науки принес методу моделирования ХХ в . Однако методология моделирования долгое время развивалась независимо отдельными науками . Отсутствовала единая система понятий, единая терминология . Лишь постепенно стала осознаваться роль моделирования как универсального метода научного познания . Термин "модель" широко используется в различных сферах человеческой деятельности и имеет множество смысловых значений . Рассмотрим только такие "модели", которые являются инструментами получения знаний . Модель - это такой материальный или мысленно представляемый объект, который в процессе исследования замещает объект-оригинал так, что его непосредственное изучение дает новые знания об объекте-оригинале . Под моделирование понимается процесс построения , изучения и применения моделей . Оно тесно связано с такими категориями , как абстракция , аналогия , гипотеза и др . Процесс моделирования обязательно включает и построение абстракций , и умозаключения по аналогии, и конструирование научных гипотез. Главная особенность моделирования в том , что это метод опосредованного познания с помощью объектов-заместителей . Модель выступает как своеобразный инструмент познания , который исследователь ставит между собой и объектом и с помощью которого изучает интересующий его объект . Именно эта особенность метода моделирования определяет специфические формы использования абстракций , аналогий , гипотез , других категорий и методов познания . Необходимость использования метода моделирования определяется тем, что многие объекты ( или проблемы , относящиеся к этим объектам ) непосредственно исследовать или вовсе невозможно, или же это исследование требует много времени и средств. Моделирование - циклический процесс . Это означает , что за первым четырехэтапным циклом может последовать второй , третий и т.д. При этом знания об исследуемом объекте расширяются и точняются, а исходная модель постепенно совершенствуется . Недостатки , обнаруженные после первого цикла моделирования , бусловленные малым знанием объекта и ошибками в построении модели , можно исправить в последующих циклах . В методологии моделирования , таким образом , заложены большие возможности саморазвития . Словесное описание Фирма , производящая некоторую продукцию осуществляет её рекламу двумя способами через радиосеть и через телевидение . Стоимость рекламы на радио обходится фирме в 5 $ , а стоимость телерекламы - в 100$ за минуту . Фирма готова тратить на рекламу по 1000 $ в месяц . Так же известно , что фирма готова рекламировать свою продукцию по радио по крайней мере в 2 раза чаще , чем по телевидению . Опыт предыдущих лет показал , что телереклама приносит в 25 раз больший сбыт продукции нежели радиореклама . Задача заключается в правильном распределении финансовых средств фирмы . Математическое описание . X1 - время потраченное на радиорекламу . X2 - время потраченное на телерекламу . Z - искомая целевая функция , оражающая максимальный сбыт от 2-ух видов рекламы . X1=>0 , X2=>0 , Z=>0 ; Max Z = X1 + 25X2 ; 5X1 + 100X2 <=1000 ; X1 -2X2 => 0 Использование графического способа удобно только при решении задач ЛП с двумя переменными . При большем числе переменных необходимо применение алгебраического аппарата . В данной главе рассматривается общий метод решения задач ЛП , называемый симплекс-методом . Информация , которую можно получить с помощью симплекс-метода , не ограничивается лишь оптимальными значениями переменных . Симплекс-метод фактически позволяет дать экономическую интерепритацию полученного решения и провести анализ модели на чувствительность . Процесс решения задачи линейного программирования носит итерационный характер : однотипные вычислительные процедуры в определенной последовательности повторяются до тех пор , пока не будет получено оптимальное решение . Процедуры , реализуемые в рамках симплекс-метода , требуют применения вычислительных машин - мощного средства решения задач линейного программирования . Симлекс-метод - это характерный пример итерационных вычислений , используемых при решении большинства оптимизационных задач . В данной главе рассматриваются итерационные процедуры такого рода , обеспечивающие решение задач с помощью моделей исследования операций . В гл 2 было показано , что правая и левая части ограничений линейной модели могут быть связаны знаками <= , = и => . Кроме того , переменные , фигурирующие в задачах ЛП , могут быть неотрицательными или не иметь ограничения в знаке . Для построения общего метода решения задач ЛП соответствующие модели должны быть представлены в некоторой форме , которую назовем стандатрной формой линейных оптимизационных моделей . При стандартной форме линейной модели 1. Все ограничения записываются в виде равенств с неотрицательной правой частью ; 2. Значения всех переменных модели неотрицательны ; 3. Целевая функция подлежит максимизации или минимизации . Покажем , каким образом любую линейную модель можно привести к стандартной . Ограничения 1. Исходное ограничение , записанное в виде неравенства типа <= ( =>) , можно представить в виде равенства , прибавляя остаточную переменную к левой части ограничения ( вычитая избыточную переменную из левой части ) . Например , в левую часть исходного ограничения 5X1 + 100X2 <= 1000 вводистя остаточная переменная S1 > 0 , в результате чего исходное неравенство обращается в равенство 5X1 + 100X2 + S1 = 1000 , S1 => 0 Если исходное ограничение определяет расход некоторого ресурса , переменную S1 следует интерпретировать как остаток , или неиспользованную часть , данного ресурса . Рассмотрим исходное ограничение другого типа : X1 - 2X2 => 0 Так как левая часть этого ограничения не может быть меньше правой , для обращения исходного неравенства в равенство вычтем из его левой части избыточную переменную S2 > 0 . В результате получим X1 - 2X2 - S2 = 0 , S2 => 0 2. Правую часть равенства всегда можно сделать неотрицательной , умножая оби части на -1 . Например равенство X1 - 2X2 - S2 = 0 эквивалентно равенству - X1 + 2X2 + S2 = 0 3. Знак неравенства изменяется на противоположный при умножении обеих частей на -1 . Например можно вместо 2 < 4 записать - 2 > - 4 , неравенство X1 - 2X2 <= 0 заменить на - X1 + 2X2 => 0 Переменные Любую переменную Yi , не имеющую ограничение в знаке , можно представить как разность двух неотрицательных переменных : Yi=Yi’-Yi’’, где Yi’,Yi’’=>0. Такую подстановку следует использовать во всех ограничениях , которые содержат исходную переменную Yi , а также в выражении для целевой функции . Обычно находят решение задачи ЛП , в котором фигурируют переменные Yi’ и Yi’’ , а затем с помощью обратной подстановки определяют величину Yi . Важная особенность переменных Yi’ и Yi’’ состоит в том , что при любом допустимом решении только одна из этих переменных может принимать положительное значение , т.е. если Yi’>0 , то Yi’’=0, и наоборот . Это позволяет рассматривать Yi’ как остаточную переменную , а Yi’’ - как избыточную переменную , причем лишь одна из этих переменных может принимать положительное значение . Указанная закономерность широко используется в целевом программировании и фактически является предпосылкой для использования соответсвующих преобразований в задаче 2.30 Целевая функция Целевая функция линейной оптимизационной модели , представлена в стандартной форме , может подлежать как максимизации , так и минимизации . В некоторых случаях оказывается полезным изменить исходную целевую функцию . Максимизация некоторой функции эквивалентна минимизации той же функции , взятой с противоположным знаком , и наоборот . Например максимизация функции Z = X1 + 25X2 эквивалентна минимизации функции ( -Z ) = -X1 - 25X2 Эквивалентность означает , что при одной и той же совокупности ограничений оптимальные значения X1 , X2 , в обоих случаях будут одинаковы . Отличие заключается только в том , что при одинаковых числовых значениях целевых функций их знаки будут противоположны . Симплекс-метод . В вычислительной схеме симплекс-метода реализуется упорядоченный процесс , при котором , начиная с некоторой исходной допустимой угловой точки ( обычно начало координат ) , осуществляются последовательные переходы от одной допустимой экстремальной точки к другой до тех пор , пока не будет найдена точка , соответствующая оптимальному решению . Общую идею симплекс-метода можно проиллюстрировать на примере модели , посроенной для нашей задачи . Пространство решений этой задачи представим на рис. 1 . Исходной точкой алгоритма является начало координат ( точка А на рис. 1 ) . Решение , соответствующее этой точке , обычно называют начальным решением . От исходной точки осуществляется переход к некоторой смежной угловой точке . Выбор каждой последующей экстремальной точки при использовании симплекс-метода определяется следующими двумя правилами . 1. Каждая последующая угловая точка должна быть смежной с предыдущей . Этот переход осуществляется по границам ( ребрам ) пространства решений . 2. Обратный переход к предшествующей экстремальной точке не может производиться . Таким образом , отыскание оптимального решения начинается с некоторой допустимой угловой точки , и все переходы осуществляются только к смежным точкам , причем перед новым переходом каждая из полученных точек проверяется на оптимальность . Определим пространство решений и угловые точки агебраически . Требуемые соотнощшения устанавливаются из указанного в таблице соответствия геометрических и алгебраических определений . |Геометрическое |Алгебраическое | |определение |определение | | |( симплекс метод ) | |Пространство решений |Ограничения модели | | |стандартной формы | |Угловые точки |Базисное решение задачи в| | |стандартной форме | Представление пространства решений стандартной задачи линейного программирования . Линейная модель , построенная для нашей задачи и приведенная к стандартной форме , имеет следующий вид : Максимизировать Z = X1 + 25X2 + 0S1 + 0S2 При ограничениях 5X1 + 100X2 + S1 = 1000 - X1 + 2X2 + S2 = 0 X1=>0 , X2=>0 , S1=>0 , S2=>0 Каждую точку пространства решений данной задачи , представленную на рис.1 , можно определить с помощью переменных X1 , X2 , S1 и S2 , фигурирующими в модели стандартной формы. При S1 = 0 и S2 = 0 ограничения модели эквивалентны равенствам , которые представляются соответствующими ребрами пространства решений . Увеличение переменных S1 и S2 будет соответствовать смещению допустимых точек с границ пространства решений в его внутреннюю область. Переменные X1 , X2 , S1 и S2 , ассоциированные с экстремальными точками А , В , и С можно упорядочить , исходя из того , какое значение ( нулевое или ненулевое ) имеет данная переменная в экстремальной точке . |Экстремальная |Нулевые переменные|Ненулевые переменные| |точка | | | |А |S2 , X2 |S1 , X1 | |В |S1 , X2 |S2 , X1 | |С |S1 , S2 |X1 , X2 | Анализируя таблицу , легко заметить две закономерности: 1. Стандартная модель содержит два уравнения и четыре неизвестных , поэтому в каждой из экстремальных точек две ( = 4 - 2 ) переменные должны иметь нулевые значения . 2. Смежные экстремальные точки отличаются только одной пе- ременной в каждой группе ( нулевых и ненулевых переменных ) , Первая закономерность свидетельствует о возможности опре- деления экстремальных точек алгебраическим способом путем при- равнивания нулю такого количества переменных , которое равно разности между количеством неизвестных и числом уравнений . В этом состоит сущность свойства однозначности экстремальных точек . На рис. 1 каждой неэкстремальной точке соответствует не более одной нулевой переменной . Так , любая точка внутренней области пространства решений вообще не имеет ни одной нулевой переменной, а любая неэкстремальная точка , лежащая на границе , всегда имеет лишь одну нулевую переменную . Свойство однозначности экстремальных точек позволяет опре- делить их алгебраическим методом. Будем считать , что линейная модель стандартной формы содержит т уравнений и п ( т <= п ) не- известных ( правые части ограничений — неотрицательные ) . Тогда все допустимые экстремальные точки определяются как все одно- значные неотрицательные решения системы m уравнений , в ко- торых п — m переменных равны нулю. Однозначные решения такой системы уравнений, получаемые путем приравнивания к нулю ( п — т ) переменных , называются базисными решениями . Если базисное решение удовлетворяет требованию неотрицательности правых частей , оно называется допустимым базисным решением. Переменные , имеющие нулевое значение , называются небазисными переменными , остальные — базисными переменными. Из вышеизложенного следует , что при реализации симплекс- метода алгебраическое определение базисных решений соответст- вует идентификации экстремальных точек , осуществляемой при геометрическом представлении пространства решений . Таким об- разом , максимальное число итераций при использовании симплекс- метода равно максимальному числу базисных решений задачи ЛП , представленной в стандартной форме . Это означает , что количество итерационных процедур симплекс-метода не превышает Cпт= n! / [ ( n - m )!m! ] Вторая из ранее отмеченных закономерностей оказывается весьма полезной для построения вычислительных процедур симп- лекс-метода , при реализации которого осуществляется последова- тельный переход от одной экстремальной точки к другой, смежной с ней . Так как смежные экстремальные точки отличаются только одной переменной, можно определить каждую последующую ( смеж- ную) экстремальную точку путем замены одной из текущих не- базисных ( нулевых ) переменных текущей базисной переменной. В нашем случае получено решение , соответствующее точке А , откуда следует осуществить переход в точку В . Для этого нужно увеличивать небазисную переменную X2 от исходного нулевого значения до значе- ния , соответствующего точке В ( см. рис. 1 ). В точке B переменная S1 ( которая в точке А была базисной ) автоматически обращается в нуль и , следовательно , становится небазисной переменной . Таким образом , между множеством небазисных и множеством базисных переменных происходит взаимообмен переменными X2 и S1 . Этот процесс можно наглядно представить в виде следующей таблицы. |Экстремальная |Нулевые переменные|Ненулевые переменные| |точка | | | |А |S2 , X2 |S1 , X1 | |В |S1 , X2 |S2 , X1 | Применяя аналогичную процедуру ко всем экстремальным точкам рис. 1 , можно убедиться в том , что любую последующую экстре- мальную точку всегда можно определить путем взаимной замены по одной переменной в составе базисных и небазисных переменных ( предыдущей смежной точки ) . Этот фактор существенно упрощает реализацию вычислительных процедур симплекс-метода. Рассмотренный процесс взаимной замены переменных приводит к необходимости введения двух новых терминов . Включаемой пе- ременной называется небазисная в данный момент переменная , которая будет включена в множество базисных переменных на сле- дующей итерации ( при переходе к смежной экстремальной точке ) . Исключаемая переменная — это та базисная переменная , которая на следующей итерации подлежит исключению из множества ба- зисных переменных . Вычислительные процедуры симплекс-метода . симплекс-алгоритм состоит из следующих шагов. Шаг 0. Используя линейную модель стандартной формы , опреде- ляют начальное допустимое базисное решение путем приравнива- ния к нулю п — т ( небазисных ) переменных. Шаг 1. Из числа текущих небазисных ( равных нулю ) перемен- ных выбирается включаемая в новый базис переменная , увеличение которой обеспечивает улучшение значения целевой функции. Если такой переменной нет , вычисления прекращаются , так как текущее базисное решение оптимально . В противном случае осуществляется переход к шагу 2. Шаг 2. Из числа переменных текущего базиса выбирается исклю- чаемая переменная , которая должна принять нулевое значение ( стать небазисной ) при введении в состав базисных новой переменной . Шаг 3. Находится новое базисное решение , соответствующее новым составам небазисных и базисных переменных . Осуществляется переход к шагу 1. Поясним процедуры симплекс-метода на примере решения нашей зада- чи . Сначала необходимо представить целевую функцию и ограничения модели в стандартной форме: Z - X1 - 25X2 +0S1 -0S2 = 0 ( Целевая функция ) 5X1 + 100X2 + S1 = 1000 ( Ограничение ) -X1 + 2X2 + S2 = 0 ( Ограничение ) Как отмечалось ранее , в качестве начального пробного решения используется решение системы уравнений , в которой две переменные принимаются равными нулю . Это обеспечивает единст- венность и допустимость получаемого решения . В рассматриваемом случае очевидно, что подстановка X1 = X2 = 0 сразу же приводит к следующему результату: S1 = 1000 , S2 = 0 ( т. е. решению , соответствующему точке А на рис. 1 ) . Поэтому точку А можно использовать как начальное допустимое решение . Величина Z в этой точке равна нулю , так как и X1 и X2 имеют нулевое значение . Поэтому , преобразовав уравнение целевой функции так , чтобы его правая часть стала равной нулю , можно убедиться в том , что правые части уравнений целевой функции и ограничений полностью характеризуют начальное решение . Это имеет место во всех случаях , когда начальный базис состоит из остаточных переменных. Полученные результаты удобно представить в виде таблицы : |Базисные |Z |X1 |X2 |S1 |S2 |Решение| | |переменные | | | | | | | | |Z |1 |-1 |- 25 |0 |0 |0 |Z - уравнение | |S1 |0 |5 |100 |1 |0 |1000 |S1 -уравнение | |S2 |0 |-1 |2 |0 |1 |0 |S2 - уравнение| Эта таблица интерпретируется следующим образом. Столбец « Базисные переменные » содержит переменные пробного базиса S1 , S2 , значения которых приведены в столбце « Решение » . При этом подразумевается , что небазисные переменные X1 и X2 ( не пред- ставленные в первом столбце ) равны нулю . Значение целевой функ- ции Z = 1*0 + 25*0 + 0*1000 + 0*1 равно нулю , что и показано в последнем столбце таблицы . Определим , является ли полученное пробное решение наи- лучшим ( оптимальным ) . Анализируя Z - уравнение , нетрудно заме- тить , что обе небазисные переменные X1 и X2 , равные нулю , имеют отрицательные коэффициенты . Всегда выбирается переменная с большим абсолютным значением отрицательного коэффициента ( в Z - уравнении ) , так как практический опыт вычислений показывает , что в этом случае оптимум достигается быстрее . Это правило составляет основу используемого в вычислительной схеме симплекс-метода условия оптимальности , которое состоит в том , что , если в задаче максимизации все небазисные переменные в Z - уравнении имеют неотрицательные коэффициенты , полученное пробное решение является оптимальным . В противном случае в ка- честве новой базисной переменной следует выбрать ту , которая имеет наибольший по абсолютной величине отрицательный коэффициент . Применяя условие оптимальности к исходной таблице , выберем в качестве переменной , включаемой в базис , переменную Х2 . Исклю- чаемая переменная должна быть выбрана из совокупности базисных переменных S1 , S2 . Процедура выбора исключаемой переменной предполагает проверку условия допустимости , требующего , чтобы в качестве исключаемой переменной выбиралась та из пере- менных текущего базиса , которая первой обращается в нуль при уве- личении включаемой переменной X2 вплоть до значения , соответствующего смежной экстремальной точке . Интересующее нас отношение ( фиксирующее искомую точку пе-ресечения и идентифицирующее исключаемую переменную ) можно определить из симплекс-таблицы. Для этого в столбце , соответствующем вводимой переменной X2 , вычеркиваются отрицательные и нулевые элементы ограничений . Затем вычисляются отношения постоянных , фигурирующих в правых частях этих ограничений , к оставшимся элементам столбца , соответствующего вводимой переменной X2 . Исключаемой переменной будет та переменная текущего базиса , для которой указанное выше отношение минимально. Начальная симплекс-таблица для нашей задачи , получаемая после проверки условия допустимости ( т. е. после вычисления соответствующих отношений и определения исключаемой переменной ) , воспроизведена ниже . Для удобства описания вычислительных процедур , осуществляемых на следующей итерации , введем ряд необходимых определений . Столбец симплекс-таблицы , ассоциированный с вводимой переменной , будем называть ведущим столбцом . Строку , соответствующую исключаемой переменной , назовем ведущей строкой ( уравнением ) , а элемент таблицы , находящийся на пересечении ведущего столбца и ведущей строки , будем называть ведущим элементом . После того как определены включаемая и исключаемая пере- менные ( с использованием условий оптимальности и допустимости ) , следующая итерация ( поиск нового базисного решения ) осуществля- ется методом исключения переменных , или методом Гаусса — Жордана . Этот процесс изменения базиса включает вычислительные процедуры двух типов . Тип 1 ( формирование ведущего уравнения ) . Новая ведущая строка = Предыдущая ведущая строка / Ведущий элемент Тип 2 ( формирование всех остальных уравнений , включая Z - yравнение ) . Новое уравнение = Предыдущее уравнение — й Коэффициент щ к ведущего столбца к * ( Новая ведущая строка ) . к предыдущего к л уравнения ы Выполнение процедуры типа 1 приводит к тому , что в новом ведущем уравнении ведущий элемент становится равным единице . В результате осуществления процедуры типа 2 все остальные коэф- фициенты , фигурирующие в ведущем столбце , становятся равными нулю . Это эквивалентно получению базисного решения путем ис- ключения вводимой переменной из всех уравнений , кроме ведущего . Применяя к исходной таблице процедуру 1 , мы делим S2 - уравнение на ведущий элемент , равный 1 . |Базисные |Z |X1 |X2 |S1 |S2 |Решен| |переменные | | | | | |ие | |Z | | | | | | | |S1 | | | | | | | |S2 |0 |-1/2 |1 |0 |1/2 |0 | Чтобы составить новую симплекс-таблицу , выполним необходимые вычислительные процедуры типа 2 . 1. Новое Z - уравнение . старое Z - уравнение : ( 1 -1 -25 0 0 0 ) ( - ( -25 ) * ( 0 -1/2 1 0 1/2 0 ) ( 1 -131/2 0 0 121/2 0 ) 2. Новое S1 - уравнение старое S1 - уравнение : ( 0 5 100 1 0 1000 ) ( - 100 ) * ( 0 -1/2 1 0 1/2 0 ) ( 0 55 0 1 -50 1000 ) Новая симплекс-таблица будет иметь вид : |Базисные |Z |X1 |X2 |S1 |S2 |Решение| | |переменные | | | | | | | | |Z |1 |-131/2|0 |0 |121/2 |0 |Z - уравнение | |S1 |0 |55 |0 |1 |-50 |1000 |S1 -уравнение | |X2 |0 |-1/2 |1 |0 |1/2 |0 |X2 - уравнение | В новом решении X1 = 0 и S2 = 0 . Значение Z не изменяется . Заметим , что новая симплекс-таблица обладает такими же ха- рактеристиками , как и предыдущая : только небазисные переменные X1 и S2 равны нулю , а значения базисных переменных , как и раньше , представлены в столбце « Решение » . Это в точности соответствует результатам , получаемым при использовании метода Гаусса—Жор- дана . Из последней таблицы следует , что на очередной итерации в со- ответствии с условием оптимальности в качестве вводимой перемен- ной следует выбрать X1 , так как коэффициент при этой переменной в Z-ypaвнении равен -131/2 . Исходя из условия допустимости , определяем , что исключаемой переменной будет S1 . Отношения , фигурирующие в правой части таблицы , показывают , что в новом базисном решении значение включаемой переменной X1 будет равно 1000/55 ( = минимальному отношению ) . Это приводит к увеличению целевой функции на ( 1000/55 ) * ( -131/2 ) = ( 2455/11 ) . К получению симплекс-таблицы , соответствующей новой итерации , приводят следующие вычислительные операции метода Гаусса—Жордана. 1) Новое ведущее S1 - уравнение = Предыдущее S1 - уравнение / ( 55 ) . |Базисные |Z |X1 |X2 |S1 |S2 |Решение| |переменные | | | | | | | |Z | | | | | | | |S1 |0 |1 |0 |1/55 |- |1000/55| | | | | | |50/55 | | |X2 | | | | | | | 2) Новое Z - уравнение = Предыдущее Z - уравнение - ( -131/2 ) * Новое /ведущее уравнение : ( 1 -131/2 0 0 121/2 0 ) - ( -131/2 ) * ( 0 1 0 1/55 -50/55 1000/55 ) ( 1 0 0 27/110 5/22 2455/11 ) 3) Новое X2 - уравнение = Предыдущее X2 - уравнение - ( -1/2 ) * Новое ведущее уравнение : ( 0 -1/2 1 0 1/2 0 ) - ( - 1/2 ) * ( 0 1 0 1/55 -50/55 1000/55 ) ( 0 0 1 1/110 1/22 91/11 ) В результате указанных преобразований получим следующую симп- лекс-таблицу . |Базисные |Z |X1 |X2 |S1 |S2 |Решение | |переменные | | | | | | | |Z |1 |0 |0 |27/110 |5/22 |2455/11 | |X1 |0 |1 |0 |1/55 |-50/55 |1000/55 | |X2 |0 |0 |1 |1/110 |1/22 |91/11 | В новом базисном решении X1=1000/55 и X2=91/11 . Значение Z увеличилось с 0 ( предыдущая симплекс-таблица ) до 2455/11 ( последняя симплекс-таблица ) . Этот результирующий прирост целевой функции обусловлен увеличением X1 от О до 1000/55 , так как из Z - строки предыдущей симплекс-таблицы следует , что возрастанию данной переменной на единицу соответствует увеличение целевой функции на( -131/2 ) . Последняя симплекс-таблица соответствует оптимальному реше- нию задачи, так как в Z - уравнении ни одна из небазисных переменных не фигурирует с отрицательным коэффициентом. Получением этой pезультирующей таблицы и завершаются вычислительные процедуры симплекс-метода . В рассмотренном выше примере алгоритм симплекс-метода ис- пользован при решении задачи , в которой целевая функция подлежала максимизации . В случае минимизации целевой функции в этом алгоритме необходимо изменить только условие оптимальности : в качестве новой базисной переменнойследует выбирать ту переменную , которая в Z - уравнении имеет наибольший положительный коэффициент . Условия допустимости в обоих случаях ( максимизации и минимизации ) одинаковы . Представляется целесообразным дать теперь окончательные формулировки обоим условиям , используемым в симплекс-методе . Условие оптимальности . Вводимой переменной в задаче максимизации ( минимизации ) является небазисная переменная , имеющая в Z -уравнении наибольший отрицательный ( положительный ) коэффициент , В случае равенства таких коэффициентов для нескольких небазисных переменных выбор делается произвольно , если все коэффициенты при небазисных переменных в Z - уравнении неотрицательны (неположительны) , полученное решение является оптимальным . Условие допустимости , в задачах максимизации и минимизации в качестве исключаемой переменной выбирается та базисная переменная , для которой отношение постоянной в правой части соответствующего ограничения к ( положительному ) коэффициенту ведущего столбца минимально. В случае равенства этого отношения для нескольких базисных переменных выбор делается произвольно . Оптимальное решение С точки зрения практического использования результатов ре- шения задач ЛП классификация переменных , предусматривающая их разделение на базисные и небазнсные , не имеет значения и при анализе данных , характеризующих оптимальное решение , может не учитываться . Переменные , отсутствующие в столбце « Базисные переменные » , обязательно имеют нулевое значение . Значения ос- тальных переменных приводятся в столбце « Решение » . При интер- претации результатов оптимизации в нашей задаче нас прежде всего интересует количество времени , которое закажет наша фирма на радио и телевидение , т. е. значения управляемых переменных X1 и X2 . Используя данные , содержащиеся в симплекс-таблице для оптимального решения , основные результаты можно представить в следующем виде : |Управляемые |Оптимальные |Решение | |переменные |значения | | |X1 |1000/55 |Время выделяемое фирмой на телерекламу | |X2 |91/11 |Время выделяемое фирмой на радиорекламу| |Z |2455/11 |Прибыль получаемая от рекламы . | Заметим, что Z = X1 + 25X2 = 1000/55 + 25 * 91/11 = 2455/11 . Это решение соответствует данным заключительной симплекс-таблицы . Статус ресурсов Будем относить ресурсы к дефицитным или недифицитным в зависимости от того , полное или частичное их использо- вание предусматривает оптимальное решение задачи . Сейчас цель состоит в том , чтобы получить соответствующую информацию непос- редственно из симплекс-таблицы для оптимального решения . Од- нако сначала следует четко уяснить следующее . Говоря о ресурсах , фигурирующих в задаче ЛП , мы подразумеваем , что установлены некоторые максимальные пределы их запасов , поэтому в соответст- вующих исходных ограничениях должен использоваться знак <= . Следовательно , ограничения со знаком => не могут рассматриваться как ограничения на ресурсы . Скорее , ограничения такого типа отра- жают то обстоятельство , что решение должно удовлетворять опре- деленным требованиям , например обеспечению минимального спро- са или минимальных отклонений от установленных структурных характеристик производства ( сбыта ) . В модели , построенной для нашей задачи , фигурирует ограничение со знаком <= . Это требование можно рассматривать как ограничение на соответствующий « ресурс » , так как увеличение спроса на продукцию эквивалентно расширению « представительства » фирмы на рынке сбыта . Из вышеизложенного следует , что статус ресурсов ( дефицитный или недефицитный ) для любой модели ЛП можно установить не- посредственно из результирующей симплекс-таблицы , обращая вни- мание на значения остаточных переменных . Применительно к нашей задаче можно привести следующую сводку результатов : |Ресурсы |Остаточная |Статус | | |переменная |ресурса | |Ограничение по бюджету |S1 |Дефицитный | |Превышение времени рекламы радио над |S2 |Дефицитный | |теле | | | Положительное значение остаточной переменной указывает на неполное использование соответствующего ресурса , т . е . данный ресурс является недефицятным. Если же остаточная переменная рав- на нулю , это свидетельствует о полном потреблении соответствующе- го ресурса. Из таблицы видно , что наши ресурсы являются дефицитными . В случае недефицитности любое увиличение ресурсов сверх установленного максимального значения привело бы лишь к тому , что они стали бы еще более недефнинтными . Оптимальное решение задачи при этом осталось бы неизменным. Ресурсы, увеличение запасов которых позволяет улучшить ре- шение ( увеличить прибыль ) , — это остаточные переменные S1 и S2 , по- скольку из симплекс-таблицы для оптимального решения видно , что они дефицитные . В связи с этим логично поставить следующий вопрос: какому из дефицитных ресурсов следует отдать предпочте- ние при вложении дополнительных средств на увеличение их запа- сов , с тем чтобы получить от них максимальную отдачу ? Ответ на этот вопрос будет дан в следующем подразделе этой главы , где рас- сматривается ценность различных ресурсов . Ценность ресурса Ценность ресурса характеризуется величиной улучшения опти- мального значения Z , приходящегося на единицу прироста объема данного ресурса . Информация для оптимального решения задачи представлена в симплекс- таблице . Обратим внимание на значения коэффициентов Z - уравнения , стоящих при переменных начального базиса S1 и S2 . Выделим для удобства соответстзующую часть симплекс-таблицы : |Базисные |Z |X1 |X2 |S1 |S2 |Решение | |переменные | | | | | | | |Z |1 |0 |0 |27/110 |5/22 |2455/11 | Как следует из теории решения задач ЛП , ценность ресурсов всегда можно определить по значениям коэффициентов при переменных начального базиса , фигурирующих в Z - уравнении оптимальной симплекс-таблицы , таким образом Y1 = 27/110 , а Y2 = 5/22 . Покажем , каким образом аналогичный результат можно получить непосредственно из симплекс-таблицы для оптимального решения . Рассмотрим Z - уравнение симплекс-таблицы для оптимального решения нашей задачи Z = 2455/11 - ( 27/110S1 + 5/22S2 ) . Положительное приращение переменной S1 относительно ее текущего нулевого значения приводит к пропорциональному уменьшению Z , причем коэффициент пропорциональности равен 27/110 . Но , как следует из первого ограничения модели : 5X1 + 100X2 + S1 = 1000 увеличение S1 эквивалентно снижению количества денег выделеных на рекламу ( далее мы будем использовать в тексте , как первый ресурс ) . Отсюда следует , что уменьшение количества денег выделеных на рекламу вызывает пропорциональное уменьшение целевой функции с тем же коэффициентом пропорциональности , равным 27/110 . Так как мы оперируем с линейными функциями , полученный вывод можно обобщить , считая , что и увеличение количества денег выделеных на рекламу ( эквивалентное введению избыточной переменной S1 < 0 ) приводит к пропорциональному увеличению Z с тем же коэффициентом пропорциональности , равным 27/110 . Аналогичные рассуждения справед- ливы для ограничения 2 . Несмотря на то что ценность различных ресурсов , определяемая значениями переменных Yi , была представлена в стоимостном выражении , ее нельзя отождествлять с действительными це- нами , по которым возможна закупка соответствующих ресурсов . На самом деле речь идет о некоторой мере , имеющей экономическую природу н количественно характеризующей ценность ресурса только относительно полученного оптимального значения целевой функции . При изменении ограничении модели соответствующие экономические оценки будут меняться даже тогда , когда оптимизируемый процесс предполагает применение тех же ресурсов . Поэтому при характерис- тике ценности ресурсов экономисты предпочитают использовать такие терминыт , как теневая цена , скрытая цена , или более специ- фичный термин — двойственная оценка . Заметим , что теневая цена ( ценность ресурса ) характеризует ин- тенсивность улучшения оптимального значения Z . Однако при этом не фиксируется интервал значений увеличения запасов ресурса , при которых интенсивность улучшения целевой функции остается постоянной . Для большинства практических ситуаций логично пред- положить наличие верхнего предела увеличения запасов , при пре- вышении которого соответствующее ограничение становится избы- точным , что в свою очередь приводит к новому базисному решению и соответствующим ему новым теневым ценам . Ниже определяется нитервал значений запасов ресурса , при которых соответствую- щее ограничение не становится избыточным . Максимальное изменение запаса ресурса При решении вопроса о том , запас какого из ресурсов следует увеличивать в первую очередь , обычно используются теневые цены Чтобы определить интервал значений изменения запаса ресурса , при которых теневая цена данного ресурса , ( фигурирующая в заклю- чительной симплекс-таблице , остается неизменной , необходимо выполнить ряд дополнительных вычислений . Рассмотрим сначала соответствующие вычислительные процедуры , а затем покажем , как требуемая информация может быть получена из симплекс-таблицы для оптимального решения . В нашей задаче запас первого ресурса изменился на D1 т. е. запас бюджета составит 1000 + D1 . При положительной величине D1 запас данного ресурса увеличивается , при отрицательной — уменьшается . Как правило , исследуется ситуация , когда объем ресурса увеличивается ( D1 > 0 ) , однако , чтобы получить результат в общем виде , рассмотрим оба случая . Как изменится симплекс-таблица при изменении величины за- паса ресурса на D1 ? Проще всего получить ответ на этот вопрос . если ввести D1 в правую часть первого ограничения начальной сим- плекс-таблицы и затем выполнить все алгебраические преобразова- ния , соответствующие последовательности итераций . Поскольку правые части ограничений никогда не используются в качестве ведущих элементов , то очевидно , что на каждой итерации D1 будет оказывать влияние только на правые части ограничений . |Уравнение |Значения элементов правой части на | | |соответствующих итерациях | | |( начало вычислений|1 |2 ( оптимум| | |) | |) | |Z |0 |0 |2455/11 | |1 |1000 |1000 + |1000/55 + | | | |D1 |D1 | |2 |0 |0 |91/11 | Фактически вce изменения правых частей ограничений , обуслов- ленные введением D1 , можно определить непосредственно по данным , содержащимся в симплекс-таблицах . Прежде всего заметим , что на каждой итерации новая правая часть каждого ограничения пред- ставляет собой сумму двух величин: 1) постоянной и 2) члена , ли- нейно зависящего от D1 . Постоянные соответствуют числам , которые фигурируют на соответствующих итерациях в правых частях ограничений симплекс-таблиц до введения D1 . Коэффициенты при D1 во вторых слагаемых равны коэффициентам при S1 на той же итерации . Так , например , на последнеи итерации ( оптимальное решение ) постоянные ( 2455/11 ; 1000/55 ; 91/11 ) представляют собои числа , фигурирующие в правых частях ограничении оптимальной симплекс-таблицы до введения D1. Коэффициенты ( 27/110 ; 1/55 ; 1/110 ) равны коэффициентам при S1 в той же симплекс- таблице потому , что эта переменная связана только с первым ограничением . Другими словами , при анализе влияния изменений в правой части второго ограничения нужно пользоваться коэффициентами при переменной S2 . Какие выводы можно сделать из полученных результатов? Так как введение D1 сказывается лишь на правой части симплекс- таблицы , изменение запаса ресурса может повлиять только на допустимость решения . Поэтому D1 не может принимать значений , при которых какая-либо из ( базисных ) переменных становится отри- цательной . Из этого следует , что величина D1 должна быть огра- ничена таким интервалом значений , при которых выполняется ус- ловие неотрицательности правых частей ограничений в результи- рующей симплекс-таблице , т . е . X1 = 1000/55 + ( 1/55 )D1 => 0 ( 1 ) X2 = 91/11 + ( 1/110 )D1 => 0 ( 2 ) Для определения допустимого интервала изменения D1 рассмо- трим два случая . Случай 1: D1 => 0 Очевидно , что оба неравнества при этом условии всегда будут неотрицательными . Случай 2: D1 < 0 . Решаем неравенства : ( 1 ) ( 1/55 )D1 => - 1000/55 . Из этого следует , что D1 => - 1000 ( 2 ) ( 1/110 )D1 => - 91/11 . Из этого следует , что D1 => - 1000 Объединяя результаты , полученные для обоих случаев , можно сделать вывод , что при - 1000 <= D1 <= + Ґ решение рассматриваемой зада- чи всегда будет допустимым , любое значение D1 , выходящее за пределы указанного интервала , приведет к недопустимости решения и новой совокупности базисных переменных . Теперь рассмотрим в каких пределах может изменяться запас ресурса 2 анализ проведем по аналогичной схеме : Запас 2-ого ресурса изменился на D2 т . е . запас рекламного времени составит 0 + D2 . Как изменилась симплекс-таблица при изменении величины запаса ресурса на D2 проиллюстрировано ниже . |Уравнение |Значения элементов правой части на | | |соответствующих итерациях | | |( начало вычислений|1 |2 ( оптимум| | |) | |) | |Z |0 |0 |2455/11 | |1 |1000 |1000 |1000/55 | |2 |0 |0 + D2 |91/11 + D2 | Найдем интервал ограничивающий величину D2 X1 = 1000/55 - ( 50/55 )D2 ( 1 ) X2 = 91/11 + ( 1/22 )D2 ( 2 ) Для определения допустимого интервала изменения D1 рассмо- трим два случая . Случай 1: D2 => 0 Решаем неравенства : ( 1 ) ( 50/55 )D2 <= 1000/55 из этого неравенства следует , что D2 <= 20 ( 2 ) Очевидно , что 2-ое уравнение неотрицательно на данном участке . Объединяя 2 уравнения для Случая 1 мы получим интервал для D2 . D2 О [ 0 ; 20 ] Случай 2: D2 < 0 . Решаем неравенства : ( 1 ) ( 50/55 )D2 => - 1000/55 . Из этого следует , что D2 <= 20 ( 2 ) ( 1/22 )D2 => - 91/11 . Из этого следует , что D2 => - 200 Объединяя 2 уравнения для Случая 2 мы получим интервал для D2 . D2 О [ - 200 ; 0 ] Объединяя 2 случая мы получим интервал [ - 200 ; 20 ] Максимальное изменение коэффициентов удельной прибыли ( стоимости ) Наряду с определением допустимых изменений запасов ресур- сов представляет интерес и установление интервала допустимых изменений коэффициентов удельной прибыли ( или стоимости ) . Следует отметить , что уравнение целевой функции никогда не используется в качестве ведущего уравнения . Поэтому лю- бые изменения коэффициентов целевой функции окажут влияние только на Z-уравнение результирующей симплекс-таблицы . Это означает , что такие изменения могут сделать полученное решение неоптимальным . Наша цель заключается в том , чтобы найти интер- валы значений изменений коэффициентов целевой функции ( рас- сматривая каждый из коэффициентов отдельно ) , при которых оп- тимальные значения переменных остаются неизменными . Чтобы показать, как выполняются соответствующие вычисле- ния , положим , что удельный объем сбыта , ассоциированной с переменной X1 изменяется от 1 до 1 + d1 где d1 может быть как положительным , так и отрицательным числом . Целевая функция в этом случае принимает следующий вид: Z = ( 1 + d1 )X1 + 25X2 Если воспользоваться данными начальной симплекс-таблицы и выполнить все вычисления , необходимые для ( получения заключн- тельной симплекс-таблицы , то последнее Z-уравнение будет выгля- деть следующим образом: |Базисные |X1 |X2 |S1 |S2 |Решение | |переменные | | | | | | |Z |0 |0 |27/110+1/55|5/22-50/55|2455/11+1000/5| | | | |d1 |d1 |5d1 | Коэффициенты при базисных переменных X1 , X2 и остаточных я равными нулю . Это уравнение отличается от Z-уравнения до введения d1 , только наличием членов , содержащих d1 . Коэффициенты при d1 равны кoэффициентам при соответствующих переменных в Z-уравнении симплекс-таблицы для полученного ранее оптимального решения |Базисные |X1 |X2 |S1 |S2 |Решение | |переменные | | | | | | |X1 |1 |0 |1/55 |-50/55 |1000/55 | Мы рассматриваем X1 - уравнение , так как коэффициент именно при этон переменной в выражении для целевои функции изменился на d1 . Оптимальные значения переменных будут оставаться неизмен- ными при значениях d1 , удовлетворяющих условию неотрицатель- ности ( задача на отыскание максимума ) всех коэффициентов при не- базисных переменных в Z-уравнении . Таким образом , должны выполняться следующие неравенства : 27/110 + 1/55d1 => 0 5/22 - 50/55d1 => 0 Из первого неравенства получаем , что d1 => - 13,5 , а из второго следует что d1 <= 1/4 . Эти результаты определяют пределы изменения коэффициента C1 в виде следующего соотношения : - 13,5 <= d1 <= 1/4 . Та- ким образом , при уменьшении коэффициента целевой функции при переменной X1 до значения , равного 1 + ( - 13,5 ) = - 12,5 или при его увеличении до 1 + 13,5 = 14,5 оптимальные значения переменных остаются неизменными . Однако оптимальное значение Z будет изменяться ( в соответствии с выражением 2455/11 + 1000/55d1 , где - 13,5 <= d1 <= 1/4 X2 изменяется от 25 до 25 + d2 где d2 может быть как положительным , так и отрицательным числом . Целевая функция в этом случае принимает следующий вид: Z = ( 25 + d2 )X2 + X1 Все предыдущее обсуждение касалось исследования изменения коэффициента при переменной , которой поставлено в соответствие ограничение , фигурирующее в симплекс-таблице . Однако такое ограничение имеется лишь в том случае , когда данная переменная является базисной ( например X1 и X2 ) . Если переменная небазисная , то в столбце , содержащем базисные переменные , она не будет представлена . Любое изменение коэффициента целевой функции при небазисной переменной приводит лишь к тому , что в заключительной симплкс-таблице изменяется только этот коэффициент . Рассмотрим в качестве иллюстрации случай , когда коэффициент при переменной S1 ( первой остаточной переменной ) изменяется от 0 до d3 . Выполнение преобразований , необходимых для получения заключительной симплекс таблицы , приводит к следующему результирующему Z-уравнению : |Базисные |X1 |X2 |S1 |S2 |Решение | |переменные | | | | | | |Z |0 |0 |27/110+1/55|5/22|2455/11 | | | | |d1 | | |