Кафедра «Финансы и менеджмент»

Н.Е. Гучек

доцент, кандидат технических наук

КОНСПЕКТ ЛЕКЦИЙ

по дисциплине

методы оптимальных решений

Направление подготовки: 080100 «Экономика»

Профили подготовки: «Финансы и кредит», «Бухгалтерский учет, анализ и

аудит», «Налоги и налогообложение», «Мировая экономика»
Форма обучения: очная

Тула 2012 г.

Конспект лекций подготовлен доцентом Н.Е. Гучек и обсужден на заседании кафедры «Финансы и менеджмент» факультета ЭиМ,

Конспект лекций пересмотрен и утвержден на заседании кафедры «Финансы и менеджмент» факультета экономики и менеджмента

Зав. кафедрой __________________________Е.А. Федорова

1.1. Основные понятия теории принятия решений 4

1.2. Математическая формализация 7

1.3. Современный этап развития теории принятия решений 12

Лекция 2. Математическое моделирование 15

2.1. Этапы построения математической модели 15

2.2. Понятия устойчивости, оптимизации и адекватности модели 18

2.3. Постановка и технология решения оптимизационных задач управления 21

Лекция 3. Линейное программирование 25

3.1. Линейное программирование как инструмент математического моделирования экономики 25

3.2. Примеры моделей линейного программирования 29

Лекция 4. Задачи линейное программирование 33

4.1. Формы задач линейного программирования и их эквивалентные преобразования 33

4.2. Геометрическая интерпретация задачи линейного программирования 37

Лекция 5. Симплексный метод решения задачи линейного программирования 41

5.1. Симплекс-метод 41

5.2. Симплексные таблицы и алгоритм решения задач 42

5.3. Применение симплексного метода в экономических задачах 44

Лекция 6. Метод искусственного базиса решения задачи линейного программирования 48

6.1. Метод искусственного базиса 48

6.2. Применение метода искусственного базиса 49

Лекция 7. Двойственные задачи линейного программирования 52

7.1. Двойственная задача для стандартной задачи 52

7.2. Основные теоремы двойственности 57

7.3. Метод одновременного решения пары двойственных задач 62

Лекция 1. Введение в теорию принятия решений

План.

1.1. Основные понятия теории принятия решений.

1.2. Математическая формализация.

1.3. Современный этап развития теории принятия решений.

1.1. Основные понятия теории принятия решений

Математические модели и методы – необходимый элемент экономической теории на микро- и макроуровне. Использование математики в экономике позволяет:

во-первых, выделить и формально описать наиболее важные, существенные связи экономических переменных и объектов ;

во-вторых, из четко сформулированных исходных данных и соотношений методами дедукции можно получать выводы, адекватные изучаемому объекту в той же мере, что и сделанные предпосылки;

в-третьих, методы математики и статистики позволяют индуктивным путем получать новые знания об объекте: оценивать форму и параметры зависимостей его переменных, в наибольшей степени соответствующие имеющимся наблюдениям;

в-четвертых, использование языка математики позволяет точно и компактно излагать положения экономической теории, формулировать ее понятия и выводы.

Математическое моделирование экономических явлений и процессов с целью обеспечения принятия решений – область научно-практической деятельности , получившая мощный стимул к развитию во время и сразу после Второй мировой войны. Это направление развивалось вместе с развитием кибернетики, исследования операций, системного анализа и информатики.

При построении, изучении и применении экономико-математических моделей принятия решений используются различные экономико-математические методы. Их можно разделить на несколько групп:

Методы оптимизации;

Вероятностно-статистические методы;

Методы построения и анализа имитационных моделей;

Методы анализа конфликтных ситуаций (теории игр).

Во всех этих группах можно выделить статическую и динамическую постановки. При наличии фактора времени используют дифференциальные уравнения и разностные схемы.

Методы оптимальных решений опираются на теорию оптимальных решений. Рассмотрим основные понятия теории принятия решений 1 .

Кто принимает решения? В теории принятия решений есть специальный термин – лицо, принимающее решение, сокращенно ЛПР. Это тот, на ком лежит ответственность за принятое решение, тот, кто подписывает приказ или иной документ, в котором выражено решение. Обычно это генеральный директор или председатель правления , командир воинской части, мэр города и т.п. Но иногда действует коллективный ЛПР, например, совет директоров, Государственная Дума Российской Федерации.

Проект решения готовят специалисты или, как говорят, «аппарат ЛПР». Однако ответственность лежит на ЛПР, а не на тех, кто участвовал в подготовке решения.

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

Порядок подготовки решения (регламент). Регламенты, определяющие порядок работы, очень важны. От них зависит принятое решение.

