ЗАДАЧА 1 . Симплексный метод решения задач линейного программирования
Для изготовления различных видов продукции 1, 2, 3 и 4 предприятие использует три вида сырья А, В и С. Нормы расхода сырья на производство единицы продукции каждого вида, цена одного изделия, а также запас каждого вида ресурса известны и приведены в таблице 1.1.
Составить такой план производства продукции, при котором предприятие получит максимальную прибыль.

Исходные данные задачи выбрать в таблицах 1.1, 1.2 в соответствии с вариантом.

Таблица 1.1 – Нормативы затрат ресурсов на единицу продукции каждого вида (общие для всех вариантов)

РЕСУРС	ВИДЫ ПРОДУКЦИИ				ЗАПАС
	1	2	3	4
А	6	8	4	7	a 5
В	0,75	0,64	0,5	0,8	a 6
С	8	12	10	14	a 7
ЭКОНОМИЧЕСКИЙ			a 3	a 4	МАХ

План решения задачи:

1. выбрать из таблиц исходные данные своего варианта;
2. обозначить неизвестные задачи;
3. сформировать систему ограничений и целевую функцию задачи;
4. привести систему ограничений к каноническому виду, обозначив и введя дополнительные переменные;
5. вычертить симплексную таблицу и заполнить её первоначальным опорным планом;
6. пользуясь алгоритмом симплексного метода, найти оптимальное решение задачи;

ЗАДАЧА 2
Решение открытой транспортной задачи методом потенциалов
На оптовых складах А 1 , А 2 , А 3 , А 4 имеются запасы некоторого продукта в известных количествах, который необходимо доставить в магазины В 1, В 2, В 3, В 4, В 5. Известны также тарифы на перевозку единицы продукта из каждого склада в каждый магазин.
Найти такой вариант прикрепления магазинов к складам, при котором сумма затрат на перевозку была бы минимальной.
Исходные данные задачи выбрать в таблицах 2.1, 2.2 в соответствии с вариантом.
Таблица 2.1 – Матрица тарифов (общая для всех вариантов)

Оптовые склады	Магазины					Запасы
	В 1	В 2	В 3	В 4	В 5
А 1	5	4	10	7	8	a 6
А 2	7	6	7	10	6	a 7
А 3	2	9	5	3	4	a 8
А 4	6	11	4	12	5	a 9
Потребности			a 3	a 4

План решения задачи:

1. Проверить, является решаемая задача закрытой или открытой.
2. Если задача открытая – выполнить действия, дающие возможность приступить к её решению.
3. Вычертить матрицу транспортной задачи и записать в неё опорный план, пользуясь одним из известных вам способов построения опорного плана (способ северо-западного угла, наилучшего тарифа, двойного предпочтения).
4. Проверить построенный опорный план на вырождение. Если надо, принять меры для преодоления вырождения опорного плана.
5. Рассчитать значение целевой функции для опорного плана.
6. По правилам метода потенциалов рассчитать потенциалы строк и столбцов.
7. Используя найденные потенциалы, проверить построенный опорный план на оптимальность.
8. Если решение оптимальное перейти к пункту 13.
9. Если решение неоптимальное, его нужно улучшить. Для этого надо найти клетку матрицы транспортной задачи, подлежащую улучшению, построить для неё замкнутый цикл, определить объём ресурсов для перемещения по вершинам этого цикла.
10. Выполнить перемещение ресурсов по вершинам цикла, не нарушая баланса по строкам и столбцам матрицы.
11. Перейти к пункту 6.
12. Выписать оптимальное решение и провести его экономический анализ.

ЗАДАЧА 3 . Оптимальное распределение ресурсов.
Совет директоров фирмы рассматривает предложение по наращиванию производственных мощностей для увеличения выпуска однородной продукции на четырех предприятиях, принадлежащих фирме.
Для модернизации предприятий совет директоров инвестирует средства в объеме 250 млн. р. с дискретностью 50 млн. р. Прирост выпуска продукции зависит от выделенной суммы, его значения предоставлены предприятиями и содержатся в таблице.
Найти предложение инвестиций между предприятиями, обеспечивающее фирме максимальный прирост выпуска продукции, причем на одно предприятие можно осуществить только одну инвестицию.
Исходные данные задачи выбрать в таблицах 3.1, 3.2 в соответствии с вариантом.
Таблица 3.1 – Значения параметров задачи

Инвестиции, млн. руб.	Прирост выпуска продукции, млн.руб.
	Предприятие	Предприятие	Предприятие	Предприятие
