Cучков В.К

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

Сучков Владилен Константинович

Учебно-теоретическое издание

РЕШЕНИЙ

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

В.К. Сучков

РЕШЕНИЙ

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

В.К. Сучков

БЕЛГОРОД

«КООПЕРАТИВНОЕ ОБРАЗОВАНИЕ»

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

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

БЕЛГОРОДСКИЙ УНИВЕРСИТЕТ КООПЕРАЦИИ, ЭКОНОМИКИ И ПРАВА

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

Рекомендовано Научно-методическим советом университета

БЕЛГОРОД

«КООПЕРАТИВНОЕ ОБРАЗОВАНИЕ»

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

Технический редактор Г.А. Габелкова

Компьютерный набор и верстка В.К. Сучкова, С.М. Филатовой

Лицензия на издательскую деятельность ЛР № 040889 от 14.04.98.

Лицензия на полиграфическую деятельность ПЛД № 32-17 от 17.06.97.

Сдано в набор 10.03.2010. Подписано в печать 11.06.2010

Формат 60.84 1/16. Бумага офсетная. Гарнитура Times New Roman.

Ризография. Усл. печ. л. 7,8. Тираж 100 экз. Заказ

Издательство Белгородского университета кооперации, экономики и права

308023, г. Белгород, ул. Садовая, 116 а

ББК 22.11 С 91

Рекомендовано к изданию кафедрой естественнонаучных дисциплин. Протокол № 8 от 13 апреля 2013г.

Автор

Сучков Владилен Константинович, канд. физ.-мат. наук, доцент кафедры естественнонаучных дисциплин БУКЭП

Рецензенты:

Москаленко Николай Иванович, канд. физ.-мат. наук, доцент кафедры естественнонаучных дисциплин БУКЭП

Флоринский Владимир Вячеславович, канд. физ.-мат. наук, доцент кафедры математического анализа БелГУ

С 91 Методы оптимальных решений: Учеб. пособие. – Белгород: Издательство БУКЭП, 2013. – с

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

УДК 512 (075.8)

ББК 22.143я73

Издательство БУКЭП,2013

Содержание

Введение…………………………………………………
Раздел 1.Основные понятия теории принятия решений…………………………………………………... Раздел 2. Линейное программирование………………...
Тема 2.1. Задача планирования производства……..
Тема 2.2. Задача составления рациона
Тема 2.3. Транспортная задача…………..
Тема 2.4. Основная задача линейного программирования……………………………………….
Тема 2.5. Геометрический метод решения задачи линейного программирования………………………
Тема 2.6. Основные теоремы теории линейного программирования
Тема 2.7. Метод последовательного улучшения плана
(симплекс-метод)
Тема 2.8. Решение задачи линейного программирования с использованием симплекс-таблиц
Тема 2.9. Метод потенциалов
Тема 2.10. Двойственные задачи линейного программирования
Тема 2.11. Усовершенствованный симплекс-метод
Тема 2.12. Метод искусственного базиса
Тема 2.13. Метод Гомори Раздел 3.Нелинейное программирование
Тема 3.1.Квадратичное программирование
Тема 3.2. Дробно-линейное программирование
Тема 3.3. Метод множителей Лагранжа
Тема 3.4. Примеры экономико-математических моделей нелинейного программирования
Тема 3.5. Задача выпуклого программирования Тема 3.6. Численные методы оптимизации Раздел 4. Динамическое программирование Тема 4.1. Принцип оптимальности и уравнение Беллмана Тема 4.2. Примеры решения оптимизационных задач методом динамического программирования Раздел 5. Принятие решений в условиях определенности Тема 5.1. Критерии принятия решений Тема 5.2. Минимаксный (максиминный) критерий Тема 5.3. Критерий Лапласа Тема 5.4. Многокритериальные задачи. Парето-оптимальность Раздел 6. Принятие решений в условиях неопределенности Тема 6.1. Принятие решений в условиях вероятностной неопределенности Тема 6.2. Принятие решений в условиях полной неопределенности Раздел 7. Матричные игры Тема 7.1. Антагонистические игры Тема 7.2. Понятия неантагонистической игры Раздел 8. Коллективные решения Тема 8.1. Основные идеи методов экспертных оценок Тема 8.2 Математические методы анализа экспертных оценок Раздел 9. Контрольные вопросы, тесты, задания по дисциплине

ВВЕДЕНИЕ

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

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

РАЗДЕЛ 1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ПРИНЯТИЯ РЕШЕНИЙ

Теория принятия решений имеет дело с такими понятиям как:

лицо, принимающее решение; регламент; цель; ресурсы; риски и неопределенности; критерии оценки принимаемого решения; математико-компьютерная поддержка принятия решений и другие.