Цели. Каждое решение направлено на достижение одной или нескольких целей. Возможны случаи, когда несколько целей можно достичь одновременно. Но чаще бывает по-другому.

Например, часто встречающаяся формулировка «максимум прибыли при минимуме затрат» внутренне противоречива. Минимум затрат равен 0, когда работа не проводится, то и прибыль тогда тоже равна 0. если же прибыль велика, то и затраты велики, поскольку и то, и другое связано с объемом производства. Можно либо максимизировать прибыль при фиксированных затратах, либо минимизировать затраты при заданной прибыли , но невозможно добиться «максимума прибыли при минимуме затрат».

Часто одной и той же цели можно добиться различными способами.

Ресурсы. Каждое решение предполагает использование тех или иных ресурсов. В практической работе над проектом решения важно отвечать на вопросы: «Чего мы хотим достичь? Какие ресурсы мы готовы использовать для этого?»

Риски и неопределенности. Многие решения принимаются в условиях риска, т.е. при возможной опасности потерь. Связано это с разнообразными неопределенностями, окружающими нас. Неопределенность – это недостаточность информации о тех или иных факторах. Кроме отрицательных неожиданностей, бывают положительные – удачи. При принятии решений следует застраховаться от потерь и не пропустить удачу.

Формулировка «Максимум прибыли и минимум риска» - внутренне противоречива. Обычно при возрастании прибыли возрастает и риск – возможность многое или все потерять. Неопределенность значений показателей, на основе которых принимаются решения, описывается интервальными значениями этих показателей, например (60  3) % или 1000  200 руб. Поэтому необходимо изучить устойчивость выводов по отношению к допустимым отклонениям исходных данных , а также по отношению к малым изменениям предпосылок используемой математической модели. Любое измерение проводится с некоторой погрешностью, и эту погрешность необходимо указывать.

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

Критерии могут противоречить друг другу. Поэтому ЛПР приходится решать, какой из критериев для него важнее. В этом ему может помочь теория полезности, хорошо разработанная в экономике (в частности, так называемая маржинальная полезность в теории поведения потребителей и др.) и имеющая развитый математический аппарат.

МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ

Кафедра статистики

и информационных систем

в экономике

Б2.Б4 методы оптимальных решений

Методические указания по дисциплине

Направление подготовки 080100 Экономика

Профили подготовки

Финансы и кредит

Налоги и налогообложение

Бухгалтерский учет, анализ и аудит

Экономика предприятий и организаций

Квалификация (степень) выпускника

Бакалавр

Составитель: ст.преподаватель Сагадеева Э. Ф.

Рецензент: к.с.н., доцент кафедры математики Гильманова Г. Х.

Ответственный за выпуск: зав. кафедрой статистики и информационных систем в экономике, к.э.н., доцент Аблеева А.М.

Введение
1. Геометрическая интерпретация задач линейного программирования
2. Симплексный метод решения задачи линейного программирования
3. Основные понятия теории двойственности
4.Двойственный симплекс-метод
5. Симплексный метод с искусственным базисом
6. Целочисленное программирование. Метод Гомори
7. Дробно-линейное программирование
8. Задачи нелинейного программирования. Метод множителей Лагранжа
9. Задания для самостоятельной работы
10. Тестовые задания
11. Задания для выполнения расчетно-графической работы и контрольной работы заочников
12. Фонд контрольных вопросов
13. Билеты к экзамену
14. Библиографический список

Введение

Методы оптимальных решений – это раздел математики, который изучает теорию и методы поиска лучших вариантов планирования хозяйственной деятельности человека как на одном определенном предприятии, так и в некоторой отрасли или в отдельном регионе, или в целом государстве.

Лучшие варианты – это те, при которых достигается максимальная производительность труда, минимум себестоимости, максимальная прибыль, минимум использования ресурсов и т.д. С точки зрения математики – это класс оптимизационных задач. Основным инструментом при их решении является математическое моделирование. Математическая модель – это формальное описание изучаемого явления и «перевод» всех существующих сведений о нем на язык математики в виде уравнений, тождеств, неравенств. Если все эти соотношения линейные, то вся задача называется задачей линейного программирования (ЗЛП). Критерием эффективности этой модели является некоторая функция, которую называют целевой.

Сформулируем общую задачу линейного программирования.

Пусть дана система m линейных уравнений и неравенств с n переменными (система ограничений):

(1)

и линейная функция

Необходимо найти такое решение системы (1), при котором линейная функцияпринимает максимальное (минимальное) значение.

В общем случае ЗЛП может иметь бесконечное множество решений. Часто решение , удовлетворяющее ограничениям (1), называютпланом . Если все компоненты (3) для, тоназываютдопустимым решением .