50	а 11	а 12	а 13	а 14
100	а 21	а 22	а 23	а 24
150	а 31	а 32	а 33	а 34
200	а 41	а 42	а 43	а 44
250	а 51	а 52	а 53	а 54

План решения задачи:

1. Выбрать из таблиц исходные данные своего варианта.
2. Разбить решение задачи на этапы по количеству предприятий, на которые предполагается осуществить инвестиции.
3. Составить рекуррентные соотношения
4. Провести первый этап расчета, когда инвестиции выделяются только первому предприятию
5. Провести второй этап расчета, когда инвестиции выделяют первому и второму предприятиям
6. Провести третий этап расчета, когда инвестиции выделяют 1-3-му предприятиям
7. Провести четвертый этап расчета, когда инвестиции распределяются между четырь­мя предприятиями
8. Выписать оптимальное решение и провести его экономический анализ.

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

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

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

в экономике

Б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

УДК 519.2 (075.8) ББК 22.1я73

Рецензенты:

канд. техн. наук, проф. В. Н. Калинина (Государственный университет управления)

канд. физ.-мат. наук, доц.В. М. Гончаренко (Финансовый университет)

С60 Соловьев В. И. Методы оптимальных решений: Учебное пособие. М.: Финансовый университет, 2012. 364 с.

ISBN 978-5-7942-ХХХХ-Х

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

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

УДК 519.2 (075.8) ББК 22.1я73

О ГЛАВЛЕНИЕ

Предисловие....................................
Введение	........................................
	Оптимальные решения в задачах планирования производства......
	Производственная функция................................................................................
	Модель поведения производителя.....................................................................
	Модели налогообложения..................................................................................
	Модель управления запасами.............................................................................
	.......................................................................
	Элементы линейной алгебры и балансовые модели экономики.....
	Векторы и матрицы.............................................................................................
	Линейные пространства......................................................................................
	Системы линейных алгебраических уравнений...............................................
	Неотрицательные решения систем линейных алгебраических уравнений...
	Обратная матрица................................................................................................
	Обращенный базис системы линейных алгебраических уравнений.............
	Модель межотраслевого баланса.......................................................................
	Контрольные вопросы и задания .......................................................................
	Методы линейного программирования............................................
	Постановка задачи линейного программирования..........................................
	Симплексный метод решения задач линейного программирования.............
	Метод искусственного базиса............................................................................
	Теория двойственности в линейном программировании................................
	Двойственный симплексный метод.................................................................
	Задачи целочисленного программирования...................................................
	Решение задач линейного программирования в пакете Microsoft Excel ....
	Контрольные вопросы и задания .....................................................................
	Оптимальные решения в линейных задачах
	управления производством и цепями поставок...............................
	Линейная задача планирования производства...............................................
	Задача о расшивке узких мест производства..................................................
	Транспортная задача.........................................................................................
	Контрольные вопросы и задания .....................................................................
	Методы нелинейного программирования.......................................
	Постановка задачи выпуклого программирования........................................
	Условия Каруша - Куна - Таккера..............................................................
	Метод возможных направлений......................................................................
	Метод условного градиента.............................................................................
	Метод штрафных функций...............................................................................
	Решение задач нелинейного программирования в пакете Microsoft Excel...
	Контрольные вопросы и задания .....................................................................

	Оптимальные решения
	в задачах изучения потребительского спроса..................................
	Бюджетное множество и функции полезности..............................................
	Предпочтения потребителя и функция полезности.......................................
	Модель поведения потребителя.......................................................................
	Уравнение Слуцкого.........................................................................................
	Модель рыночного равновесия........................................................................
	Контрольные вопросы и задания .....................................................................
	Задачи динамического программирования в экономике...............
	Постановка задачи динамического программирования...............................
	Задача оптимального распределения инвестиций.........................................
	Многошаговая задача управления производством и запасами....................
	Дискретные модели ценообразования опционов...........................................
	Контрольные вопросы и задания .....................................................................
	Теория графов и ее экономические приложения............................
	Графы..................................................................................................................
	Задачи о кратчайшем и критическом пути.....................................................
	Потоки в сетях...................................................................................................
	Контрольные вопросы и задания .....................................................................
	Задачи многокритериальной оптимизации в экономике...............
	Постановка задачи многокритериальной оптимизации...............................
	Оптимальность по Парето................................................................................
	Субоптимизация................................................................................................
	Лексикографическая оптимизация..................................................................
	Свертка критериев.............................................................................................
	Метод идеальной точки....................................................................................
	Метод последовательных уступок...................................................................
	Контрольные вопросы и задания .....................................................................