Лицо, принимающее решения, сокращенно ЛПР. Это тот, на ком лежит ответственность за принятое решение, кто подписывает приказ или иной документ, в котором выражено решение. Им может быть: преподаватель, выставляющий оценку студенту; генеральный директор фирмы; командир воинской части; губернатор; мэр города; директор завода; министр и т.п., словом - ответственный работник. В качестве ЛПР может быть коллектив: Совет директоров фирмы, общее собрание акционеров; Ученый Совет университета и т.п.

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

Принятию решения предшествует обычно обсуждение различных вариантов. Но если решение принято, то его надо исполнять, а не обсуждать.

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

Цель. Каждое решение направлено на достижение одной или нескольких целей. Например, Совет директоров фирмы "Бытовые холодильники" желал:

- продолжать выпуск холодильников;

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

Ресурсы. Каждое решение предполагает использование определенных ресурсов. Так, Совет директоров фирмы "Бытовые холодильники" исходит из существования уже имеющейся системы предприятий, позволяющей выпускать холодильники типа "Альфа" и типа "Бета". Если бы такого производства не было, то целесообразно сначала: обсудить вопрос о их строительстве, о посильности таких затрат для фирмы и другие вопросы.

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

Таким образом при обсуждении проекта решения надо определить цель проекта и ресурсы ее достижения.

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

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

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

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

F (X) → оптимум, где X Є A.

Здесь Х - управляющий параметр, А – область допустимых значений параметра, F (X) – целевая функция.

РАЗДЕЛ 2. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Тема 2.1. Задача планирования производства

Для производства n видов товаров предприятие располагает m видами сырья. Пусть a – расход i -го сырья на производство единицы j -го товара; b – запас i- го сырья; c– прибыль предприятия от реализации единицы j -го товара; x – выпуск j -го товара; (x , x ₂,..., х ) – план производства.

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

Прибыль предприятия выражается функцией цели:

f =

условие производства товаров выражается системой неравенств:

ax+ax+ax++a+x

ax+ax+ax+ax

ax+ax+ax+ax,

xx, x

Таким образом, экономическая задача о планировании производства имеет следующую математическую формулировку.

Найти наибольшее значение линейной функции f = если переменные величины x неотрицательные и удовлетворяют системе линейных неравенств:

Тема 2.2. Задача составления рациона

Для откорма животных предприятие располагает n видами кормов, при этом контролируется потребление m питательных веществ, содержащихся в них.

Пусть:

– содержание i– го питательного вещества в единице

j -го корма;

– минимально допустимая суточная норма потребления i -го питательного вещества;

– стоимость единицы j -го корма;

– количество j -го корма в дневном рационе (). Требуется составить самый дешевый рацион. Стоимость рациона выражается формулой:

.

Условие откорма выражается системой неравенств:

Таким образом, задача о составлении рациона принимает следующую математическую формулировку: найти наименьшее значение функции

,

если величины неотрицательные и удовлетворяют системе неравенств

Тема 2.3 Транспортная задача

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

- стоимость перевозки 1т груза с - го склада-тому потребителю (тариф);

– запас груза на i -м складе (т);

– спрос груза j -м потребителем (т).

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

И так как весь груз со складов должен быть вывезен, а спрос каждого из потребителей удовлетворен, то:

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

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

Тема 2.4. Основная задача линейного программирования.

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

.

Эту систему уравнений можно записать в матричной форме где:

, ,

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

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

Задача. Пусть дана функция f = и система ограничений:

Требуется найти оптимальный план. Покажем, как эту задачу можно свести к основной задаче ЛП. В левую часть каждого i - го неравенства добавим неотрицательную величину у такую, чтобы неравенство обратилось в равенство (= l,2 ,..., m). В результате система неравенства обратится в систему уравнений:

Целевую функцию f запишем в виде:

f =

То есть, по существу целевая функция не изменилась. Предположим, что точка (x, x,...,x_n, y, y₂,...,y_m) удовлетворяет системе уравнений. Тогда, опуская положительные слагаемые у, получаем, что точка (x, х₂,..., х) удовлетворяет системе неравенств. Наоборот, если точка (х,х₂,...,х) удовлетворяет системе неравенств, то можно подобрать неотрицательные величины у, у₂,...,у_m такие, что точка (x,х₂,…, х, у, у₂,..., у_m) будет удовлетворять системе уравнений. Наконец, ясно, что если функция f принимает оптимальное значение в точке (x, х₂,...,х, y,y,, у_m), то она примет оптимальное значение в точке (x,х₂,...,х ) и наоборот.

Добавочные переменные величины y, у₂,...,у_m называются балансовыми переменными. Если система ограничений задачи ЛП задана неравенствами

,

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

Дата добавления: 2014-10-31