Оптимальным решением или оптимальным планом задачи линейного программирования называется такое ее решение , которое удовлетворяет всем ограничениям системы (1), условию (3) и при этом дает максимум (минимум) целевой функции (2).

Каноническая	Стандартная	Общая
1) Ограничения
Уравнения	Неравенства	Уравнения и неравенства
2) Условия неотрицательности
Все переменные	Все переменные	Часть переменных
3) Целевая функция
(max или min )

Здесь: – переменные задачи;– коэффициенты при переменных в целевой функции;– коэффициенты при переменных в основных ограничениях задачи; – правые части ограничений.

Линейное программирование - это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на неизвестные которой наложены линейные ограничения. Таким образом, задачи линейного программирования относятся к задачам на условный экстремум функции. Казалось бы, что для исследования линейной функции многих переменных на условный экстремум достаточно применить хорошо разработанные методы математического анализа, однако невозможность их использования можно довольно просто проиллюстрировать.

Действительно, путь необходимо исследовать на экстремум линейную функцию

Z = С 1 х 1 +С 2 х 2 +... +С N x N

при линейных ограничениях

a 11 x 1 + a 22 x 2 + ... + a 1N Х N = b 1

a 21 x 1 + a 22 x 2 + ... + a 2N Х N = b 2

. . . . . . . . . . . . . . .

a М 1 x 1 + a М 2 x 2 + ... + a М N Х N = b М

Так как Z - линейная функция, то Z = С j , (j = 1, 2, ..., n), то все коэффициенты линейной функции не могут быть равны нулю, следовательно, внутри области, образованной системой ограничений, экстремальные точки не существуют. Они могут быть на границе области, но исследовать точки границы невозможно, поскольку частные производные являются константами.

Для решения задач линейного программирования потребовалось создание специальных методов. Особенно широкое распространение линейное программирование получило в экономике, так как исследование зависимостей между величинами, встречающимися во многих экономических задачах, приводит к линейной функции с линейными ограничениями, наложенными на неизвестные.

МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ

Краткий курс лекций

Саратов 2012

МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА

РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО

ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ

УНИВЕРСИТЕТ имени Н. И.ВАВИЛОВА»

_____________________________________________________

МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ

Краткий курс лекций

Саратов 2012

УДК 517(075.8)

ББК 22.161.

Издание осуществлено при поддержке

программы TEMPUS JP, грант Европейской

Комиссии 159188-TEMPUSPL-TEMPUS-JPCR

Терехова оптимальных решений. (краткий курс лекций): Учебное пособие /сост.: , – Саратов: Изд – во ФГБОУ ВПО «Саратовский ГАУ»., 201с.

Краткий курс лекций подготовлен в соответствии с положениями и требованиями Государственного образовательного стандарта высшего профессионального образования , включает основные теоретические вопросы, литературу по изучению курса.

Предназначено для студентов направления подготовки 110100.62 Агрохимия и агропочвоведение (профиль Агроэкология), 280100.68 «Природообустройство и водопользование», для бакалавров направления “Экономика предприятий и организаций” профиль“ Экономика предприятий и организаций (агропромышленного комплекс а)”, “Бухгалтерский учёт и аудит”, “Пищевая промышленность”, “Финансы и кредит”, а также для магистров, аспирантов, преподавателей, научных сотрудников.

© ФГБОУ ВПО СГАУ имени

ISBN , 2012

ВВЕДЕНИЕ

В курсе рассматриваются вопросы, связанные с построением математических моделей ситуаций целенаправленного принятия решения, исследуются свойства этих моделей, излагаются методы и алгоритмы, позволяющие находить оптимальные значения отвечающих за рациональный выбор параметров. Значительное внимание уделяется ситуациям, в которых при формировании оптимального решения необходимо учитывать интересы различных сторон.

Краткий курс лекций имеет прикладную направленность: теоретический материал иллюстрируется достаточно доступными примерами и задачами, имеющими, как правило, экономический и социальный характер. Материал данного курса найдёт свое конкретное применение в общепрофессиональных и специальных дисциплинах факультета экономики , посвященных микро - и макроэкономике, государственному управлению и экономике общественного сектора, фондовому рынку и финансовому менеджменту , институциональной экономике и ряду других научных областей. Поэтому данный курс лекций является важной составляющей системы фундаментальной подготовки современного экономиста, а также обеспечивает ему профессиональную мобильность.

ЛЕКЦИЯ 1

Исследование операций. Экономико-математические модели.

Управление организационными системами (оргсистемами) – сложная проблема. Характерной особенностью таких систем является включение в них, наряду с материальными, денежными, энергетическими и информационными ресурсами, также и коллективов людей, взаимодействующих как между собой, так и с указанными ресурсами. Примерами оргсистем служат фирмы, ведомства , министерства, вузы и их филиалы, города и др.