ГЛАВА 10.Теория игр и ее экономические приложения..................................
§ 10.1. Матричные игры................................................................................................
§ 10.2. Принятие решений в условиях неопределенности........................................
§ 10.3. Биматричные игры............................................................................................
§ 10.4. Непрерывные игры............................................................................................
§ 10.5. Позиционные игры............................................................................................
	Контрольные вопросы и задания .....................................................................
ГЛАВА 11.Моделирование поведения фирм на конкурентных рынках.........
§ 11.1. Модель поведения двух производителей на рынке одного товара.............
§ 11.2. Стратегии поведения дуополистов..................................................................
§ 11.3. Модели несовершенной и совершенной конкуренции..................................
§ 11.4. Модели конкуренции на рынке информационных технологий....................
	Контрольные вопросы и задания .....................................................................
ГЛАВА 12.Теория оптимального управления
	и ее экономические приложения.....................................................
§ 12.1. Постановка задачи оптимального управления...............................................
§ 12.2. Принцип максимума Понтрягина....................................................................
§ 12.3. Моделирование оптимального экономического роста..................................
§ 12.4. Моделирование динамики взаимодействия разработчиков
	коммерческого и некоммерческого программного обеспечения.................
	Контрольные вопросы и задания .....................................................................

П РЕДИСЛОВИЕ

Учебное пособие подготовлено в соответствии с действующими Федеральными государственными образовательными стандартами высшего профессионального образования по направлениям подготовки бакалавров «Экономика» (дисциплина «Методы оптимальных решений») и «Менеджмент» (дисциплина «Методы принятия управленческих решений»). Также во внимание принимался Федеральный государственный образовательный стандарт высшего профессионального образования по направлению подготовки бакалавров «Прикладная математика и информатика».

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

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

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

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

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

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

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

Во-первых, пособие является в определенном смысле самодостаточным: для его освоения студенту необходимо владеть (помимо арифметики, элементарной алгебры и основ экономики) лишь классическим дифференциальным исчислением, весь остальной необходимый математический аппарат вводится в нужном объеме по мере необходимости. В частности, это относится к методам линейной алгебры: серьезное внимание уделено методу Жордана - Гаусса и его вычислительной реализации.

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

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

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

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

В-шестых, в данном пособии динамическое программирование рассматривается только в применении к дискретным процессам, а в качестве ме-

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

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

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

адресу [email protected].

В ВЕДЕНИЕ

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

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

производства.

П РИМЕР В.1. Предприятие производит продукцию двух видов (A и Б), используя при изготовлении этой продукции ресурсы трех видов (первого, второго и третьего). Чтобы произвести одну единицу продукции A, нужно затратить по 1 единице первого и второго ресурсов и 2 единицы третьего ресурса. Для производства единицы продукции Б требуется 2 единицы первого ресурса и 1 единица второго ресурса. Запасы ресурсов у предприятия ограничены: на складах есть 90 единиц первого ресурса, 50 единиц второго и 80 единиц третьего ресурса.

Рыночная цена продукции A составляет 800 руб. а цена продукции Б равна 1000 руб. Сколько продукции следует произвести, чтобы получить наибольшую выручку?

Решение. Пусть предприятие планирует произвестиx 1 единиц продукции A иx 2 единиц продукции Б, тогда выручка предприятия будет, очевидно, равна

z = 800x 1 +1000x 2 .

Относительно величин x 1 иx 2 можно сказать следующее. Вопервых, они должны быть неотрицательными - отрицательный план производства продукции не имеет экономического смысла. Во вторых, общие расходы ресурсов при производствеx 1 единиц продукции A иx 2 единиц продукции Б не должны превысить запасы этих ресурсов.

Вычислим суммарный расход первого ресурса. На производство единицы продукции A тратится 1 единица первого ресурса, а всего про-

дукции A производится x 1 единиц, значит, на производство всей продукции A будет затрачено1 x 1 = x 1 единиц первого ресурса. Аналогично, на производство единицы продукции Б тратится 3 единицы первого ресурса, а всего продукции Б производитсяx 2 единиц, значит, на производство всей продукции Б будет затрачено3 x 2 единиц первого ресурса. Суммарный расход первого ресурса на производство всей продукции (и A, и Б) соста-

вит x 1 + 3 x 2 единиц. А в запасе есть всего 90 единиц этого ресурса. Значит, должно выполняться ограничение:x 1 + 3 x 2 90 . Добавляя аналогичные ограничения по второму и третьему ресурсам, приходим окончательно к следующей задаче.

