Реферат: Построение экономической модели c использованием симплекс-метода
ОГЛАВЛЕНИЕ
Аннотация 3
Введение. 4
1. ОСНОВЫ СИСТЕМНОГО ПОДХОДА 5
1.1.Основные понятия и определения системного подхода 5
1.1.1. Понятие системы и среды 7
1.1.2. Понятие проблемной ситуации 11
1.1.3. Понятие цели системы 14
1.1.4. Понятие функций системы 16
1.1.5. Структура системы 17
1.1.6. Внешние условия системы 20
1.1.7. Основные этапы системной деятельности 21
1.2. Модели систем 22
1.2.1. Определение и классификация моделей систем 22
1.2.2. Уровни моделей системы* 25
ПРАКТИЧЕСКАЯ ЧАСТЬ 28
Словесное описание 28
Математическое описание . 29
Ограничения 30
Переменные 31
Целевая функция 32
Симплекс-метод . 33
Представление пространства решений стандартной задачи
линейного программирования . 34
Вычислительные процедуры симплекс-метода . 37
Оптимальное решение 42
Статус ресурсов 43
Ценность ресурса 45
Максимальное изменение запаса ресурса 47
Максимальное изменение коэффициентов удельной 50
прибыли ( стоимости ) 50
Заключение 52
Список литературы : 53
Аннотация
В данной курсовой работе рассматриваются основные принципы построения системы, а также практическое применение полученных знаний на примере распределения финансов фирмы.
Введение.
Сегодня в для любого гражданина Украины не секрет, что экономика его страны практически перешла на рыночные рельсы и функционирует исключительно по законам рынка. Каждое предприятие отвечает за свою работу само и само принимает решения о дальнейшем развитии. Современные условия рыночного хозяйствования предъявляют к методам прогнозирования очень высокие требования, ввиду все возрастающей важности правильного прогноза для судьбы предприятия, да и экономики страны в целом.
Именно прогнозирования функционирования экономики регионов или даже страны, на мой взгляд нужно уделять пристальное внимание на данный момент, потому что за пеленой сиюминутных собственных проблем все почему-то забыли о том, что экономика страны тоже должна управляться, а следовательно и прогнозирование показателей ее развития должно быть поставлено на твердую научную основу.
Целью данной курсовой работы явилось изучение практического опыта использования экономико-статистических методов прогнозирования.
Моделирование в научных исследованиях стало применяться еще в глубокой древности и постепенно захватывало все новые области научных знаний : техническое конструирование , строительство и архитектуру , астрономию , физику , химию , биологию и , наконец , общественные науки . Большие успехи и признание практически во всех отраслях современной науки принес методу моделирования ХХ в . Однако методология моделирования долгое время развивалась независимо отдельными науками . Отсутствовала единая система понятий, единая терминология . Лишь постепенно стала осознаваться роль моделирования как универсального метода научного познания
Термин "модель" широко используется в различных сферах человеческой деятельности и имеет множество смысловых значений . Рассмотрим только такие "модели", которые являются инструментами получения знаний .
Модель - это такой материальный или мысленно представляемый объект, который в процессе исследования замещает объект-оригинал так, что его непосредственное изучение дает новые знания об объекте-оригинале .
Под моделирование понимается процесс построения , изучения и применения моделей . Оно тесно связано с такими категориями , как абстракция , аналогия , гипотеза и др . Процесс моделирования обязательно включает и построение абстракций , и умозаключения по аналогии, и конструирование научных гипотез.
Главная особенность моделирования в том , что это метод опосредованного познания с помощью объектов-заместителей . Модель выступает как своеобразный инструмент познания , который исследователь ставит между собой и объектом и с помощью которого изучает интересующий его объект . Именно эта особенность метода моделирования определяет специфические формы использования абстракций , аналогий , гипотез , других категорий и методов познания .
Необходимость использования метода моделирования определяется тем, что многие объекты ( или проблемы , относящиеся к этим объектам ) непосредственно исследовать или вовсе невозможно, или же это исследование требует много времени и средств.
Моделирование - циклический процесс . Это означает , что за первым четырехэтапным циклом может последовать второй , третий и т.д. При этом знания об исследуемом объекте расширяются и точняются, а исходная модель постепенно совершенствуется . Недостатки , обнаруженные после первого цикла моделирования , бусловленные малым знанием объекта и ошибками в построении модели , можно исправить в последующих циклах . В методологии моделирования , таким образом , заложены большие возможности саморазвития .
1. ОСНОВЫ СИСТЕМНОГО ПОДХОДА
1.1.Основные понятия и определения системного подхода
Окружающие нас производственные, социальные, организационные и природные объекты обладают множеством различных свойств: они достаточно сложны, распределены в пространстве, динамичны во времени, поведение их описывается как детерминированными, так и стохастическими законами и т.д.
В управлении такими системами задействовано большое количество людей, громадные природные, материальные и энергетические ресурсы. В этой связи подход к объектам управления как к сложным системам выражает одну из главных особенностей современного этапа развития общества.
Умение распознать систему, декомпозировать ее на элементарные составляющие, определить законы управления каждой подсистемой и вновь синтезировать систему требует разработки ряда специальных формальных моделей , процедур алгоритмов. Еще философ Древнего Рима Квиантилиан утверждал, что любую сколь угодно сложную ситуацию можно полностью структурировать и описать, руководствуясь следующими семью вопросами [2] (рис. 1.1).
Рис. 1.1. Основные факторы системы
Наука, в рамках которой получили развитие исследования, направленные на решение вышеобозначенных проблем, получила название "теория систем" - "системный подход" - "системный анализ". Эта теория зародилась в 30-х годах ХХ века и в 50-е годы сформировалась как самостоятельное на-учное направление. У ее истоков стояли биологи Берталанфи, Р,Жерар, специалист по математическим проблемам в области биологии и психологии - А.Рапопорт, экономист - К. Боулдинг [8].
В дальнейшем эти исследования были продолжены в многочисленных работах зарубежных и отечественных ученых.: М. Месарочича, С. Оптнера, С. Янга, Я. Такахару, Р. Акоффа, А.А. Богданова, В.Н. Садовского, А.И. Уемова, Ю.И.Черняка, А.А. Денисова и др.
1.1.1. Понятие системы и среды
Понятие системы уточняется и развивается на протяжении развития самого системного анализа. Так, основоположник теории систем Людвиг фон Берталанфи определил систему как комплекс взаимодействующих элементов, находящихся в определенных отношениях друг с другом и со средой.
Таким образом исходным моментом в определении системы является ее противопоставление среде , т.е. среда - это все то, что не входит в систему, а система - это конечное множество объектов, каким-то образом выделенное из среды. Между средой и системой существует бесконечное множество взаимных связей, с помощью которых реализуется процесс взаимодей-ствия среды и системы. Выделение системы из среды и определение границ их взаимодействия является одной из первоочередных задач системного анализа. От правильности определения границ зависят не только выполняемые функции, эффективность и качество системы, но и нередко сама ее жизнедеятельность. С другой со стороны, диалектической основой системных исследований является принцип системности, суть которого сводится к тому, что система как нечто целое обладает свойствами, не присущими составляющим ее элементам. В этом случае при определении системы необходимо исходить из двух основополагающих понятий:
•система как совокупность взаимодействующих элементов; •система как целостная среда, обладающая новыми системообразую-щими свойствами.
С учетом вышеизложенного перечислим следующие отличительные качества системы:
•система есть нечто целое;
•система есть множество элементов, свойств и отношений;
•система есть организованное множество элементов;
•система есть динамическое множество элементов.
Тогда определение системы можно сконструировать следующим образом: система есть конечное множество функциональных элементов и отношений между ними, выделяемое из среды в соответствии с определен-ной целью, в рамках определенного временного интервала.
В этом случае под элементом принято понимать простейшую неделимую часть системы - подсистему. При этом ответ на вопрос, что является такой частью не может быть однозначным и зависит от целей рассмотрения объекта как системы.
Объективно, с точки зрения внешней среды, любая система существует как источник удовлетворения ее потребностей. Из этого следует, что простейшая модель взаимодействия между системой и средой выглядит следующим образом (рис.1.2).
Рис.1.2. Модель взаимодействия системы и среды
На вход системы из среды поступают:
•множество целей и ограничений - Z = {Zk} •множество ресурсов - X = {Xj}
Выводом из системы является множество конечных продуктов, благ и услуг ориентированных на удовлетворение потребностей внешней среды - Y = {Yi} .
При этом множество конечных продуктов и ресурсов можно классифицировать на следующие группы: материальные, информационные, финансовые, трудовые, энергетические.
В ряде случаев в классификаторе выходов системы помимо полезных конечных продуктов необходимо выделять отходы, т.е. конечные продукты, оказывающие негативное влияние на внешнюю среду.
На рис. 1.3 представлена обобщенная модель взаимодействия предприятия "как системы" с элементами ее внешней среды.
Рис. 1.3. Модель взаимодействия предприятия с элементами внешней среды
В качестве примера рассмотрим фрагмент модели взаимодействия учебного заведения с элементами внешней среды.
В качестве конечных продуктов учебного заведения можно рассмат-ривать следующие множества:
Y1- инженерные кадры;
Y11- инженерные кадры, подготовленные по типовым программам;
Y12- инженерные кадры, подготовленные по заказам органов власти и управления;
Y13- инженерные кадры, подготовленные по заказам финансовых ин-ститутов;
Y14- инженерные кадры, подготовленные по заказам конкретного предприятия и т.д.;
Y2- информационная продукция вуза;
Y21- учебно-методическая литература;
Y22- научно-техническая литература;
Y23- отчетная информация о деятельности вуза;
Y3- научно-технические разработки вуза;
Y4- кадры высшей квалификации.
В качестве входных ресурсов учебного заведения выделим:
X1 - финансовые ресурсы для организации учебного процесса;
X11 - федеральный бюджет;
X12 - местный бюджет;
X13 - внебюджетные фонды;
X14 - благотворительные фонды;
X15 - кредиты банков;
X2 - финансовые ресурсы для организации научно-исследовательской деятельности;
X3 - финансовые ресурсы для организации административно-хозяй-ственной деятельности;
X4 - абитуриенты, поступающие в вуз;
X41 - на основе госбюджетного финансирования;
X42 - по заказам органов власти и управления;
X43 - по заказам финансовых институтов;
X44 - по заказам конкретных промышленных предприятий.
В качестве множества целей и ограничений, определяющих деятельность вуза, можно рассматривать:
•по учебной деятельности -
Z11 - требования ГОС на подготовку специалистов по конкретной спе-циальности;
Z12 - требования органов власти и управления на подготовку специа-листов;
Z13 - требования финансовых структур на подготовку специалистов;
•по научно-исследовательской деятельности -
Z21 - требования федеральных органов к качеству выполнения госбюд-жетных тем;
Z22 - требования заказчиков к качеству выполнения хоздоговорных тем.
1.1.2. Понятие проблемной ситуации
Как было показано в предыдущем разделе, взаимодействие между системой и средой построено по следующей схеме: среда поставляет системе ресурсы, устанавливает цели, ограничения, а получает из системы и потребляет ее конечные продукты. Характерно, что КП системы принципиально не могут быть созданы в среде (в противном случае нет необходимости выделять систему из среды).
Возникшая либо назревающая степень неудовлетворения элементов внешней среды конечными продуктами системы, либо низкая эффективность взаимодействия элементов внешней среды с системой порождают новое по-нятие системного подхода - "проблемная ситуация" - возникшая либо назревающая степень неудовлетворения взаимосвязи между системой и средой. В этом случае очевидно, что перечень проблемных ситуаций можно определить исходя из анализа взаимосвязи элементов множеств:
Y={Yip} ; X={Xjp} ; Z={Zkp}
При проведении данного этапа системных исследований рекомендуется прежде всего четко сформулировать сущность проблемы и описать ситуацию, в которой она имеет место [4]. При этом содержание деятельности включает следующие этапы:
•установление содержания проблемы, т.е. уяснение, есть ли в действительности проблема либо она является надуманной;
•определение новизны проблемной ситуации;
•установление причин возникновения проблемной ситуации;
•определение степени взаимосвязи проблемных ситуаций;
•определение полноты и достоверности информации о проблемной ситуации; •определение возможности разрешения проблемы.
Определение существования проблемы предполагает проверку истинности или ложности формулировки проблемы и ее принадлежности. Проверка истинности существования проблемы должна осуществляться прежде всего по наличию в системе совокупности экономических и социальных потерь, а ее значимость - по критерию экономического, либо социального эффекта, получаемого в системе после ликвидации проблемной ситуации. Оценка же степени проблемности должна производится на сопоставлении фактических (в данный момент либо в будущем) значений целей с их плановыми либо нормативными значениями.
Определение новизны проблемной ситуации необходимо для выявления и установления возможных прецедентов или аналогий. Наличие прошлого опыта или нормативных рекомендаций позволяют существенно облегчить работу экспертов по выработке и принятию решений по ликвидации проблемы.
Установление причин (как в системе, так и во внешней среде) возникновения проблемы позволяет глубже понять закономерности функционирования объекта управления, вскрыть наиболее существенные факторы, приведшие к проблемной ситуации.
При анализе проблемной ситуации необходимо установить возможные взаимосвязи рассматриваемой проблемы с другими проблемами. При этом необходимо провести классификацию этих проблем на главные и второстепенные, общие и частные, срочные и несрочные. Анализ взаимосвязей проблем позволит четко и глубоко выявить причинно-следственные зависимости и способствовать выработке комплексного решения. Комплексность предполагает при выработке решения выдавать рекомендации по изменению не только исследуемой системы, но и внешней среды.
Большое значение в анализе имеет определение степени полноты и достоверности информации о проблемной ситуации. В случае полной информации нетрудно сформулировать сущность проблемы и комплекс характеризующих ее условий. Если же имеет место неопределенность информации, то необходимо рассмотреть две альтернативы: провести работу по получению недостающей информации; отказаться от получения дополнитель-ной информации и принимать решение в условиях имеющейся неопределенности. Выбор той или иной альтернативы в каждом конкретном случае надо производить исходя из схемы "затраты - эффект".
Важной составной частью анализа проблемной ситуации является оп-ределение степени разрешимости проблемы. В данном случае уже на предварительном этапе необходимо хотя бы приблизительно оценить возмож-ность разрешения проблемы, поскольку не имеет смысла заниматься поис-ком решений для неразрешимых в данный момент времени проблем.
Сложность и многообразие систем и проблемных ситуаций требуют разработки формальных процедур организации такого рода деятельности. В [3] предлагается следующий перечень методов, позволяющих систематизировать анализ и оценку проблемных ситуаций:
•анкетное обследование;
•прогнозирование на базе временных рядов;
•производное прогнозирование (использование уже полученных прогнозов для оценки каких-либо ситуаций, например, компания, производящая запчасти к автомобилям может воспользоваться прогнозами об объемах про-даж автомобилей);
•моделирование на базе факторного и регрессионного анализа (уста-новление причинно-следственных связей между некоторыми факторами и переменной величиной, которую необходимо определить);
•метод мозгового штурма;
•метод Дельфи;
•метод разработки сценариев.
Продолжая рассматривать пример анализа взаимодействия учебного заведения с элементами внешней среды, выделим следующий перечень проблемных ситуаций:
•на взаимосвязи X14 - низкое качество подготовки специалистов под требования современного производства;
•на взаимосвязи X11 - низкий уровень финансирования учебного процесса со стороны государства;
•на взаимосвязи X13 - низкие объемы и темпы привлечения внебюджетных средств при организации целевой и коммерческой подготовки студентов;
•на взаимосвязи X41 - низкий конкурс при поступлении в вуз по ряду специальностей и т.д.
1.1.3. Понятие цели системы
Понятие цели и связанные с ней понятия целенаправленности, целеустремленности, целесообразности трудно сформулировать виду их одно-значного толкования. Так, в БСЭ цель определяется как "заранее мыслимый результат созидательной деятельности человека". Кроме того, в литературе имеется еще ряд альтернативных вариантов определения цели системы:
•"желаемое состояние выходов системы";
•"определенное извне или установленное самой системой состояние ее выходов"; •"идеальный образ того, чего человек либо группа людей хочет достичь"; •"предвосхищение в сознании результата, на достижение которого направлены действия";
•"требуемые внешней средой результаты деятельности системы, за-данные на множестве выходных конечных продуктов".
В данном случае при определении понятия цели будем исходить из следующих предпосылок. Поскольку проблемная ситуация идентифицируется с анализом взаимоотношений системы с элементами внешней среды, то цели системы должны выражаться через идеальный информационный образ этих взаимоотношений. Таким образом, главная трудность формирования целей связана с тем, что цели являются как бы антиподом проблем. Форму-лируя проблемы, мы говорим в явном виде, что нам не нравится. Говоря о целях, мы пытаемся сформулировать, что мы хотим. При формулировке цели не следует подменять ее средствами. Предположим вы хотите "улучшить информационное обслуживание своей фирмы" - приобретение необходимого количества ПЭВМ является лишь одним из возможных действий в этом на-правлении.
Дальнейшее изложение материала будем проводить исходя из следующей классификации целей (рис. 1.4).
Рис. 1.4. Классификации целей
Конечные цели характеризуют вполне определенный результат, кото-рый может быть получен в заданном времени и пространстве. Бесконечные цели определяют, как правило, общее направление деятельности. Выбор того или иного класса целей зависит от характера решаемой проблемы. Очевидно, что при определении целей необходимо исходить из общественных интере-сов системы. При этом формулировка целей может выражаться как в качест-венной, так и в количественной форме, быть четкой и компактной, носить повелительный характер.
По отношению к состоянию целей система может находиться в двух режимах: функционирования и развития. В первом случае считается, что система полностью удовлетворяет потребности внешней среды и процесс перехода ее и ее отдельных элементов из состояния в состояние происходит при постоянстве заданных целей. Во втором случае считается, что система в некоторый момент времени перестает удовлетворять потребностям внешней среды, и требуется корректировка прежних целевых установок.
Учитывая, что практически все системы относятся к классу многопродуктовых (многоцелевых) систем, следует рассматривать простые (частные) цели системы и сложные (комплексные) цели. Так, например, для достиже-ния успеха в бизнесе можно ограничиться заданием целей в следующих областях деятельности [2]:
Этот пример показывает, что если вы при организации бизнеса задаетесь только одной целью, например, в области эффективности - "максимальное получение прибыли", ваша деятельность является паразитирующей. В конечном счете, любой бизнес должен иметь свое определенное общественное предназначение, быть полезным обществу с точки зрения производства каких-либо конечных продуктов и услуг.
1.1.4. Понятие функций системы
Наличие проблемной ситуации и объективной цели системы , как прообраза ее будущего состояния, требует реализации определенных действий по достижению заданных целевых результатов.
В этом случае, определим функцию системы как способ (совокупность действий) достижения системой поставленных целей.
Для определения множества функции с успехом могут быть использованы уже упоминавшиеся:
•метод мозгового штурма;
•метод Дельфи;
•метод разработки сценариев.
В ряде случаев для генерации множества функций рекомендуется привлекать внешних экспертов, специалистов, не обремененных прошлым системы, не знающих ее внутренних ограничений и противоречий.
Например, при реализации цели "Обеспечить качество подготовки специалистов под требования конкретного предприятия" можно сформулировать следующие функции (виды деятельности):
1.заключение договоров по целевой подготовке специалистов;
2.перевод студентов на индивидуальное обучение;
3.подготовка цикла специализированных занятий под требования предприятия; 4.развитие материальной базы учебного процесса и т.д.
1.1.5. Структура системы
Рассмотренные выше этапы создания системы под проблемную ситуацию (формирование целей и способов их достижения, т.е. функций) объективно требуют следующего логического шага - выявления таких элементов и отношений между ними (внутреннего устройства системы), которые реализуют целенаправленное функционирование системы. Элементы любого содержания, необходимые для реализации функции, назовем частями или ком-понентами системы. Совокупность частей (компонентов) системы образует ее элементный (компонентный) состав. При этом те элементы системы, которые рассматриваются как неделимые, будут называться элементарными. Часть системы, состоящая более чем из одного элемента образует подсистему. Вместе с тем каждую из подсистем, реализующих конкретную функцию, можно, в свою очередь, рассматривать как новую систему и т.д. Упорядоченное множество отношений между частями, существенное по отношению к цели, необходимое для реализации функции, образует структуру системы.
Понятие структуры происходит от латинского слова structure, означающего строение, расположение, порядок, а наиболее точное определение структуры выглядит следующим образом: "Под структурой понимается совокупность элементов системы и взаимосвязей между ними". При этом понятие "связи" может характеризовать одновременно и строение (статику), и функционирование (динамику) системы. Кроме того, при проведении анализа используются два определяющих понятия структуры: материальная структура и формальная структура.
В общем случае под формальной структурой понимается совокуп-ность функциональных элементов и их отношений, необходимых и достаточных для достижения системой поставленных целей. Из определения следует, что формальная структура описывает нечто общее, присущее системам одного типа.
В свою очередь материальная структура является носителем конкретных типов и параметров элементов системы и их взаимосвязей.
Приведенные рассуждения позволяют сделать два вывода относительно сущности формальных структур: фиксированной цели соответствует как правило одна и только одна формальная структура; одной формальной структуре может соответствовать множество материальных структур.
При проведении системного анализа на этапе изучения формальных и материальных структур системы аналитики решают обычно следующие задачи:
•соответствует ли существующая структура новым целям и функциям системы; •требуется ли реорганизация существующей структуры либо необходимо спроектировать принципиально новую структуру;
•каким образом распределить (перераспределить) новые и старые функции системы по элементам структуры.
Все эти задачи во многом зависят от типов используемых в системе структур. В этой связи кратко рассмотрим ряд типовых структур систем, использующихся при описании организационно-экономических, производст-венных и технических объектов (рис. 1.5).
Рис. 1.5. Типы (виды) структур
Линейная структура (рис.1.5,а) характеризуется тем, что каждая вершина связана с двумя соседними. При выходе из строя хотя бы одного элемента (связи) структура разрушается.
Кольцевая структура (рис.1.5,б) отличается замкнутостью, любые два элемента обладают двумя направлениями связи. Это повышает скорость общения, делает структуру более живучей.
Сотовая структура (рис.1.5,в) характеризуется наличием резервных связей, что повышает надежность (живучесть) функционирования структуры, но приводит к повышению ее стоимости.
Многосвязная структура (рис.1.5,г) имеет структуру полного графа. Надежность функционирования максимальная, эффективность функциони-рования высокая, за счет наличия кратчайших путей, стоимость - максимальная. Частным случаем многосвязной структуры является "колесо" - (рис.1.5,д).
Иерархическая структура (рис.1.5,е) получила наиболее широкое распространение при проектировании систем управления, чем выше уровень иерархии тем меньшим числом связей обладают его элементы. Все элементы кроме верхнего и нижнего уровней обладают как командными, так и подчиненными функциями управления. Каждый уровень такой системы характе-ризуется уровнем иерархии, который определяется как отношение числа исходящих связей к числу входящих.
Звездная структура (рис.1.5,ж) имеет центральный узел, который выполняет роль центра, все остальные элементы системы являются подчиненными.
Графовая структура (рис.1.5,з) является инвариантной по отношению к иерархической и используется обычно при описании производственно-технологических систем.
В целом структура является материальным носителем целевой деятельности по ликвидации проблемной ситуации и от ее эффективности во многом зависит конечный результат этой деятельности. В этом случае при выборе того либо иного варианта структур, целесообразно использовать не-которые показатели эффективности, например: оперативность, централизация, периферийность, живучесть, объем.
Оперативность оценивается временем реакции системы на воздействие внешней среды либо скоростью ее изменения и зависит в основном от общей схемы соединения элементов и их расположения.
Централизация определяет возможности выполнения одного из элементов системы руководящих функций. Численно централизация определяется средним числом связей центрального (руководящего) элемента со всеми остальными.
Периферийность характеризует пространственные свойства структур. Численно периферийность характеризуется показателем центра тяжести структуры, при этом в качестве единичной оценки меры связности выступает "относительный вес" элемента структуры.
Живучесть системы определяет способность сохранять значения показателей при повреждении части системы. Этот показатель может характеризоваться относительным числом элементов (или связей), при уничтожении которых остальные показатели не выходят за допустимые пределы.
Объем является количественной характеристикой структуры и определяется обычно общим количеством элементов либо средней плотностью.
Задача оптимизации структуры с целью получения наибольшей эффективности системы является актуальной и требует определенного математического аппарата для своего решения. В качестве такого аппарата обычно используется теория графов и целочисленное программирование.
1.1.6. Внешние условия системы
Применение указанных выше этапов формирования системы под проблемную ситуацию (определение целей, функций и структуры системы) позволяют создать идеально-нормативную систему, которая может служить эталоном реальных систем, функционирующих в условиях ограничений, накладываемых внешней средой. При несоответствии существующей структуры системы нормативному набору функций, приводящему к достижению целей и невозможности ее реорганизации за счет внутренних ресурсов системы, должны рассматриваться варианты привлечения в систему элементов внешней среды. В большинстве случаев в качестве элементов внешней среды, активно воздействующих на систему, рассматриваются:
•внешние ресурсы: финансовые, материальные, трудовые;
•ограничения: законодательные акты, нормативно-правовые документы и т.д.
Очевидно, и те и другие воздействия могут оказывать влияние как на структуру, так и на функции системы.
Иногда, после определения множества необходимых ресурсов становится очевидным нереальность заданных целевых результатов и требуется корректировка исходных целей либо множества функций по их реализации.
Однако этап постановки "оптимальных целей" не является потерей, так как стратегия "это лучшее, что можно сделать" может быть подменена стратегией "это лучшее, что может быть сделано".В случае, если внешних ресурсов достаточно, то можно говорить о ликвидации анализируемой проблемной ситуации. В противном случае речь должна пойти о переосмысление проблемы и формулировании новой системы целей.
Пример. В качестве ресурсов внешней среды при реализации функции "подготовка специалистов под требования конкретного предприятия" можно рассматривать:
•финансовые ресурсы, поступающие от предприятия в виде денежной компенсации за дополнительную подготовку;
•материальные ресурсы, представленные в виде оригинального обо-рудования, приборов и устройств, которые студент должен изучить и уметь пользоваться; •постановления министерства общего и профессионального образования Российской Федерации, регламентирующие права и обязанности вуза, предприятия и студента.
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
X1 -2X2 => 0
Использование графического способа удобно только при решении задач ЛП с двумя переменными . При большем числе переменных необходимо применение алгебраического аппарата . В данной главе рассматривается общий метод решения задач ЛП , называемый симплекс-методом .
Информация , которую можно получить с помощью симплекс-метода , не ограничивается лишь оптимальными значениями переменных . Симплекс-метод фактически позволяет дать экономическую интерепритацию полученного решения и провести анализ модели на чувствительность .
Процесс решения задачи линейного программирования носит итерационный характер : однотипные вычислительные процедуры в определенной последовательности повторяются до тех пор , пока не будет получено оптимальное решение . Процедуры , реализуемые в рамках симплекс-метода , требуют применения вычислительных машин - мощного средства решения задач линейного программирования .
Симлекс-метод - это характерный пример итерационных вычислений , используемых при решении большинства оптимизационных задач . В данной главе рассматриваются итерационные процедуры такого рода , обеспечивающие решение задач с помощью моделей исследования операций .
В гл 2 было показано , что правая и левая части ограничений линейной модели могут быть связаны знаками . Кроме того , переменные , фигурирующие в задачах ЛП , могут быть неотрицательными или не иметь ограничения в знаке . Для построения общего метода решения задач ЛП соответствующие модели должны быть представлены в некоторой форме , которую назовем стандатрной формой линейных оптимизационных моделей . При стандартной форме линейной модели
1. Все ограничения записываются в виде равенств с неотрицательной правой частью ;
2. Значения всех переменных модели неотрицательны ;
3. Целевая функция подлежит максимизации или минимизации .
Покажем , каким образом любую линейную модель можно привести к стандартной .
Ограничения
1. Исходное ограничение , записанное в виде неравенства типа ) ,
можно представить в виде равенства , прибавляя остаточную переменную к левой части ограничения ( вычитая избыточную переменную из левой части ) .
Например , в левую часть исходного ограничения
5X1 + 100X2
вводистя остаточная переменная S1 > 0 , в результате чего исходное неравенство обращается в равенство
5X1 + 100X2 + S1 = 1000 , S1 => 0
Если исходное ограничение определяет расход некоторого ресурса , переменную S1 следует интерпретировать как остаток , или неиспользованную часть , данного ресурса .
Рассмотрим исходное ограничение другого типа :
X1 - 2X2 => 0
Так как левая часть этого ограничения не может быть меньше правой , для обращения исходного неравенства в равенство вычтем из его левой части избыточную переменную S2 > 0 . В результате получим
X1 - 2X2 - S2 = 0 , S2 => 0
2. Правую часть равенства всегда можно сделать неотрицательной , умножая оби части на -1 .
Например равенство X1 - 2X2 - S2 = 0 эквивалентно равенству - X1 + 2X2 + S2 = 0
3. Знак неравенства изменяется на противоположный при умножении обеих частей на -1 .
Например можно вместо 2 < 4 записать - 2 > - 4 , неравенство X1 - 2X2 0
Переменные
Любую переменную Yi , не имеющую ограничение в знаке , можно представить как разность двух неотрицательных переменных :
Yi=Yi’-Yi’’, где Yi’,Yi’’=>0.
Такую подстановку следует использовать во всех ограничениях , которые содержат исходную переменную Yi , а также в выражении для целевой функции .
Обычно находят решение задачи ЛП , в котором фигурируют переменные Yi’ и Yi’’ , а затем с помощью обратной подстановки определяют величину Yi . Важная особенность переменных Yi’ и Yi’’ состоит в том , что при любом допустимом решении только одна из этих переменных может принимать положительное значение , т.е. если Yi’>0 , то Yi’’=0, и наоборот . Это позволяет рассматривать Yi’ как остаточную переменную , а Yi’’ - как избыточную переменную , причем лишь одна из этих переменных может принимать положительное значение . Указанная закономерность широко используется в целевом программировании и фактически является предпосылкой для использования соответсвующих преобразований в задаче 2.30
Целевая функция
Целевая функция линейной оптимизационной модели , представлена в стандартной форме , может подлежать как максимизации , так и минимизации . В некоторых случаях оказывается полезным изменить исходную целевую функцию .
Максимизация некоторой функции эквивалентна минимизации той же функции , взятой с противоположным знаком , и наоборот . Например максимизация функции
Z = X1 + 25X2
эквивалентна минимизации функции
( -Z ) = -X1 - 25X2
Эквивалентность означает , что при одной и той же совокупности ограничений оптимальные значения X1 , X2 , в обоих случаях будут одинаковы . Отличие заключается только в том , что при одинаковых числовых значениях целевых функций их знаки будут противоположны .
Симплекс-метод .
В вычислительной схеме симплекс-метода реализуется упорядоченный процесс , при котором , начиная с некоторой исходной допустимой угловой точки ( обычно начало координат ) , осуществляются последовательные переходы от одной допустимой экстремальной точки к другой до тех пор , пока не будет найдена точка , соответствующая оптимальному решению .
Общую идею симплекс-метода можно проиллюстрировать на примере модели , посроенной для нашей задачи . Пространство решений этой задачи представим на рис. 1 . Исходной точкой алгоритма является начало координат ( точка А на рис. 1 ) . Решение , соответствующее этой точке , обычно называют начальным решением . От исходной точки осуществляется переход к некоторой смежной угловой точке .
Выбор каждой последующей экстремальной точки при использовании симплекс-метода определяется следующими двумя правилами .
1. Каждая последующая угловая точка должна быть смежной с предыдущей . Этот переход осуществляется по границам ( ребрам ) пространства решений .
2. Обратный переход к предшествующей экстремальной точке не может производиться .
Таким образом , отыскание оптимального решения начинается с некоторой допустимой угловой точки , и все переходы осуществляются только к смежным точкам , причем перед новым переходом каждая из полученных точек проверяется на оптимальность .
Определим пространство решений и угловые точки агебраически . Требуемые соотнощшения устанавливаются из указанного в таблице соответствия геометрических и алгебраических определений
Геометрическое определение
Алгебраическое определение( симплекс метод )
Пространство решений
Ограничения модели стандартной формы
Угловые точки
Базисное решение задачи в стандартной форме
Представление пространства решений стандартной задачи линейного программирования .
Линейная модель , построенная для нашей задачи и приведенная к стандартной форме , имеет следующий вид :
Максимизировать
Z = X1 + 25X2 + 0S1 + 0S2
При ограничениях
5X1 + 100X2 + S1= 1000
- X1 +2X2+ S2 = 0
X1=>0 , X2=>0 , S1=>0 , S2=>0
Каждую точку пространства решений данной задачи , представленную на рис.1 , можно определить с помощью переменных X1 , X2 , S1 и S2 , фигурирующими в модели стандартной формы. При S1 = 0 и S2 = 0 ограничения модели эквивалентны равенствам , которые представляются соответствующими ребрами пространства решений . Увеличение переменных S1 и S2 будет соответствовать смещению допустимых точек с границ пространства решений в его внутреннюю область. Переменные X1 , X2 , S1 и S2 , ассоциированные с экстремальными точками А , В , и С можно упорядочить , исходя из того , какое значение ( нулевое или ненулевое ) имеет данная переменная в экстремальной точке .
Экстремальная точка
Нулевые переменные
Ненулевые переменные
А
S2 , X2
S1 , X1
В
S1 , X2
S2 , X1
С
S1 , S2
X1 , X2
Анализируя таблицу , легко заметить две закономерности:
1. Стандартная модель содержит два уравнения и четыре
неизвестных , поэтому в каждой из экстремальных точек две ( = 4 - 2 ) переменные должны иметь нулевые значения .
2. Смежные экстремальные точки отличаются только одной пе-
ременной в каждой группе ( нулевых и ненулевых переменных ) ,
Первая закономерность свидетельствует о возможности опре-
деления экстремальных точек алгебраическим способом путем при-
равнивания нулю такого количества переменных , которое равно
разности между количеством неизвестных и числом уравнений .
В этом состоит сущность свойства однозначности экстремальных
точе на рис 1 каждой неэкстремальной точке соответствует
не более одной нулевой переменной . Так , любая точка внутренней
области пространства решений вообще не имеет ни одной нулевой
переменной, а любая неэкстремальная точка , лежащая на границе ,
всегда имеет лишь одну нулевую переменную .
Свойство однозначности экстремальных точек позволяет опре-
делить их алгебраическим методом. Будем считать , что линейная
модель стандартной формы содержит т уравнений и п ( т
известных ( правые части ограничений — неотрицательные ) . Тогда
все допустимые экстремальные точки определяются как все одно-
значные неотрицательные решения системы m уравнений , в ко-
торых п — m переменных равны нулю.
Однозначные решения такой системы уравнений, получаемые
путем приравнивания к нулю ( п — т ) переменных , называются
базисными решениями . Если базисное решение удовлетворяет
требованию неотрицательности правых частей , оно называется
допустимым базисным решением. Переменные , имеющие нулевое
значение , называются небазисными переменными , остальные —
базисными переменными.
Из вышеизложенного следует , что при реализации симплекс-
метода алгебраическое определение базисных решений соответст-
вует идентификации экстремальных точек , осуществляемой при
геометрическом представлении пространства решений . Таким об-
разом , максимальное число итераций при использовании симплекс-
метода равно максимальному числу базисных решений задачи ЛП ,
представленной в стандартной форме . Это означает , что количество
итерационных процедур симплекс-метода не превышает
Cпт= n! / [ ( n - m )!m! ]
Вторая из ранее отмеченных закономерностей оказывается
весьма полезной для построения вычислительных процедур симп-
лекс-метода , при реализации которого осуществляется последова-
тельный переход от одной экстремальной точки к другой, смежной с ней . Так как смежные экстремальные точки отличаются только
одной переменной, можно определить каждую последующую ( смеж-
ную) экстремальную точку путем замены одной из текущих не-
базисных ( нулевых ) переменных текущей базисной переменной.
В нашем случае получено решение , соответствующее точке А , откуда следует осуществить переход в точку В . Для этого нужно увеличивать небазисную переменную X2 от исходного нулевого значения до значе-
ния , соответствующего точке В ( см. рис. 1 ). В точке B переменная
S1 ( которая в точке А была базисной ) автоматически обращается в
нуль и , следовательно , становится небазисной переменной . Таким
образом , между множеством небазисных и множеством базисных
переменных происходит взаимообмен переменными X2 и S1 . Этот
процесс можно наглядно представить в виде следующей таблицы.
Экстремальная точка
Нулевые переменные
Ненулевые переменные
А
S2 , X2
S1 , X1
В
S1 , X2
S2 , X1
Применяя аналогичную процедуру ко всем экстремальным точкам
рис. 1 , можно убедиться в том , что любую последующую экстре-
мальную точку всегда можно определить путем взаимной замены
по одной переменной в составе базисных и небазисных переменных
( предыдущей смежной точки ) . Этот фактор существенно упрощает
реализацию вычислительных процедур симплекс-метода.
Рассмотренный процесс взаимной замены переменных приводит
к необходимости введения двух новых терминов . Включаемой пе-
ременной называется небазисная в данный момент переменная ,
которая будет включена в множество базисных переменных на сле-
дующей итерации ( при переходе к смежной экстремальной точке ) .
Исключаемая переменная — это та базисная переменная , которая
на следующей итерации подлежит исключению из множества ба-
зисных переменных .
Вычислительные процедуры симплекс-метода .
Симплекс-алгоритм состоит из следующих шагов.
Шаг 0. Используя линейную модель стандартной формы , опреде-
ляют начальное допустимое базисное решение путем приравнива-
ния к нулю п — т ( небазисных ) переменных.
Шаг 1. Из числа текущих небазисных ( равных нулю ) перемен-
ных выбирается включаемая в новый базис переменная , увеличение
которой обеспечивает улучшение значения целевой функции. Если
такой переменной нет , вычисления прекращаются , так как текущее
базисное решение оптимально . В противном случае осуществляется
переход к шагу 2.
Шаг 2. Из числа переменных текущего базиса выбирается исклю-
чаемая переменная , которая должна принять нулевое значение ( стать
небазисной ) при введении в состав базисных новой переменной .
Шаг 3. Находится новое базисное решение , соответствующее
новым составам небазисных и базисных переменных . Осуществляется переход к шагу 1.
Поясним процедуры симплекс-метода на примере решения нашей зада-
чи . Сначала необходимо представить целевую функцию и ограничения модели в стандартной форме:
Z - X1 - 25X2 +0S1 -0S2 = 0 ( Целевая функция )
5X1 + 100X2 + S1 = 1000 ( Ограничение )
-X1 +2X2 + S2 = 0 ( Ограничение )
Как отмечалось ранее , в качестве начального пробного решения
используется решение системы уравнений , в которой две переменные принимаются равными нулю . Это обеспечивает единст-
венность и допустимость получаемого решения . В рассматриваемом
случае очевидно, что подстановка X1 = X2 = 0 сразу же приводит к следующему результату: S1 = 1000 , S2 = 0 ( т. е. решению , соответствующему точке А на рис. 1 ) . Поэтому точку А можно использовать как начальное допустимое решение . Величина Z в этой точке равна нулю , так как и X1 и X2 имеют нулевое значение . Поэтому , преобразовав уравнение целевой функции так , чтобы его правая часть стала равной нулю , можно убедиться в том , что правые части уравнений целевой функции и ограничений полностью характеризуют начальное решение . Это имеет место во всех случаях , когда начальный базис состоит из остаточных переменных.
Полученные результаты удобно представить в виде таблицы :
Эта таблица интерпретируется следующим образом. Столбец
« Базисные переменные » содержит переменные пробного базиса 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 00 )
( - ( -25 ) * ( 0 -1/210 1/2 0 )
( 1 -131/2 00 121/2 0 )
2. Новое S1 - уравнение
старое S1 - уравнение : ( 0 5 100 10 1000 )
( - 100 ) * ( 0 -1/2 1 0 1/20 )
( 0 55 01 -50 1000 )
Новая симплекс-таблица будет иметь вид :
Базисные переменные Z X1 X2 S1 S2 Решение
Z 1 -131/2 0 0 121/2 0 Z – уравнение
S1 0 55 0 1 -50 1000 S1 –уравнение
X2 0 -1/2 1 0 1/2 0 X2 – уравнение
В новом решении X1 = 0 и S2 = 0 . Значение Z не изменяется .
Заметим , что новая симплекс-таблица обладает такими же ха-
рактеристиками , как и предыдущая : только небазисные переменные
X1 и S2 равны нулю , а значения базисных переменных , как и раньше ,
представлены в столбце « Решение » . Это в точности соответствует
результатам , получаемым при использовании метода Гаусса—Жор-
дана .
Из последней таблицы следует , что на очередной итерации в со-
ответствии с условием оптимальности в качестве вводимой перемен-
ной следует выбрать X1 , так как коэффициент при этой переменной в
Z-ypaвнении равен -131/2 . Исходя из условия допустимости , определяем , что исключаемой переменной будет S1 . Отношения , фигурирующие в правой части таблицы , показывают , что в новом базисном решении значение включаемой переменной X1 будет равно 1000/55 ( = минимальному отношению ) . Это приводит к увеличению целевой функции на ( 1000/55 ) * ( -131/2 ) = ( 2455/11 ) .
К получению симплекс-таблицы , соответствующей новой итерации , приводят следующие вычислительные операции метода Гаусса—Жордана.
1) Новое ведущее S1 - уравнение = Предыдущее S1 - уравнение / ( 55 ) .
Базисные переменные Z X1 X2 S1 S2 Решение
Z
S1 0 1 0 1/55 - 50/55 1000/55
X2
В результате указанных преобразований получим следующую симп-
лекс-таблицу .
Базисные переменные 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 ) , однако , чтобы получить результат в общем виде , рассмотрим оба случая .
Как изменится симплекс-таблица при изменении величины за-
паса ресурса на????? Проще всего получить ответ на этот вопрос .
если ввести ???в правую часть первого ограничения начальной сим-
плекс-таблицы и затем выполнить все алгебраические преобразова-
ния , соответствующие последовательности итераций . Поскольку
правые части ограничений никогда не используются в качестве
ведущих элементов , то очевидно , что на каждой итерации ???будет
оказывать влияние только на правые части ограничений .
Уравнение
Значения элементов правой части на соответствующих итерациях
Фактически в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/55 )???=> - 1000/55 . Из этого следует , что ???=> - 1000
( 2 )
( 1/110 )???=> - 91/11 . Из этого следует , что ???=> - 1000
Объединяя результаты , полученные для обоих случаев , можно
сделать вывод , что при - 1000 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-уравнения до введения??? , только наличием членов , содержащих ???. Коэффициенты при ?? равны Коэффициентам при соответствующих переменных в Z-уравнении симплекс-таблицы для полученного ранее оптимального решения
Мы рассматриваем X1 - уравнение , так как коэффициент именно при
этон переменной в выражении для целевои функции изменился
на??? .
Оптимальные значения переменных будут оставаться неизмен-
ными при значениях ???, удовлетворяющих условию неотрицатель-
ности ( задача на отыскание максимума ) всех коэффициентов при не-
базисных переменных в Z-уравнении . Таким образом , должны выполняться следующие неравенства :
27/110 + 1/55???????
5/22 - 50/55???????
Из первого неравенства получаем , что ?? => - 13,5 , а из второго следует что ??