Оргсистемы являются объектом изучения теории исследования операций.

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

Исследование операций – научная дисциплина, занимающаяся разработкой и практическим применением методов управления различными оргсистемами.

Ее цель – количественное обоснование принимаемых управленческих решений и прогнозных планов развития .

Исследование операций осуществляется на математических моделях изучаемых объектов.

Термин «модель» используется в различных сферах человеческой деятельности и имеет множество смысловых значений. В нашем курсе лекций определим модель как материальный или мысленно представляемый объект, который в процессе исследования замещает объект-оригинал так, что его непосредственное изучение дает новые знания об объекте-оригинале.

Следовательно, модель является инструментом научного познания. Она строится субъектом исследования так, чтобы отобразить характеристики объекта-оригинала (свойства, взаимосвязи, структурные и функциональные параметры и т. п.), существенные для цели исследования. Поэтому вопрос об адекватности модели объекту-оригиналу правомерно решать лишь относительно определенной цели.

Процесс построения, изучения и применения моделей называется моделированием . Его сущность схематически представлена на рис. 1.

https://pandia.ru/text/78/095/images/image004_15.gif" width="529" height="371">

Моделирование в экономике – это воспроизведение экономических объектов и процессов в ограниченных, малых, экспериментальных формах, в искусственно созданных условиях.

В экономике в основном используется математическое моделирование посредством описания экономических процессов математическими зависимостями. При изучении экономических процессов математические модели рассматриваются в тесной связи с целевыми системами и представляют собой некоторые целостные структуры, называемые экономико-математическими моделями (ЭММ). Таким образом, ЭММ – модели, включающие в себя совокупность математических зависимостей, логических построений, схем, графиков и т. д., связанных в некоторую единую систему, имеющую экономический смысл.

Приведем следующую общую классификацию ЭММ .

По целевому назначению ЭММ делятся на теоретико-аналитические и прикладные. Теоретико-аналитические ЭММ предназначены для исследования общих свойств и закономерностей экономических процессов. Прикладные ЭММ используются при решении конкретных экономических задач .

По характеру отражения причинно-следственных связей выделяют жестко детерминистские ЭММ и ЭММ, учитывающие случайность и неопределенность.

По способам отражения фактора времени ЭММ делятся на статические и динамические. В статических ЭММ все зависимости относятся к одному моменту или периоду времени. Динамические ЭММ характеризуют изменения экономических процессов во времени.

По исследуемым экономическим процессам различают макроэкономические и микроэкономические ЭММ. Макроэкономические модели строятся на уровне национального хозяйства , а микроэкономические – на уровне организаций, их объединений и отдельных регионов.

Существуют и другие признаки классификации ЭММ. Причем с развитием экономико -математических исследований классификация исследуемых ЭММ расширяется.

Отметим также, что по характеру используемого математического аппарата при построении ЭММ различают методы классической и прикладной математики.

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

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

Одним из признаков качества функционирования оргсистемы является критерий оптимальности ее функционирования. В сфере принятия экономических решений критерий оптимальности – это показатель, выражающий предельную меру экономического эффекта принимаемого управленческого решения для сравнительной оценки возможных решений и выбора наилучшего из них.

Критерий оптимальности, как правило, носит количественный характер. Например, в его роли могут выступить максимум прибыли или минимум затрат.

Математической формой критерия оптимальности в ЭММ является так называемая целевая функция, экстремальное значение которой характеризует предельно допустимую эффективность деятельности моделируемого объекта-оригинала.

На практике нередко успех операции оценивается не по одному, а сразу по нескольким критериям. В этом случае для выбора оптимального решения используют два подхода.

Первый подход заключается в том, что в целевой функции устанавливают приоритет критериев введением специальных коэффициентов (весов).

Второй подход состоит в отбрасывании из множества допустимых решений заведомо неудачных решений, уступающих другим по всем критериям. В результате такой процедуры остаются эффективные или так называемые «паретовские» решения, множество которых существенно меньше исходного.

Компромиссное решение – решение, оптимальное по всем критериям, как правило, не существует. И потому окончательный выбор приемлемого по этим критериям решения остается за лицом, принимающим решение.

ЛЕКЦИЯ 2

Балансовые модели. Модель Леонтьева многоотраслевой экономики.

Продуктивные модели.

В экономике существует баланс между отдельными отраслями. Рассмотрим простой вариант модели межотраслевого баланса – модель «затраты-выпуск».

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

xi ‑ общий объем продукции отрасли i за плановый год ‑ так называемый валовой выпуск отрасли i ;

