Построение экономической модели c использованием симплекс-метода
Пример. В качестве ресурсов внешней среды при реализации функции "подготовка специалистов под требования конкретного предприятия" можно рассматривать:
•финансовые ресурсы, поступающие от предприятия в виде денежной компенсации за дополнительную подготовку;
•материальные ресурсы, представленные в виде оригинального обо-рудования, приборов и устройств, которые студент должен изучить и уметь пользоваться; •постановления министерства общего и профессионального образования Российской Федерации, регламентирующие права и обязанности вуза, предприятия и студента.
1.1.7. Основные этапы системной деятельности
Использование приведенных понятий и определений в системной деятельности позволяет ответить на совокупность взаимосвязанных вопросов: "что?", "как?", "кто?" и "чем?". Другими словами следует ответить на вопросы: наличие либо отсутствие проблемной ситуации и определить основные направления (цели) ее ликвидации; какие функции системы при этом надо реализовать и какой структурой; и, наконец, есть ли для этой реализации соответствующие ресурсы.
Легко заметить, что цепочка "проблемная ситуация, цели, функция, структура, внешние ресурсы" образует логически обоснованную (на содержательном уровне) последовательность системной деятельности (рис.1.6), и может использоваться как на этапах анализа (исследования), так и синтеза (проектирования) систем.

![]()
![]()
Рис.1.6. Модель этапов системной деятельности
В данном случае сплошной линией показаны этапы синтеза, а пунктирной - анализа.
1.2. Модели систем
1.2.1. Определение и классификация моделей систем
Множество окружающих нас предметов и явлений обладают наличием входных свойств. Процесс познания этих свойств состоит в том, что мы создаем для себя некоторое представление об изучаемом объекте, помогающее лучше понять его внутреннее состояние, законы функционирования, основные характеристики. Такое представление, выраженное в той либо иной форме называется моделью. Как отмечается в [1], под моделью следует понимать любую другую систему, обладающую той же формальной структурой при условии, если:
•между системными характеристиками модели и оригиналом существует соответствие; •модель более проста и доступна для изучения и исследования основных свойств объекта-оригинала.
Любая модель есть объект-заменитель объекта-оригинала, обеспечивающий изучение некоторых свойств оригинала.
Замещение одного объекта другим с целью получения информации о важнейших свойствах объекта-оригинала с помощью объекта-модели можно назвать моделированием, т.е. моделирование - это представление объекта моделью для получения информации об объекте путем проведения эксперимента с его моделью.
С точки зрения философии моделирование следует рассматривать как эффективное средство познания природы. При этом процесс моделирования предполагает наличие: объекта исследования, исследователя-экспериментатора, модели.
В автоматизированных системах обработки информации и управления в качестве объекта моделирования могут выступать:
•производственные процессы; процессы административного управления; процессы функционирования комплекса технических средств; процессы организации и функционирования информационного
•обеспечения АСУ; процессы функционирования программного обеспечения АСУ. Преимущества моделирования состоят в том, что появляется
•возможность сравнительно простыми средствами изучать свойства системы, изменять ее параметры, вводить целевые и ресурсные характеристики внешней среды.
Как правило, моделирование используется:
1.для исследования системы до того, как она спроектирована с целью определения ее основных характеристик и правил взаимодействия элементов между собой и с внешней средой;
2.на этапе проектирования для анализа и синтеза различных видов структур и выбора наилучшего варианта реализации с учетом сформулированных критериев оптимальности и ограничений;
3.на этапе эксплуатации системы для получения оптимальных режимов функционирования и прогнозных оценок ее развития.
При этом одну и ту же систему можно описать различными типами моделей. Например, транспортную сеть некоторого района можно промоделировать электрической схемой, гидравлической системой, математической моделью с использованием аппарата теории графов.
Кратко остановимся на классификации используемых на практике моделей:
•по способу описания модели подразделяются на описательные (не-формализованные) и формализованные;
•по природе возникновения целей системы модели подразделяются на познавательные (теоретические цели) и прагматические (практические цели). При этом познавательные цели являются формой организации и пред-ставления знаний, средством соединения новых знаний с имеющимися. Прагматические модели являются, как правило, средством управления, средством организации практических действий, способом представления образцово правильных действий. Следует заметить, что при возникновении различий между моделью и реальной действительностью, в первом случае речь идет о корректировке модели, а во втором случае - к изменению реальности, т.е. в соответствии с полученным на модели решением изменить свойству и структуре системы;
•по природе используемых элементов модели подразделяются на физические (аналоговые, электрические, графические, чертеж, фотографии) и математические.
В дальнейшем будем изучать только класс математических моделей, под которыми понимают совокупность математических выражений, описывающих поведение (структуру) системы и те условия (возмущения, ограничения), в которых она работает. В совою очередь, математические модели в зависимости от используемого математического аппарата подразделяются на:
•статистические и динамические;
•детерминированные и вероятностные;
•дискретные и непрерывные;
•аналитические и численные.
Статистические модели описывают поведение объекта в какой-либо момент времени, а динамические отражают поведение объекта во времени. Детерминированные модели описывают процессы, в которых отсутствуют (не учитываются) случайные факторы, в свою очередь, вероятностные модели отражают случайные процессы - события. Дискретные модели описывают процессы, описываемые дискретными переменными, в свою очередь, непрерывные - непрерывными. Аналитические модели описывают процесс в виде некоторых функциональных отношений или (и) логических условий. Численные модели отражают элементарные явления с сохранением их логической структуры и последовательности протекания во времени.
1.2.2. Уровни моделей системы*
Первым наиболее простым и абстрактным уровнем описания системы является модель, так называемого "черного ящика". В этом случае предполагается, что выделенная система связана со средой через совокупность входов и выходов. Выходы модели соответствуют понятиям целей системы, а входы - соответственно понятиям ресурсов и ограничений (рис. 1.7). При этом предполагается, что мы ничего не знаем и не хотим знать о внутреннем содержании системы. Модель в этом случае отражает два важных и существенных ее свойства: целостность и обособленность от среды.
Такая модель, несмотря на ее внешнюю простоту и отсутствие сведений о внутренней структуре, оказывается часто полезной на первом этапе системного анализа.
Например, для анализа работоспособности бытового телевизора необходимо проверить входы (шнур электропитания, антенну, ручки управления и настройки) и выходы (экран кинескопа и выходные динамики); системное описание какого-либо производственного процесса необходимо начинать с анализа его информационного и материального входов и выходов - планируемых и результирующих показателей деятельности, качество входных ресурсов и конечных продуктов и т.д.