Требуется найти такой п л а н				п р о и з в о д с т в а (т. е. числаx 1
и x 2 ) , чтобы выполнение				плана обеспечивало предприятию
наибольшую в ы р у ч к у
z = 800x 1 + 1000x 2 ® max
при о г р а н и ч е н и я х п о	р е с у р с а м
	x + 3 x
	x 1+ x 250,
и о г р а н и ч е н и я х н е о т р и ц а т е л ь н о с т и
	x 10,		x 20 .
Построим область точек на плоскости, где все пять ограничений
выполняются. Уравнение x 1 + 3 x 2 = 90				определяет множество точек плос-

кости, лежащих на некоторой прямой. Чтобы эту прямую построить, достаточно вспомнить, что любая прямая полностью определяется любыми своими двумя различными точками. Подставим в данное уравнение x 1 = 0,

	что 0 + 3 x 2 = 90 , откудаx 2 = 30. Итак, получили первую точку:
A (x 1 = 0,	x 2 = 30). Если подставить в данное уравнениеx 2 = 0, то получим:
x 1 + 3 × 0 = 90 или простоx 1 = 90. Получили вторую точкуB (x 1 = 90,		x 2 = 0).
Построим эту прямую: на рис. В.1, а она обозначена римской цифрой I.
Данная прямая разбивает всю плоскость на две полуплоскости, в одной
из полуплоскостей выполняется неравенство x 1 + 3 x 2 < 90 , а в другой -

венство x 1 + 3 x 2 > 90 . Проверим, какое из этих двух неравенств выполняется в

полуплоскости, которая лежит ниже и левее только что построенной прямой. Подставим в неравенство x 1 + 3 x 2 < 90 координаты точкиO (x 1 = 0,x 2 = 0):

0 + 3× 0< 90 - значит, и для всех остальных точек, которые лежат ниже и левее прямойx 1 + 3 x 2 = 90 , выполняется неравенствоx 1 + 3 x 2 < 90 .

Таким образом, ограничение x 1 + 3 x 2 90 выполняется во всех точ-

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

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

(рис. В.1, б ).

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

Таким образом, любой план производства, соответствующий некоторой точке из заштрихованного пятиугольника, можно выполнить, такие планы называются допустимыми и мы замечаем, что, вообще говоря, их очень много. Как из них выбрать оптимальный, т. е. приносящий наибольшую выручку z = 800 x 1 + 1000 x 2 ?

Оказывается, что если оптимальный план существует, то он обязательно будет лежать в одной из угловых точек множества допустимых планов, т. е. в одной из вершин OABCD . Координаты точкиA мы знаем. Найдем координаты других вершин, например, точкиС .

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

x + x
2x 1

	Из уравнения 2 x 1 = 80 получаемx 1 = 40. Подставимx 1 = 40 в урав-
	x 1 + x 2 = 50 и получим, чтоx 2 = 10. Таким образом точкаС имеет
координаты		С (x 1 = 40,x 2 = 10). Аналогично получаем координаты всех
оставшихся вершин пятиугольника OABCD .
	Итак, оптимальное решение обязательно находится в одной из угловых
	O (x 1	0, x 2 = 0), в этой точке выручкаz = 800 x 1 + 1000 x 2 = 800 × 0 +
	1000× 0= 0 ;
	A (x 1	0, x 2 = 30), z = 800x 1 + 1000x 2 = 800× 0+ 1000× 30= 30 000;
	B (x 1	30, x 2 = 20), z = 800x 1 + 1000x 2 = 800× 30+ 1000× 20= 44 000;

∙ C (x 1 = 40, x 2 = 10), z = 800x 1 + 1000x 2 = 800× 40+ 1000× 10= 42 000;

∙ D (x 1 = 40, x 2 = 0), z = 800x 1 + 1000x 2 = 800× 40+ 1000× 0= 32 000.

Видим, что наибольшую выручку (44 000 руб.) обеспечит план B (x 1 = 30,x 2 = 20), по которому нужно произвести 30 единиц продукции A

и 20 единиц продукции Б.

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

Н.Е. Гучек

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

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

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

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

Направление подготовки: 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 руб. Поэтому необходимо изучить устойчивость выводов по отношению к допустимым отклонениям исходных данных , а также по отношению к малым изменениям предпосылок используемой математической модели. Любое измерение проводится с некоторой погрешностью, и эту погрешность необходимо указывать.

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

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

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

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

УДК 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">. В результате находят точку (точки), в которой целевая функция принимает оптимальное решение, либо устанавливают неограниченность функции на множестве планов.