xij ‑ объем продукции отрасли i, расходуемый отраслью j в процессе производства;

yi ‑ объем продукции отрасли i, предназначенный к потреблению в непроизводственной сфере ‑ объем конечного потребления. В него входят создаваемые в хозяйстве запасы, личное потребление граждан, обеспечение общественных потребностей (просвещение, наука, здравоохранение, развитие инфраструктуры и т. д.), поставки на экспорт.

Указанные величины сведем в таблицу.

Производственное потребление	Конечное Потребление

Балансовый характер этой таблицы выражается в том, что при любом выполняется соотношение

означающее, что валовой выпуск xi расходуется на производственное потребление, равное https://pandia.ru/text/78/095/images/image011_6.gif" width="64" height="57">остаются постоянными в течение ряда лет, что объясняется примерным постоянством используемой технологии производства.

Сделаем следующее допущение: для выпуска любого объема xj продукции отрасли j необходимо затратить продукцию отрасли i в количестве , т. е. материальные издержки пропорциональны объему производимой продукции:

https://pandia.ru/text/78/095/images/image014_8.gif" width="23" height="28 src="> называют коэффициентами прямых материальных затрат или коэффициентами материалоемкости . Они показывают сколько необходимо единиц продукции отрасли i для производства единицы продукции отрасли j , если учитывать только прямые затраты .

https://pandia.ru/text/78/095/images/image016_7.gif" width="85" height="24 src=">, (3)

https://pandia.ru/text/78/095/images/image018_6.gif" width="15" height="17"> называется вектором валового выпуска , вектор ‑ вектором конечного потребления , а матрица А ‑ матрицей прямых затрат. Соотношение (3) называется уравнением линейного межотраслевого баланса. Вместе с изложенной интерпретацией матрицы А и векторов https://pandia.ru/text/78/095/images/image019_9.gif" width="16" height="23 src="> это соотношение называют также моделью Леонтьева.

Уравнения межотраслевого баланса можно использовать для плановых расчетов:

Задавая для каждой отрасли i валовой выпуск продукции можно определить объемы конечного потребления каждой отрасли https://pandia.ru/text/78/095/images/image023_7.gif" width="101" height="25 src=">,

где Е – единичная матрица;

Задавая величины конечного потребления каждой отрасли https://pandia.ru/text/78/095/images/image021_7.gif" width="19" height="25">:

,

где – матрица, обратная к матрице https://pandia.ru/text/78/095/images/image020_9.gif" width="15" height="19"> и неотрицательны (это вытекает из экономического смысла А , https://pandia.ru/text/78/095/images/image019_9.gif" width="16" height="23 src=">). Для краткости будем записывать это так: .

Таким образом, плановые расчеты по модели Леонтьева можно выполнять при соблюдении следующего условия продуктивности:

матрица называется продуктивной , если для любого вектора существует решение уравнения (3).

В этом случае и модель Леонтьева, определяемая матрицей А , тоже называется продуктивной.

Сформулируем критерии продуктивности матрицы https://pandia.ru/text/78/095/images/image028_5.gif" width="45" height="20 src="> продуктивна тогда и только тогда, когда матрица существует и неотрицательна.

Критерий II . Матрица https://pandia.ru/text/78/095/images/image025_6.gif" width="72" height="28 src="> в матричный ряд

В соотношении (4) матрицы называются матрицами коэффициентов косвенных затрат 2-го, 3-го и т. д. порядков. Их сумма образует матрицу коэффициентов косвенных затрат

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

Таким образом, из соотношений (4) и (5) имеем

т. е. матрица коэффициентов полных материальных затрат включает в себя матрицы коэффициентов прямых и косвенных затрат.

Рассмотрим примеры.

Пример 1. Исследовать на продуктивность матрицу

https://pandia.ru/text/78/095/images/image037_4.gif" width="48 height=19" height="19">:

https://pandia.ru/text/78/095/images/image039_4.gif" width="577" height="143 src=">

алгебраические дополнения для элементов матрицы

https://pandia.ru/text/78/095/images/image041_4.gif" width="189 height=55" height="55">;

https://pandia.ru/text/78/095/images/image043_3.gif" width="220 height=55" height="55">;

https://pandia.ru/text/78/095/images/image045_3.gif" width="221 height=55" height="55">;

https://pandia.ru/text/78/095/images/image047_5.gif" width="209" height="55 src=">;

https://pandia.ru/text/78/095/images/image049_3.gif" width="468" height="84 src=">

Полученная матрица неотрицательна и по Критерию I исходная матрица А продуктивная.

Пример 2. Для матрицы А коэффициентов прямых затрат из примера 1 и вектора конечного потребления