Рис. 1.7
Следует отметить, что существует множество систем, внутреннее устройство которых невозможно либо нецелесообразно описывать, и в этом случае модель "черного ящика" является единственным вариантом их исследования. Например, мы не знаем как устроен организм человека; в то же время необходимо изучать влияние и поведенческий аспект средств массовой информации, влияние на живой организм лекарственным препаратов и т.д. Формализация модели "черного ящика" основывается на задании двух множеств входных и выходных переменных, и никаких других отношений между множествами не фиксируется.
Вместе с тем следует отметить, что построение модели "черного ящика" не является тривиальной задачей, так как ответ на вопрос о содержании множеств не всегда однозначен.
Построение модели основывается на выборе из бесконечного множества связей системы со средой их конечного множества, адекватно отражающего цели исследования. Очевидно. Что такие модели не надо сводить к моносистеме (т.е. системе с одним входом и выходом), а для обоснования необходимого и достаточного количества параметров множеств X и Y широко использовать методы математической статистики, привлекать опытных экспертов.

Следующим
уровнем моделирования
сложных систем
являются модели
состава систем.
При рассмотрении
любой системы
прежде всего
обнаруживается,
что ее целостность
и обособленность
выступают как
внешнее свойство.
Вместе с тем
внутренняя
структура
системы также
является
многообразной,
неоднородной
и состоит из
множества
неделимых
функциональных
элементов.
Декомпозиция
внутренней
структуры
"черного ящика"
на более мелкие
составляющие
(подсистемы,
отдельные
элементы) позволяют
строить модели
состава систем
(рис. 1.8).
Рис. 1.8. Модель состава системы
Например, если в качестве системы рассматривать производственное подразделение, то в качестве подсистемы выступают производственные участки, а в качестве отдельных элементов - оборудование, сырье, рабочие; сис-тема телевидения состоит из аппаратуры передачи, каналов связи, аппаратуры приема.
Построение модели состава в силу многообразия природы и форм элементов также не является простым делом. Это можно объяснить тремя факторами:
1.неоднозначностью понятия "элементарного элемента";
2.многоцелевым характером объекта, объективно требующим выделить под каждую цель соответствующий ей состав;
3.условностью (субъективностью) процедуры деления целого на части (системы на подсистемы, элементы).
Простота и доступность моделей "черного ящика" и состава позволяет решать с их использованием множество практических задач. Вместе с тем для более детального (глубокого) изучения систем необходимо устанавливать в модели состав отношения (связи) между элементами. Описание системы через совокупность необходимых и достаточных для достижения целей отношений между элементами назовем моделью структуры системы.
Перечень связей между элементами, на первый взгляд, является не-сколько отвлеченной, абстрактной моделью. На самом деле как рассматривать связи, если не рассмотрены сами элементы.
ПРАКТИЧЕСКАЯ ЧАСТЬ
Словесное описание
Фирма , производящая некоторую продукцию осуществляет её рекламу двумя способами через радиосеть и через телевидение . Стоимость рекламы на радио обходится фирме в 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