Построение экономической модели с использованием симплекс-метода
СОДЕРЖАНИЕ: Моделирование как метод научного познания. Введение в симплекс-метод. Словесное описание. Математическое описание. Представление пространства решений стандартной задачи линейного программирования. Вычислительные процедуры симплекс-метода..
Курсовая работа
Моделирование как метод научного познания.
Моделирование в научных исследованиях стало применяться еще в глубокой древности и постепенно захватывало все новые области научных знаний : техническое конструирование, строительство и архитектуру, астрономию, физику, химию, биологию и, наконец, общественные науки. Большие успехи и признание практически во всех отраслях современной науки принес методу моделирования ХХ в. Однако методология моделирования долгое время развивалась независимо отдельными науками. Отсутствовала единая система понятий, единая терминология. Лишь постепенно стала осознаваться роль моделирования как универсального метода научного познания.
Термин модель широко используется в различных сферах человеческой деятельности и имеет множество смысловых значений. Рассмотрим только такие модели, которые являются инструментами получения знаний.
Модель это такой материальный или мысленно представляемый объект, который в процессе исследования замещает объект-оригинал так, что его непосредственное изучение дает новые знания об объекте-оригинале.
Под моделирование понимается процесс построения, изучения и применения моделей. Оно тесно связано с такими категориями, как абстракция, аналогия, гипотеза и др. Процесс моделирования обязательно включает и построение абстракций, и умозаключения по аналогии, и конструирование научных гипотез.
Главная особенность моделирования в том, что это метод опосредованного познания с помощью объектов-заместителей. Модель выступает как своеобразный инструмент познания, который исследователь ставит между собой и объектом и с помощью которого изучает интересующий его объект. Именно эта особенность метода моделирования определяет специфические формы использования абстракций, аналогий, гипотез, других категорий и методов познания.
Необходимость использования метода моделирования определяется тем, что многие объекты ( или проблемы, относящиеся к этим объектам ) непосредственно исследовать или вовсе невозможно, или же это исследование требует много времени и средств.
Моделирование циклический процесс. Это означает, что за первым четырехэтапным циклом может последовать второй, третий и т.д. При этом знания об исследуемом объекте расширяются и точняются, а исходная модель постепенно совершенствуется. Недостатки, обнаруженные после первого цикла моделирования, бусловленные малым знанием объекта и ошибками в построении модели, можно исправить в последующих циклах. В методологии моделирования, таким образом, заложены большие возможности саморазвития.
Словесное описание
Фирма, производящая некоторую продукцию осуществляет её рекламу двумя способами через радиосеть и через телевидение. Стоимость рекламы на радио обходится фирме в 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 было показано, что правая и левая части ограничений линейной модели могут быть связаны знаками =, = и =. Кроме того, переменные, фигурирующие в задачах ЛП, могут быть неотрицательными или не иметь ограничения в знаке. Для построения общего метода решения задач ЛП соответствующие модели должны быть представлены в некоторой форме, которую назовем стандатрной формой линейных оптимизационных моделей. При стандартной форме линейной модели
Все ограничения записываются в виде равенств с неотрицательной правой частью ;
Значения всех переменных модели неотрицательны ;
Целевая функция подлежит максимизации или минимизации.
Покажем, каким образом любую линейную модель можно привести к стандартной.
Ограничения
Исходное ограничение, записанное в виде неравенства типа = ( =),
можно представить в виде равенства, прибавляя остаточную переменную к левой части ограничения ( вычитая избыточную переменную из левой части ).
Например, в левую часть исходного ограничения
5X1 + 100X2 = 1000
вводистя остаточная переменная S1 0, в результате чего исходное неравенство обращается в равенство
5X1 + 100X2 + S1 = 1000, S1 = 0
Если исходное ограничение определяет расход некоторого ресурса, переменную S1 следует интерпретировать как остаток, или неиспользованную часть, данного ресурса.
Рассмотрим исходное ограничение другого типа :
X1 2X2 = 0
Так как левая часть этого ограничения не может быть меньше правой, для обращения исходного неравенства в равенство вычтем из его левой части избыточную переменную S2 0. В результате получим
X1 2X2 S2 = 0, S2 = 0
Правую часть равенства всегда можно сделать неотрицательной, умножая оби части на -1.
Например равенство X1 2X2 S2 = 0 эквивалентно равенству X1 + 2X2 + S2 = 0
Знак неравенства изменяется на противоположный при умножении обеих частей на -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 ). Решение, соответствующее этой точке, обычно называют начальным решением. От исходной точки осуществляется переход к некоторой смежной угловой точке.
Выбор каждой последующей экстремальной точки при использовании симплекс-метода определяется следующими двумя правилами.
Каждая последующая угловая точка должна быть смежной с предыдущей. Этот переход осуществляется по границам ( ребрам ) пространства решений.
Обратный переход к предшествующей экстремальной точке не может производиться.
Таким образом, отыскание оптимального решения начинается с некоторой допустимой угловой точки, и все переходы осуществляются только к смежным точкам, причем перед новым переходом каждая из полученных точек проверяется на оптимальность.
Определим пространство решений и угловые точки агебраически. Требуемые соотнощшения устанавливаются из указанного в таблице соответствия геометрических и алгебраических определений.
| Геометрическое определение | Алгебраическое определение ( симплекс метод ) |
| Пространство решений | Ограничения модели стандартной формы |
| Угловые точки | Базисное решение задачи в стандартной форме |
Представление пространства решений стандартной задачи линейного программирования.
Линейная модель, построенная для нашей задачи и приведенная к стандартной форме, имеет следующий вид :
Максимизировать
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 )
Новое 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 ).
К получению симплекс-таблицы, соответствующей новой итерации, приводят следующие вычислительные операции метода Гаусса—Жордана.
Новое ведущее S1 уравнение = Предыдущее S1 уравнение / ( 55 ).
| Базисные переменные | Z | X1 | X2 | S1 | S2 | Решение |
| Z | ||||||
| S1 | 0 | 1 | 0 | 1/55 | 50/55 | 1000/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. Однако при этом не фиксируется интервал значений увеличения запасов ресурса, при которых интенсивность улучшения целевой функции остается постоянной. Для большинства практических ситуаций логично предположить наличие верхнего предела увеличения запасов, при превышении которого соответствующее ограничение становится избыточным, что в свою очередь приводит к новому базисному решению и соответствующим ему новым теневым ценам. Ниже определяется нитервал значений запасов ресурса, при которых соответствующее ограничение не становится избыточным.
Максимальное изменение запаса ресурса
При решении вопроса о том, запас какого из ресурсов следует увеличивать в первую очередь, обычно используются теневые цены Чтобы определить интервал значений изменения запаса ресурса, при которых теневая цена данного ресурса, ( фигурирующая в заключительной симплекс-таблице, остается неизменной, необходимо выполнить ряд дополнительных вычислений. Рассмотрим сначала соответствующие вычислительные процедуры, а затем покажем, как требуемая информация может быть получена из симплекс-таблицы для оптимального решения.
В нашей задаче запас первого ресурса изменился на т. е. запас бюджета составит 1000 + . При положительной величине запас данного ресурса увеличивается, при отрицательной — уменьшается. Как правило, исследуется ситуация, когда объем ресурса увеличивается ( 0 ), однако, чтобы получить результат в общем виде, рассмотрим оба случая.
Как изменится симплекс-таблица при изменении величины запаса ресурса на? Проще всего получить ответ на этот вопрос. если ввести в правую часть первого ограничения начальной симплекс-таблицы и затем выполнить все алгебраические преобразования, соответствующие последовательности итераций. Поскольку правые части ограничений никогда не используются в качестве ведущих элементов, то очевидно, что на каждой итерации будет оказывать влияние только на правые части ограничений.
| Уравнение | Значения элементов правой части на соответствующих итерациях | ||
| ( начало вычислений ) | 1 | 2 ( оптимум ) | |
| Z | 0 | 0 | 2455/11 |
| 1 | 1000 | 1000 + | 1000/55 + |
| 2 | 0 | 0 | 91/11 |
Фактически вce изменения правых частей ограничений, обусловленные введением , можно определить непосредственно по данным, содержащимся в симплекс-таблицах. Прежде всего заметим, что на каждой итерации новая правая часть каждого ограничения представляет собой сумму двух величин: 1) постоянной и 2) члена, линейно зависящего от . Постоянные соответствуют числам, которые фигурируют на соответствующих итерациях в правых частях ограничений симплекс-таблиц до введения . Коэффициенты при во вторых слагаемых равны коэффициентам при S1 на той же итерации. Так, например, на последнеи итерации ( оптимальное решение ) постоянные ( 2455/11 ; 1000/55 ; 91/11 ) представляют собои числа, фигурирующие в правых частях ограничении оптимальной симплекс-таблицы до введенияКоэффициенты ( 27/110 ; 1/55 ; 1/110 ) равны коэффициентам при S1 в той же симплекс-таблице потому, что эта переменная связана только с первым ограничением. Другими словами, при анализе влияния изменений в правой части второго ограничения нужно пользоваться коэффициентами при переменной S2.
Какие выводы можно сделать из полученных результатов? Так как введение сказывается лишь на правой части симплекстаблицы, изменение запаса ресурса может повлиять только на допустимость решения. Поэтому не может принимать значений, при которых какая-либо из ( базисных ) переменных становится отрицательной. Из этого следует, что величина должна быть ограничена таким интервалом значений, при которых выполняется условие неотрицательности правых частей ограничений в результирующей симплекс-таблице, т. е.
X1 = 1000/55 + ( 1/55 ) 0 ( 1 )
X2 = 91/11 + ( 1/110 )= 0 ( 2 )
Для определения допустимого интервала изменения рассмотрим два случая.
Случай 1: 0 Очевидно, что оба неравнества при этом условии всегда будут неотрицательными.
Случай 2: 0. Решаем неравенства : ( 1 )
( 1/55 )= 1000/55. Из этого следует, что = 1000
( 2 )
( 1/110 )= 91/11. Из этого следует, что = 1000
Объединяя результаты, полученные для обоих случаев, можно сделать вывод, что при 1000 = = + решение рассматриваемой задачи всегда будет допустимым, любое значение , выходящее за пределы указанного интервала, приведет к недопустимости решения и новой совокупности базисных переменных.
Теперь рассмотрим в каких пределах может изменяться запас ресурса 2 анализ проведем по аналогичной схеме :
Запас 2-ого ресурса изменился на т. е. запас рекламного времени составит 0 + Как изменилась симплекс-таблица при изменении величины запаса ресурса напроиллюстрировано ниже.
| Уравнение | Значения элементов правой части на соответствующих итерациях | ||
| ( начало вычислений ) | 1 | 2 ( оптимум ) | |
| Z | 0 | 0 | 2455/11 |
| 1 | 1000 | 1000 | 1000/55 |
| 2 | 0 | 0 + | 91/11 + |
Найдем интервал ограничивающий величину
X1 = 1000/55 ( 50/55 )
X2 = 91/11 + ( 1/22 )
Для определения допустимого интервала изменения рассмотрим два случая.
Случай 1: 0 Решаем неравенства : ( 1 )
( 50/55 )1000/55 из этого неравенства следует, что
Очевидно, что 2-ое уравнение неотрицательно на данном участке.
Объединяя 2 уравнения для Случая 1 мы получим интервал для
[ 0 ; 20 ]
Случай 2: 0. Решаем неравенства : ( 1 )
( 50/55 )1000/55. Из этого следует, что 20
( 2 )
( 1/22 )91/11. Из этого следует, что
Объединяя 2 уравнения для Случая 2 мы получим интервал для
[ 200 ; 0 ]
Объединяя 2 случая мы получим интервал [ 200 ; 20 ]
Максимальное изменение коэффициентов удельной прибыли ( стоимости )
Наряду с определением допустимых изменений запасов ресурсов представляет интерес и установление интервала допустимых изменений коэффициентов удельной прибыли ( или стоимости ). Следует отметить, что уравнение целевой функции никогда не используется в качестве ведущего уравнения. Поэтому любые изменения коэффициентов целевой функции окажут влияние только на Z-уравнение результирующей симплекс-таблицы. Это означает, что такие изменения могут сделать полученное решение неоптимальным. Наша цель заключается в том, чтобы найти интервалы значений изменений коэффициентов целевой функции ( рассматривая каждый и з коэффициентов отдельно ), п ри которых оптимальные значе ни я переменных остаются неизме нными.
Чтобы пок азать , как выполняются соответствующие вычислен ия, положим, что удельный объем сбыта, ассоциированной с пере менной
X1 изменяется от 1 до 1 + где может быть как положительным, так и отрицательным числом. Целевая функция в этом случае принимает следующий вид:
Z = ( 1 + X1 + 25X2
Если воспользоваться данными начальной симплекс-таблицы и выполнить все вычисления, необходимые для ( получения заключнтельной симплекс-таблицы, то последнее Z-уравнение будет выглядеть следующим образом:
| Базисные переменные | X1 | X2 | S1 | S2 | Решение |
| Z | 0 | 0 | 27/110+1/55 | 5/22-50/55 | 2455/11+1000/55 |
Коэффициенты при базисных переменных X1, X2 и остаточных я равными нулю. Это уравнение отличается от Z-уравнения до введения, только наличием членов, содержащих . Коэффициенты при равны кoэффициентам при соответствующих переменных в Z-уравнении симплекс-таблицы для полученного ранее оптимального решения
| Базисные переменные | X1 | X2 | S1 | S2 | Решение |
| X1 | 1 | 0 | 1/55 | -50/55 | 1000/55 |
Мы рассматриваем X1 уравнение, так как коэффициент именно при этон переменной в выражении для целевои функции изменился на.
Оптимальные значения переменных будут оставаться неизменными при значениях , удовлетворяющих условию неотрицательности ( задача на отыскание максимума ) всех коэффициентов при небазисных переменных в Z-уравнении. Таким образом, должны выполняться следующие неравенства :
27/110 + 1/55
5/22 50/55
Из первого неравенства получаем, что = 13,5, а из второго следует что = 1/4. Эти результаты определяют пределы изменения коэффициента C1 в виде следующего соотношения : 13,5 = = 1/4. Таким образом, при уменьшении коэффициента целевой функции при переменной X1 до значения, равного 1 + ( 13,5 ) = 12,5 или при его увеличении до 1 + 13,5 = 14,5 оптимальные значения переменных остаются неизменными. Однако оптимальное значение Z будет изменяться ( в соответствии с выражением 2455/11 + 1000/55, где 13,5 = = 1/4
X2 изменяется от 25 до 25 + где может быть как положительным, так и отрицательным числом. Целевая функция в этом случае принимает следующий вид:
Z = ( 25 + X2 + X1
Все предыдущее обсуждение касалось исследования изменения коэффициента при переменной, которой поставлено в соответствие ограничение, фигурирующее в симплекс-таблице. Однако такое ограничение имеется лишь в том случае, когда данная переменная является базисной ( например X1 и X2 ). Если переменная небазисная, то в столбце, содержащем базисные переменные, она не будет представлена.
Любое изменение коэффициента целевой функции при небазисной переменной приводит лишь к тому, что в заключительной симплкс-таблице изменяется только этот коэффициент. Рассмотрим в качестве иллюстрации случай, когда коэффициент при переменной S1 ( первой остаточной переменной ) изменяется от 0 до Выполнение преобразований, необходимых для получения заключительной симплекс таблицы, приводит к следующему результирующему Z-уравнению :
| Базисные переменные | X1 | X2 | S1 | S2 | Решение |
| Z | 0 | 0 | 27/110+1/55 | 5/22 | 2455/11 |