https://pandia.ru/text/78/095/images/image051_3.gif" width="80" height="84 src=">

а) Вектор валового выпуска вычислим по формуле

https://pandia.ru/text/78/095/images/image053_3.gif" width="483" height="84 src=">

б) Матрицу косвенных затрат В найдем из соотношения (2.6):

https://pandia.ru/text/78/095/images/image055_3.gif" width="409" height="84 src=">

Таким образом, при увеличении вектора конечного потребления на https://pandia.ru/text/78/095/images/image056_3.gif" width="88" height="84">.

ЛЕКЦИЯ 3,4,5

Задачи математического и линейного программирования.

Модели линейного программирования.

Нередко экономические задачи имеют не единственное решение и требуется выбрать лучшее – оптимальное из них. Моделирование таких задач сводится к задачам математического программирования (ЗМП).

Математическое программирование – область математики, изучающая оптимизационные процессы посредством поиска экстремума функции при заданных ограничениях.

Сформулируем в общем виде ЗМП:

https://pandia.ru/text/78/095/images/image058_3.gif" width="296" height="79"> (8)

https://pandia.ru/text/78/095/images/image060_3.gif" width="123" height="25"> – целевая функция , условия (8) – специальные ограничения , условия (9) – общие ограничения ЗМП.

Точку , координаты которой удовлетворяют ограничениям (8) и (9), называют допустимым решением ЗМП.

Множество всех допустимых решений ЗМП называют допустимым множеством .

Допустимое решение , удовлетворяющее соотношению (7), называют оптимальным решением ЗМП.

Если в ЗМП целевая функция и функции , – линейные, то имеем общую задачу линейного программирования (ЗЛП):

https://pandia.ru/text/78/095/images/image065_3.gif" width="356" height="79 src="> (11)

https://pandia.ru/text/78/095/images/image066_3.gif" width="336" height="25 src=">;

- стандартная ЗЛП, включающая в качестве ограничений (11) только неравенства, т. е.

https://pandia.ru/text/78/095/images/image068_3.gif" width="20" height="25">, и , из которого можно наладить производство двух видов товаров: https://pandia.ru/text/78/095/images/image072_2.gif" width="20" height="25 src=">. Запасы сырья, норма его расхода на производство единицы товаров, а также прибыль от реализации единицы каждого товара приведены в таблице 1 (цифры условные).

Таблица 1

В настоящие дни в образовательную программу специальностей, связанных с экономикой, финансами и менеджментом, входит дисциплина с названием «Методы оптимальных решений». В рамках данной дисциплины студенты изучают математическую сторону оптимизации, исследования операций, принятия решений и моделирования. Главная особенность данной дисциплины определяется совместным изучением математических методов с их приложением к решению экономических задач.

Задачи на оптимизацию: общие сведения

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

В зависимости от свойств функций задачи на оптимизацию можно разделить на два вида:

• задача линейного программирования (все функции линейны);
• задача нелинейного программирования (хотя бы одна из функций не является линейной).

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

Наиболее изученными задачами на оптимизацию являются задачи линейного программирования (ЗЛП), решения которых принимают только целочисленные значения.

ЗЛП: формулировка, классификация

Задача линейного программирования в общем случае состоит в нахождении минимума (максимума) линейной функции при некоторых линейных ограничениях.

Общей ЗЛП называют задачу вида

при ограничениях

где — переменные, — заданные действительные числа, — целевая функция, — план задачи, (*)-(***) — ограничения.

Важной особенностью ЗЛП является то, что экстремум целевой функции достигается на границе области допустимых решений.

Практическое экономическое приложение методы оптимальных решений находят при решении задач следующих видов:

• задачи о смесях (т.е. планирование состава продукции);
• задачи оптимального распределения ресурсов в производственном планировании;

ЗЛП: примеры

Задача о смесях

Решение задачи о смесях состоит в отыскании наиболее дешевого набора, состоящего из определенных исходных материалов, которые обеспечивают получение смеси с заданными свойствами.

Задача о распределении ресурсов

Предприятие осуществляет выпуск n различных изделий, для производства которых требуется m различных видов ресурсов. Запасы используемых ресурсов ограничены и составляют соответственно b 1 , b 2 ,…, b m у.е. Кроме того, известны технологические коэффициенты a ij , которые показывают какое количество единиц i -го ресурса необходимо для производства одной единицы изделия j -го вида (). Прибыль, которую получает предприятие при реализации изделия j -го вида, составляет c j ден.ед. Необходимо составить план выпуска продукции, прибыль предприятия при реализации которого будет наибольшей.

Условия задач о смесях и распределении ресурсов часто записываются в виде таблиц.

