Построение экономической модели с использованием симплекс-метода

Курсовая работа

Тема: Построение экономической модели с использованием симплекс-метода .

Работу выполнил

студент УТФ-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 было показано , что правая и левая части ограничений
линейной модели могут быть связаны знаками <= , = и => . Кроме того ,
переменные , фигурирующие в задачах ЛП , могут быть неотрицательными или
не иметь ограничения в знаке . Для построения общего метода решения
задач ЛП соответствующие модели должны быть представлены в некоторой
форме , которую назовем стандатрной формой линейных оптимизационных
моделей . При стандартной форме линейной модели

Все ограничения записываются в виде равенств с неотрицательной правой
частью ;

Значения всех переменных модели неотрицательны ;

Целевая функция подлежит максимизации или минимизации .

Покажем , каким образом любую линейную модель можно привести к
стандартной .

Ограничения

Исходное ограничение , записанное в виде неравенства типа <= ( =>) ,

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

Например , в левую часть исходного ограничения

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 . Однако при этом

не фиксируется интервал значений увеличения запасов ресурса ,

при которых интенсивность улучшения целевой функции остается

постоянной . Для большинства практических ситуаций логично пред-

положить наличие верхнего предела увеличения запасов , при пре-

вышении которого соответствующее ограничение становится избы-

точным , что в свою очередь приводит к новому базисному решению

и соответствующим ему новым теневым ценам . Ниже определяется

нитервал значений запасов ресурса , при которых соответствую-

щее ограничение не становится избыточным .

Максимальное изменение запаса ресурса

При решении вопроса о том , запас какого из ресурсов следует

увеличивать в первую очередь , обычно используются теневые цены

Чтобы определить интервал значений изменения запаса ресурса ,

при которых теневая цена данного ресурса , ( фигурирующая в заклю-

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

соответствующие вычислительные процедуры , а затем покажем , как

требуемая информация может быть получена из симплекс-таблицы

для оптимального решения .

В нашей задаче запас первого ресурса изменился на D1 т. е. запас бюджета
составит 1000 + D1 . При положительной величине D1 запас данного
ресурса увеличивается , при отрицательной — уменьшается . Как правило ,
исследуется ситуация , когда объем ресурса увеличивается ( D1
> 0 ) , однако , чтобы получить результат в общем виде , рассмотрим оба
случая .

Как изменится симплекс-таблица при изменении величины за-

паса ресурса на D1 ? Проще всего получить ответ на этот вопрос .

если ввести D1 в правую часть первого ограничения начальной сим-

плекс-таблицы и затем выполнить все алгебраические преобразова-

ния , соответствующие последовательности итераций . Поскольку

правые части ограничений никогда не используются в качестве

ведущих элементов , то очевидно , что на каждой итерации D1 будет

оказывать влияние только на правые части ограничений .

Уравнение Значения элементов правой части на соответствующих итерациях

( начало вычислений ) 1 2 ( оптимум )

Z 0 0 2455/11

1 1000 1000 + D1 1000/55 + 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/55d1 5/22-50/55d1 2455/11+1000/55d1



Коэффициенты при базисных переменных 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/55d1 5/22 2455/11