Ресурсы	Потребности			Запасы
	B 1	…	B n
A 1				b 1
…				…
A m				b m
Прибыль	c 1	…	c n

Задачи о смесях и распределении ресурсов можно решить несколькими способами:

• графический метод (в случае малого числа переменных в математической модели);
• симплекс-метод (в случае числа переменных в математической модели больше двух).

К транспортной задаче относится класс задач, которые имеют определенную специфическую структуру. Простейшей транспортной задачей является задача о перевозках продукта в пункты назначения из пунктов отправления при минимальных затратах на перевозку всех продуктов.

Для наглядности и удобства восприятия условие транспортной задачи принято записывать в таблицу следующего вида:

В общем случае решение транспортной задачи выполняется в несколько этапов:

• I этап: построение первоначального опорного плана;
• II этап: проверка опорного плана на оптимальность;
• III этап: уточнение опорного плана, если он не является оптимальным.

Существует несколько методов получения первоначального опорного плана, например, метод северо-западного угла, метод Фогеля, метод минимальных стоимостей.

Проверка плана на оптимальность выполняется с применением метода потенциалов:

— для занятых клеток,
— для незанятых клеток.

Если план не является оптимальным, то выполняется построение цикла и перераспределение перевозок.

Заключение

В рамках одной статьи нет возможности охватить всю теорию и практику методов оптимальных решений, поэтому рассмотрены только некоторые моменты, позволяющие дать общее представление о данной дисциплине, задачах и методах их решения.

Кроме того, неплохо отметить, что для проверки полученных решений задач оптимизации можно очень эффективно применять надстройку «Поиск решения» пакета MS Excel. Но это уже другая история, собственно, как и подробное рассмотрение методов решения задач на оптимизацию.

Приведем несколько учебников для изучения методов оптимального решения:

1. Банди Б. Основы линейного программирования: Пер. с англ. – М.: Радио и связь, 1989. – 176 с.
2. Кремер Н.Ш. Исследование операций в экономике: Учеб. пособие для вузов /Н.Ш. Кремер, БА. Путко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера. – М.: ЮНИТИ, 2005. – 407 с.

Решение методов оптимизации на заказ

Мы можем помочь вам с решением любых задач по методам оптимальных решений. Заказать решение задач можно у нас на сайте. Достаточно лишь указать срок и прикрепить файл с заданием. вашего заказа можно бесплатно.

МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ

Учебное пособие

УДК 51-77.330.4

МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ

Составим экономико-математическую модель задачи. Обозначим через xj – количество исходного материала (листов стали), которые необходимо раскроить по одному из способов j. Ограничения в задаче должны соответствовать плановому выходу заготовок различных видов. Целевая функция сводиться к нахождению минимума отходов при раскрое

https://pandia.ru/text/78/539/images/image018_31.gif" width="159" height="105 src=">

Пример 2. На раскрой (распил, обработку) поступает материал одного образца в количестве a единиц. Требуется изготовить из него l разных комплектующих изделий в количествах, пропорциональных числам b1, b2,…,bl (условие комплектности). Каждая единица материала может быть раскроена n различными способами, причем использование i-го способа (i = 1, 2,…,n) дает aik единиц k-го изделия (k = 1, 2,…,l). Необходимо найти план раскроя, обеспечивающий максимальное число комплектов.

Составим экономико-математическую модель задачи.

Обозначим через xi – число единиц материала, раскраиваемых i-ым способом, и x – число изготавливаемых комплектов изделий. Тогда целевая функция сводиться к нахождению

https://pandia.ru/text/78/539/images/image020_30.gif" width="163" height="116 src=">

1.4. Задача об использовании мощностей

Предприятию задан план производства продукции по времени и номенклатуре. Требуется за время t выпустить n1, n2,…,nk единиц продукции p1, p2,…,pk Продукция производится на станках s1, s2,…,sm. Для каждого станка известны производительность aij, то есть число единиц продукции pj, которые можно произвести на станке si и затраты bij на изготовление продукции pj на станке si в единицу времени. Необходимо составить такой план работы станков, чтобы затраты на производство всей продукции были минимальными.

Обозначим через xij – время, в течении которого станок будет занят изготовлением продукции pj (i = 1, 2,…,m; j = 1, 2,…,k) Тогда затраты на производство всей продукции выразятся функцией

https://pandia.ru/text/78/539/images/image023_31.gif" width="133" height="84 src=">

по номенклатуре и не отрицательности переменных

Неликвиды" href="/text/category/nelikvidi/" rel="bookmark">неликвидными активами банка, так как в случае непредвиденной потребности в наличности обратить кредиты в деньги без существенных потерь невозможно. Другое дело ценные бумаги , особенно государственные. Их можно в любой момент продать, получив некоторую прибыль или, во всяком случае, без большого убытка. Поэтому существует правило, согласно которому коммерческие банки должны покупать в определенной пропорции ликвидные активы – ценные бумаги, чтобы компенсировать не ликвидность кредитов. В нашем примере ликвидное ограничение таково: ценные бумаги должны составлять не менее 50% средств, размещенных в кредитах и ценных бумагах. Составим математическую модель задачи. Обозначим через x1 – средства в млн д. е., размещенные в кредитах, x2 – средства, вложенные в ценные бумаги. Цель банка состоит в том, чтобы получить максимальную прибыль от кредитов и ценных бумаг

https://pandia.ru/text/78/539/images/image026_24.gif" width="39" height="20 src=">. Учитывая балансовое, кредитное и ликвидное ограничения, получим систему ограничений неравенств

https://pandia.ru/text/78/539/images/image028_27.gif" width="65" height="40">, (11)

при условиях

(12)

Функция (11) называется целевой функцией ЗЛП, а условия (12)- ограничениями ЗЛП.

Определение ..gif" width="108" height="25">, при котором целевая функция принимает максимальное или минимальное значение.

Определение . Основной (или канонической) ЗЛП называется задача, которая состоит в определении оптимального значения целевой функции, при условии, что система ограничений представлена в виде системы уравнений

https://pandia.ru/text/78/539/images/image032_29.gif" width="175" height="63 src=">

Определение . Стандартной (или симметричной) ЗЛП называется задача, которая состоит в определении оптимального значения целевой функции, при условии, что система ограничений представлена в виде системы неравенств

https://pandia.ru/text/78/539/images/image034_27.gif" width="157" height="63">

3. ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЗАДАЧ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Рассмотрим ЗЛП с двумя переменными:

https://pandia.ru/text/78/539/images/image037_24.gif" width="112" height="103 src=">

Каждое неравенство системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми ai1x1 + ai2x2 = bi, (i = 1,2,…,m). Условие неотрицательности определяют полуплоскости с граничными прямыми x1 = 0, x2 = 0. Если система неравенств совместна, то область ее решений есть множество точек, принадлежащих всем указанным полуплоскостям. Совокупность этих точек будем называть многоугольником решений или областью допустимых решений (ОДР) ЗЛП. Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки равенств (граничные прямые).

Областью допустимых решений системы неравенств могут быть:

– выпуклый многоугольник;

– выпуклая многоугольная неограниченная область;

– пустая область;

– отрезок;

– единственная точка.

Целевая функция L определяет на плоскости семейство параллельных прямых, каждой из которых соответствует определенное значение L. Целевая функция без свободного члена c1x1 + c2x2 = 0, проходит через начало координат и называется основной прямой. Вектор перпендикулярный этой прямой, указывает направление наискорейшего возрастания L, а противоположный вектор – направление убывания L.

Таким образом, геометрическая интерпретация ЗЛП заключается в нахождении (построении) многоугольника решений, каждая точка которого является допустимым решением ЗЛП. Среди этого множества решений надо отыскать точку многоугольника решений, координаты которой обращают в min или max целевую функцию.

Теорема. Если ЗЛП имеет оптимальный план, то целевая функция задачи принимает свое оптимальное значение в одной из вершин многоугольника решений.

Для определения данной вершины строится L = 0, проходящая через начало координат и перпендикулярно вектору, и передвигается в направлении этого вектора до тех пор, пока она не коснется последней крайней точки многоугольника решений. Координаты полученной точки определяют максимальное значение целевой функции L и максимальный план данной задачи.

Нахождение минимального значения L отличается от нахождения ее максимального значения лишь тем, что L = 0 передвигается не в направлении вектора , а в противоположном направлении.

Если в направлении вектора многоугольник решений неограничен, то .

3.2. Графический метод решения задач
линейного программирования

Графический метод основан на геометрической интерпретации ЗЛП и включает следующие этапы:

– строят граничные прямые, уравнения которых получают в результате замены в системе ограничений ЗЛП знаков неравенств на знаки точных равенств;

– находят полуплоскости, определяемые каждым из ограничений неравенств ЗЛП;

– находят многоугольник решений (область допустимых решений);

– строят основную прямую с1x1 + c2x2 = 0, проходящую через начало координат и перпендикулярную вектору;

– перемещают прямую L = 0 в направлении вектора https://pandia.ru/text/78/539/images/image039_22.gif" width="60" height="20">. В результате находят точку (точки), в которой целевая функция принимает оптимальное решение, либо устанавливают неограниченность функции на множестве планов.