Экономическая сущность исследования операций. Мастяева И.Н

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Этапы построения математических моделей :

Подобные документы

Главная / Франшиза услуг

Задача №1

Решить транспортную задачу по данным таблицы 1.

Таблица 1 - Исходные данные

В таблице 1 введены следующие обозначения:

Аi-запасы продукции на i-м пункте отправления (ПО);

Bj-заявки на продукцию от Bj пунктов назначения (ПН);

Cij-стоимость перевозки единицы продукции с i-го ПО в j-й ПН.

Сумма всех заявок должна быть равна сумме всех запасов. Общую стоимость перевозки обозначим Z.

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

Решение задачи 1

Исходя из данных таблицы 1 исходная транспортная таблица имеет вид, представленный в таблице 2.

Таблица 2 Исходная транспортная таблица

Пункт отправления / Пункт назначения	заявки на продукцию


запасы продукции

Шаг 1: При заполнении таблицы учитывалось условие закрытости транспортной задачи, т.е. сумма всех заявок равна сумме всех запасов: общее число заявок = 87, общие запасы = 87. Задача является сбалансированной (закрытой).

Шаг 2: Начальное опорное решение находится методом минимальной стоимости.

Для этого запасы в Аi пунктов отправления распределяются в соответствии с заявками Bj пунктов назначения и заполняются клетки с минимальными стоимостями перевозок. При этом все запасы должны быть распределены в соответствии с заявками. Хij - количество перевозимого груза.

Опорный план, полученный методом минимальной стоимости

Вычислим затраты для этого опорного решения:

Zнач = C13 ? X13 + C14 ? X14 + C15 ? X15 + C25 ? X25 + C33 ? X33 + C41 ? X41 + C42 ? X42 +C44 ? X44 = 1 ? 2 + 6 ? 5 + 4 ? 4 + 27 ? 2 + 19 ? 1 + 14 ? 2 + 9 ? 13 + 7 ? 4 = 204.

Шаг 3: Проверим полученный опорный план на невырожденность. Количество заполненных клеток N должно удовлетворять условию N=n+m-1. В нашем случае N=8, n+m=5+4=9 , что удовлетворяет условию невырожденности плана.

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

Пусть a4 = 0. Тогда: a1 = 1; a2 = -1; a3 = 0; a4 = 0; b1 = 2; b2 = 3; b3 = 1; b4 = 4; b5 = 3.

Значение потенциалов записываем в таблицу рядом с Аi и Bj. Проверяем опорное решение на оптимальность для всех незаполненных клеток таблицы

a1 + b3 - c13 = 1 + 1 - 2 = 0 ? 0 a1 + b4 - c14 = 1 + 4 - 5 = 0 ? 0

a1 + b5 - c15 = 1 + 1 - 4 = -2 < 0 a2 + b5 - c25 = -1 + 3 - 2 = -4 < 0

a3 + b3 - c33 = 0 + 1 - 1 = 0 ? 0 a4 + b1 - c41 = 0 + 2 - 2 = 0 ? 0

a4 + b2 - c42 = 0 + 3 - 3 = 0 ? 0 a4 + b4 - c44 = 0 + 4 - 4 = 0 ? 0

Начальное опорное решение является оптимальным, т.к. нет положительных оценок. Значение целевой функции: Zопт=204.

2. Задача № 2

Соорудить траекторию движения ВС, соединяющую т. А и т. В. Затраты на перелет должны быть минимальны. Стоимость полета на каждом отрезке приведена внутри отрезка. Определить условное и безусловное оптимальные управления.

Решение задачи 2

Динамическое программирование специально приспособлено к так называемым многошаговым операциям.

Процесс динамического программирования разворачивается от конца (т.В) к началу (т.А) - условная оптимизация (условно оптимальное управление и условно минимальные затраты). Затем производится оптимизация от начала (т.А) к концу (т.В) - безусловная оптимизация (безусловно оптимальное управление и безусловно оптимальные затраты).

Для проведения условной оптимизации расстояние от А до В разделено в восточном направлении на 5 частей, а в северном - на 4 части. Тогда любой путь из А в В состоит из m = 4 + 5 = 9 отрезков, направленных на восток или на север. Процедуру условной оптимизации будем разворачивать в обратном направлении - от конца к началу. Прежде всего, произведем условную оптимизацию последнего, 9-го шага. Рассмотрим отдельно правый верхний угол нашей прямоугольной сетки. После 8-го шага мы можем быть в точке с затратами либо 7 (В1), либо 8 (В2). Перемещаемся в точку В1, из которой можно двигаться вниз (6 единиц), либо влево (5 единиц). Аналогичные операции проводятся по всем точкам, причем передвигаются в сторону, где затраты меньше. Условно минимальные затраты составили 47, что представлено в таблице 1.

Таблица 3 Процедура условной оптимизации

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

Таблица 4 Безусловное оптимальное управление

3. Задача № 3

Определить комплексные показатели надежности нерезервированных средств связи. Исходные данные приведены в табл. 3.

Для решения задания 3 необходимо:

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

Таблица 5

Решение задачи 3

Наиболее простую структуру имеет нерезервированная система, состоящая из n элементов, у которой отказ одного из элементов приводит к отказу всей системы. В этом случае система S имеет логически последовательное соединение элементов (рисунок 1).

Схема логического соединения элементов нерезервированной системы

Нерезервированная восстанавливаемая система в произвольный момент времени находится в одном из двух состояний: работоспособном G0 или неработоспособном G1. Процесс ее функционирования можно отразить графом состояний (рисунок 2):

Граф состояний нерезервированной системы

Из состояния S0 в состояние S1 система переходит в результате отказов с интенсивностью л, а из S1 в S0 - в результате восстановления с интенсивностью µ. В дальнейшем будем считать, что потоки отказов и восстановлений являются простейшими: л = const, µ = const. Это значит, что производительность труда ремонтника постоянна и не зависит от времени. Поэтому время восстановления имеет экспоненциальный закон распределения

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

В задаче TB = 1,5, следовательно µ = 1 / 1,5 ? 0,667.

Основным показателем надежности нерезервированной восстанавливаемой системы является коэффициент готовности Кг.

Для его определения рассмотрим работу системы на интервале времени (t,t+?t). Обозначим через P0(t), P0(t+?t) и P1(t),P1(t+?t) - вероятности того, что в момент времени t и t+?t система находится в состоянии S0 и S1. Тогда

P0(t)+P1(t)=1 и Kг=P0(t).

Обозначим также через P01(?t) и P10(?t) - условную вероятность того, что в момент времени t система находится или в состоянии S0 или в состоянии S1, а в момент времени t+?t или в состоянии S1 или в состоянии S0, т.е. за интервал времени?t произошел отказ (восстановление) системы.

Будем считать, что за время?t может произойти только один отказ или только одно восстановление. Тогда на интервале?t могут произойти четыре несовместимые события: A1(S0, S0) - в момент времени t система находилась в состоянии S0, в момент времени t+?t она осталась в том же состоянии, т.е. отказа не произошло;A2(S0, S1) - отказ произошел;A3(S1, S0) - восстановление произошло; A4(S1, S1) - восстановление не произошло.

Положим. Тогда получим систему дифференциальных уравнений

которая дополняется условием P0(t)+P1(t).

Решение системы при начальных условиях P0(t)=1 и P1(t)=0, т.е. в начальный момент времени система работоспособна, имеет вид

Если в начальный момент времени система неработоспособна, то P0(0)=0, P1(0)=1 и решение системы имеет вид

При независимо от начального состояния системы (S0 или S1) вероятности Po(t)=Kг, P1(t) стремятся к постоянным значениям

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

и получить систему линейных алгебраических уравнений, откуда непосредственно находятся P0=Kг и P1:

Для нашего случая нам известно значение µ ? 0,667.

Откуда можно определить значение л (по формуле

Зная значения л и µ из последней системы уравнений можно определить финальные вероятности Р0 и Р1, которые равны 0,9995 и 0,0005 соответственно.

4. Задача № 4

Определить показатели надежности резервированных средств связи. Исходные данные приведены в табл. 4.

Для решения задачи 4 необходимо:

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

транспортный затрата нерезервированный алгебраический

Таблица 6

Решение задачи 4

В резервированной системе отказ какого-либо элемента не обязательно приводит к отказу всей системы. Типичным случаем является логически параллельное соединение элементов (рисунок 1), при котором система отказывает тогда, когда отказывают все ее элементы. Такой тип резервирования называют постоянным или нагруженным (m-1)-кратным резервированием. В этом случае все элементы выполняют одну и ту же функцию, работают одновременно и равнонадежны.

Схема логического соединения элементов резервированной системы

Резервированная восстанавливаемая система описывается графом состояний (рисyнок 2).

Граф состояний резервированной системы

В отличие от нерезервированной системы резервированная система имеет 4 состояния: S0 - исправное; S1 - первый полукомплект работоспособен, а второй неисправен (ремонтируется); S2 - второй полукомплект работоспособен, а первый неисправен (ремонтируется); S3 - неработоспособное (оба комплекта ремонтируются).

С учетом условий задачи линейные алгебраические уравнения Колмогорова имеют вид:

2 · л · Р0 = µп · (Р1 + Р2) (1)
(л+ µп) · Р1 = л · Р0 + µв · Р3 (2)
(л+ µп)·Р2 = л · Р0 + µв · Р3 (3)
2 · µв · Р3 = л ·(Р1 + Р2) (4) ,

где л и µв - интенсивность отказа и восстановления;

µп - интенсивность переключения.

Система дополняется нормировочным уравнением

Р0+Р1+Р2+Р3=1. (5)

Из уравнений (2) и (3) видно, что Р1 = Р2. Тогда уравнение (1) запишется в виде:

Уравнение (4) имеет вид:

Уравнение (5) имеет вид:

Р0 = Т0 / (Т0 + 2Тп) = 3000 / (3000+2·45/3600) = 0,999991667.

Р1 = Р0 · Тп / Т0 = 0,999991667 · (45/3600) / 3000 = 0,00000417.

Р2 = Р0 · Тп / Т0 = 0,999991667 · (45/3600) / 3000 = 0,00000417.

Р3 = Р0 · ((Тп·Тв)/ Т0) = 0,999991667 · ((45/3600·1,5)/3000) = 0,00000625.

Определим среднее время безотказной работы резервированной системы:

Т01 = (Р0 · Тв) / (1- Р0) = (0,999991667 ·1,5) / (1 - 0,999991667) = 180 000 часов.

В вероятностной трактовке коэффициент готовности определяют по формуле:

где To - наработка на отказ (по условию задачи равна 3000),

TB - среднее время восстановления (по условию задачи равно 1,5).

Следовательно, коэффициент готовности равен Кг = 3000 / (3000 + 1,5) = 0,9995.

Список использованных источников

1. Вентцель Е.С. Исследование операций. Задачи, принципы, методология / Е.С.Вентцель. - М.: Наука, 1986.
2. Кремер Н.Ш. Исследование операций в экономике. Учебное пособие для вузов / Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман. - М.: ЮНИТИ, 2002.
3. Демидов Ю. М. Исследование операций. Пособие по выполнению контрольной работы.- М.: МГТУ ГА, 2010- 20 стр.
4. Волков И.K., Загоруйко Е.А. Исследование операций. Учебное пособие для вузов / под ред. B.C. Зарубина, A.П. Крищенко. - М.: Изд-во MГТУ им. Н.Э. Баумана, 2002.
5. Афанасьев М.Ю., Суворов Б.П. Исследование операций в экономике: модели, задачи, решения. Учебное пособие / М.Ю. Афанасьев, Б.П. Суворов. - М.: ИНФРА-М, 2003.

Размещено на Аllbest.ru

УДК 330.115(075.8) ББК22.1я73 А94

Афанасьев М.Ю., Суворов Б.П. Исследование операций в экономике: модели, задачи, решения:А94 Учеб. пособие. - М.: ИНФРА-М, 2003. - 444 с. - (Серия «Высшее образование»). ISBN 5-16-001580-9

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

Для студентов экономических вузов и преподавателей. ББК 22.1я73

ISBN5-16-001580-9	©М.Ю. Афанасьев, Б.П. Суворов, 2003

Предисловие..........................................................................................................................................................................................
Глава 1. Оптимизация плана производства........................................................................................................................................
Глава 2. Оптимальное смешение.......................................................................................................................................................
Глава 3. Оптимальный раскрой.........................................................................................................................................................
Глава 4. Планирование финансов......................................................................................................................................................
Глава 5. Транспортная задача............................................................................................................................................................
Глава 6. Задача о назначениях...........................................................................................................................................................
Глава 7. Сетевой анализ проектов. Метод СРМ...............................................................................................................................
Глава 8. Сетевой анализ проектов. Метод PERT.............................................................................................................................
Глава 9. Анализ затрат на реализацию проекта.............................................................................................................................
Глава 10. Стратегические игры........................................................................................................................................................
Глава 11. Нелинейное программирование......................................................................................................................................
Глава 12. Модели управления запасами.........................................................................................................................................
Глава 13. Модели систем массового обслуживания......................................................................................................................
Глава 14. Имитационное моделирование.......................................................................................................................................
Глава 15. Целочисленные задачи линейного программирования................................................................................................
Глава 16. Основы теории принятия решений.................................................................................................................................
Список основной литературы..........................................................................................................................................................
Список дополнительной литературы..............................................................................................................................................

Предисловие

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

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

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

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

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

Вопросы. Наиболее простая форма контроля знаний. Предлагается набор из нескольких вопросов и варианты ответов, один из которых верен.

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

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

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

В конце каждой главы приведены ответы на вопросы и решения задач.

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

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

Авторы благодарят А. Б. Ароновича за сотрудничество при подготовке глав 10 и 11, а также Н.В. Васильеву, чей опыт практических занятий по курсу «Исследование операций» позволил внести полезные коррективы в материал учебного пособия.

Глава 1. Оптимизация плана производства

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

микроэкономическими объектами.

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

целевую функцию;

ограничения;

допустимый план;

множество допустимых планов;

модель линейного программирования;

оптимальный план;

двойственные оценки;

границы устойчивости.

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

Введем обозначения:

п - количество выпускаемых продуктов;

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

а ij - объем затрат i- го ресурса на выпуск единицы j -й продукции; сj - прибыль от выпуска и реализации единицы j- го продукта;

b i - количество имеющегося i -го ресурса;х j - объем выпуска j -го продукта.

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

Здесь (1) - целевая функция (максимум прибыли);

(2) - система специальных ограничений (constraint) на объем фактически имеющихся ресурсов;

(3) - система общих ограничений (на неотрицательность переменных);

хj -переменная (variable).

Задача (1)-(3) называется задачей линейного программирования в стандартной форме на максимум. Задача линейного программирования в стандартной форме на минимумимеет вид

Вектор х = (x 1 ,x 2 , ...,x n ), компонентых j которого удовлетворяют ограничениям (2) и (3) (или (5) и (6) в задаче на минимум), называетсядопустимым решением илидопустимым планом задачи ЛП.

Совокупность всех допустимых планов называется множеством допустимых планов.

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

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

Двойственной к задаче ЛП (1)-(3) является задача

Соответственно, двойственной к задаче ЛП (7)-(9) является задача (1)-(3). Каждой переменной (специальному ограничению) исходной задачи соответствует специальное ограничение (переменная) двойственной задачи. Если исходная задача ЛП имеет решение, то имеет решение и двойственная к ней задача, при этом значения целевых функций для соответствующих оптимальных решений равны.

Компонента y i * оптимального решения двойственной задачи (7)-(9) называетсядвойственной оценкой

	å n a ijx j≤
(Dual Value) ограничения j = 1		исходной задачи ЛП.
	c j xj
Пусть ϕ = max (j = 1	), где х j - компонента допустимого решения задачи (1)-(3).

Тогда при выполнении условий невырожденности оптимального решения имеют место следующие соотношения:

Изменим значение правой части b i одного основного ограничения(RHS) исходной задачи ЛП.

Пусть b i ′ - минимальное значение правой части основного ограничения, при котором решениеу*

двойственной задачи не изменится. Тогда величину b i ′ называют нижней границей(Lower Bound) устойчивости по правой части ограничения.

Пусть b i ′′ - максимальное значение правой части основного ограничения, при котором решениеy*

двойственной задачи не изменится. Тогда величину b i ′′ называют верхней границей(Upper Bound) устойчивости по правой части ограничения.

Изменим значение одного коэффициента с j целевой функции исходной задачи ЛП.

Пусть c ′ j - минимальное значение коэффициента целевой функции, при котором оптимальное решение

x * исходной задачи не изменится. Тогда величинуc ′ j называют нижней границей устойчивости по коэффициенту целевой функции.

Пусть c ′ j ′ - максимальное значение коэффициента целевой функции, при котором оптимальное

решение х * исходной задачи не изменится. Тогда величинуc ′ j ′ называют верхней границей устойчивости по коэффициенту целевой функции.

Пример 1. Сколько производить?

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

1. Сколько продукта 1 следует производить для того, чтобы обеспечить максимальную прибыль?

2. Сколько продукта 2 следует производить для того, чтобы обеспечить максимальную прибыль?

3. Какова максимальная прибыль?

4. На сколько возрастет максимальная прибыль, если запасы сырья увеличатся на 1 т?

5. На сколько возрастет максимальная прибыль, если допустимый объем трудозатрат увеличится с 400

Решение. Пустьх 1 - объем выпуска продукта 1 в тоннах,х 2 - объем выпуска продукта 2 в тоннах. Тогда задача может быть описана в виде следующей модели линейного программирования:

Используя пакет РОМ for WINDOWS (далее- POMWIN ), исходную информацию для решения этой задачи можно представить в виде следующей таблицы:

Решая эту задачу, получаем следующий результат:

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

Чтобы обеспечить максимальную прибыль, следует производить 16,47 т продукта 1 и 14,12 т продукта 2.

Максимальная прибыль равна 988,24 тыс. руб.

В правом столбце таблицы указаны двойственные оценки для каждого ограничения. Так, величина 3,82 показывает, что при увеличении запаса сырья на 1 т (до 121) максимальное значение целевой функции для нового оптимального плана увеличится по сравнению с 988,24 на 3,82 тыс. руб. Аналогично можно интерпретировать значение двойственной оценки 1,32 для второго ресурса.

Следующая таблица содержит дополнительную информацию, предоставляемую пакетом POMWIN:

Два правых столбца таблицы - границы устойчивости по значениям коэффициентов целевой функции (верхняя часть таблицы) и правых частей ограничений (нижняя часть).

Так, в случае если прибыль, получаемая от реализации 1 т продукта 1, изменится, но останется в пределах от 21 до 40,83, количество продукта 1 в оптимальном плане не изменится.

В случае если запас сырья изменится, но останется в пределах от 85,71 до 166,66, двойственная оценка этого ресурса не изменится.

Соответственно, если допустимый объем трудозатрат изменится в пределах от 288 до 560 ч, двойственная оценка этого ресурса не изменится.

Если допустимый объем трудозатрат увеличится с 400 до 500 ч, то максимальная прибыль увеличится на 132 тыс. руб.

Пример 2. Производить или покупать?

Фирма производит два типа химикатов. На предстоящий месяц она заключила контракт на поставку следующего количества этих химикатов:

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

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

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

1. Сколько химикатов типа 1 следует производить фирме?

2. Сколько химикатов типа 2 следует производить фирме?

3. Сколько химикатов типа 1 следует закупать со стороны?

4. Сколько химикатов типа 2 следует закупать со стороны?

5. Каковы минимальные издержки на выполнение контракта?

6. Следует ли изменить объем закупок химикатов типа 2 со стороны, если их цена возрастет до 75 тыс. руб. за тонну?

7. На сколько возрастут минимальные издержки, если фонд времени работы реактора 2 сократится с 400 до 300 ч?

Решение. Введем обозначения:

x 1 - количество продукта 1, производимого компанией;z 1 - количество продукта 1, закупаемого компанией;x 2 - количество продукта 2, производимого компанией;z 2 - количество продукта 2, закупаемого компанией.

Модель линейного программирования приведена в следующей таблице:

Условия неотрицательности переменных: x 1 ³ 0 ;x 2 ³ 0 ;z 1 ³ 0 ;z 2 ³ 0 . Таблица исходной информации для расчетов вPOMWIN имеет следующий вид:

Результаты расчетов:

Таблица двойственных оценок и границ устойчивости:

Из таблицы двойственных оценок и границ устойчивости видно, что в пределах изменения закупочной цены на химикат типа 2 от 61 до 76 (ее фактическое значение 66) оптимальный план не изменится.

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

Ответы: 1. 55,55 т. 2. 38,89 т. 3. 44,44 т. 4. 81,11 т. 5. 11 475,56 тыс. руб. 6. Нет, не следует. 7. Ha 111 тыс. руб.

Вопросы Вопрос 1. Дана задача линейного программирования

Если эта задача имеет решение, то какие знаки имеют переменные y 1 иy 2 двойственной задачи? Варианты ответов:

Вопрос 2. На предприятии - два цеха. Проведены оптимизационные расчеты по определению программы развития предприятия с минимальными затратами. Получены оптимальный план и двойственные оценки ограничений по загрузке мощностей двух цехов. Оказалось, что двойственная оценка ограничений на производственные мощности первого цеха равна нулю, а второго - строго положительна. Это означает, что:

1) информации для ответа недостаточно;

2) мощности обоих цехов недогружены;

3) мощности обоих цехов использованы полностью;

4) мощности цеха 1 использованы полностью, а цеха 2 недогружены;

5) мощности цеха 1 недогружены, а цеха 1 использованы полностью.

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

Варианты ответов:

1) т/руб.; 2) руб./ч; 3) ч/руб.; 4) руб./т; 5) т.

Вопрос 4. Рассматривается задача оптимизации плана производства нефтепродуктов. Объем производства измеряется в тоннах. Задача решается на минимум издержек. Учитывается ограничение на время использования оборудования. В каких единицах измеряется значение коэффициентов матрицы для этого ограничения?

Варианты ответов:

Вопрос 5. Рассматривается задача оптимизации производственной программы. Критерий - максимум прибыли. Оптимальное значение критерия - 100. Двойственная оценка ограничения по трудозатратам равна 0,5, по объему производства - 1,5. Чему будет равна максимальная прибыль, если общий объем трудозатрат сократится на 10 единиц?

Варианты ответов:

1) 85; 2) 90; 3) 95; 4) 100; 5) 110.

Вопрос 6. Для всякого ли многогранника существует задача линейного программирования, допустимым множеством которой он является?

Варианты ответов:

1) да, для всякого;

2) нет, только для многогранника, имеющего более трех вершин;

3) нет, только для многогранника с положительными координатами вершин;

4) нет, только для выпуклого многогранника с неотрицательными координатами вершин;

5) нет, только для выпуклого многогранника.

Вопрос 7. Допустимое решение задачи линейного программирования:

1) должно одновременно удовлетворять всем ограничениям задачи;

2) должно удовлетворять некоторым, не обязательно всем, ограничениям задачи;

3) должно быть вершиной множества допустимых решений;

4) должно обеспечивать наилучшее значение целевой функции;

5) не удовлетворяет указанным выше условиям.

Вопрос 8. Рассмотрим следующую задачу линейного программирования:

при условиях

Оптимальное значение целевой функции в этой задаче равно: 1) 1600; 2) 1520; 3) 1800; 4) 1440; 5) не равно ни одному из указанных значений.

Вопрос 9. Рассмотрим следующую задачу линейного программирования: пои условиях

Какая из следующих точек с координатами (X, Y) не является допустимой? Варианты ответов:

5) ни одна из указанных.

Вопрос 10. Рассмотрим следующую задачу линейного программирования:

при условиях

Множество допустимых планов имеет следующие четыре вершины: (48, 84), (0, 120), (0, 0), (90, 0).

	Чему равно оптимальное значение целевой функции?
Варианты ответов:

	ни одному из указанных значений.

Задача 1. Нефтеперерабатывающая установка может работать в двух различных режимах. При работе в первом режиме из одной тонны нефти производится 300 кг темных и 600 кг светлых нефтепродуктов; при работе во втором режиме - 700 кг темных и 200 кг светлых нефтепродуктов. Ежедневно на этой установке необходимо производить 110 т темных и 70 т светлых нефтепродуктов. Это плановое задание необходимо ежедневно выполнять, расходуя минимальное количество нефти.

1. Сколько тонн нефти следует ежедневно перерабатывать в первом режиме?

2. Сколько тонн нефти следует ежедневно перерабатывать во втором режиме?

3. Каков минимальный ежедневный расход нефти?

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

в день 80 т светлых нефтепродуктов?

Задача 2. Фирма «Television» производит два вида телевизоров: «Астро» и «Космо».

В цехе 1 производят телевизионные трубки. На производство одной трубки к телевизору «Астро» требуется потратить 1,2 человекочаса, а на производство трубки к «Космо» - 1,8 человекочаса. В настоящее время в цехе 1 на производство трубок к обеим маркам телевизоров может быть затрачено не более 120 человекочасов в день.

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

Продажа каждого телевизора марки «Астро» обеспечивает прибыль в размере 1500 руб., а марки «Космо» - 2000 руб.

Фирма заинтересована в максимизации прибыли. Вопросы:

1. Сколько телевизоров «Астро» следует производить ежедневно?

2. Какова максимальная ежедневная прибыль телевизионной компании?

3. На сколько рублей в день увеличится прибыль, если ресурс времени в цехе 2 возрастет на 5 человекочасов?

4. Следует ли изменить план производства, если прибыль от телевизора «Космо» увеличится до 2200 руб.?

Задача 3. Чулочно-носочная фирма производит и продает два вида товаров: мужские носки и женские чулки. Фирма получает прибыль в размере 10 руб. от производства и продажи одной пары чулок и в размере 4 руб. от производства и продажи одной пары носков.

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

Руководство рассчитало, что в следующем месяце фирма ежедневно будет располагать следующими ресурсами рабочего времени на каждом из участков: 60 ч на участке 1; 70 ч на участке 2 и 100 ч на участке 3.

1. Сколько пар носков следует производить ежедневно, если фирма хочет максимизировать прибыль?

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

Размещено на http://www.allbest.ru/

1. Общие понятия и определения в и сследование операций

Следует усвоить основные понятия и определения исследования операций.

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

Замечание 1

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

Замечание 2

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

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

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

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

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

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

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

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

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

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

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

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

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

Основные особенности исследования операций:

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

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

3. Одной из существенных особенностей исследования операций является стремление найти оптимальное решение поставленной задачи. Однако часто такое решение оказывается недостижимым из-за ограничений, накладываемых имеющимися в наличии ресурсами (денежные средства, машинное время) или уровнем современной науки. Например, для многих комбинаторных задач, в частности задач календарного планирования при числе станков п > 4, оптимальное решение при современном развитии математики оказывается возможным найти лишь простым перебором вариантов. Тогда приходится ограничиваться поиском «достаточно хорошего», или субоптимального решения. Поэтому исследование операций один из его создателей -- Т. Саати -- определил как «...искусство давать плохие ответы на те практические вопросы, на которые даются еще худшие ответы другими методами».

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

Каждое операционное исследование проходит последовательно следующие основные этапы:

1) описание задачи планирования,

2) построение математической модели,

3) нахождение решения,

4) проверка и корректировка модели,

5) реализация найденного решения на практике.

Описание задачи планирования:

· Задачи сетевого планирования и управления

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

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

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

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

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

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

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

· Задачи выбора маршрута, или сетевые задачи, чаще всего встречаются при исследовании разнообразных задач на транспорте и в системе связи и состоят в определении наиболее экономичных маршрутов (1, стр.15).

2. Математическая форма моде ли

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

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

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

В создание современного математического аппарата и развитие многих направлений исследования операций большой вклад внесли российские ученые Л. В. Канторович, Н. П. Бусленко, Е. С. Вентцель, Н. Н. Воробьев, Н. Н. Моисеев, Д. Б. Юдин и многие другие. Особо следует отметить роль академика Л. В. Канторовича, который в 1939 г., занявшись планированием работы агрегатов фанерной фабрики, решил несколько задач: о наилучшей загрузке оборудования, раскрое материалов с наименьшими потерями, о распределении грузов по нескольким видам транспорта и др. Л. В. Канторович сформулировал новый класс условно-экстремальных задач и предложил универсальный метод их решения, положив начало новому направлению прикладной математики -- линейному программированию.

Значительный вклад в формирование и развитие исследования операций внесли зарубежные ученые Р. Акоф, Р. Беллман, Г. Данциг, Г. Кун, Дж. Нейман, Т. Саати, Р. Черч мен, А. Кофман и др. (1, стр. 17)

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

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

2. Формализация операций

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

3. Проверка адекватности модели

Исходный вариант модели необходимо проверить по следующим аспектам:

1) все ли существенные параметры включены в модель?

2) нет ли в модели несущественных параметров?

3) правильно ли отражены связи между параметрами?

4) правильно ли определены ограничения на значения параметров?

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

4. Корректировка модели

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

5. Оптимизация модели

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

Типы моделей:

В самом общем случае математическая модель задачи имеет вид:

max Z=F(x, y) (1.1)

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

где Z=F(x, y) - целевая функция (показатель качества или эффективность) системы; х -- вектор управляемых переменных; у -- вектор неуправляемых переменных; Gi(x, y)-- функция потребления i-го ресурса; bi -- величина i-го ресурса (например, плановый фонд машинного времени группы токарных автоматов в станко-часах).

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

Определение 2. Допустимое решение, в котором целевая функция достигает своего максимума или минимума называется оптимальным решением задачи.

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

1. Линейное программирование, если F(x, y), -- линейны относительно переменных х.

2. Нелинейное программирование, если F(x, y) или -- нелинейны относительно переменных х.

3. Динамическое программирование, если целевая функция F(x, y) имеет специальную структуру, являясь аддитивной или мультипликативной функцией от переменных х.

F(x)=F(x1, x2, …, xn) -- аддитивная функция, если F(x1, x2, …, xn)=, и функция F(x1, x2, …, xn) -- мультипликативная функция, если F(x1, x2, …, xn)=.

4. Геометрическое программирование, если целевая функция F(x) и ограничения представляют собой функции вида

Математическая модель задачи в этом случае записывается в виде

при условиях

где I=(m0, m0+1, …, n0); I[k]= (mk, mk+1, …, nk); mk+1=nk+1; m0=1; n0=n.

5. Стохастическое программирование, когда вектор неуправляемых переменных у случаен.

В этом случае математическая модель задачи (1.1--1.2) будет иметь

maxMyE=My{f(x, y)}

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

или вероятностных ограничениях

где My -- математическое ожидание по у; Р{gi (х)Ј b} -- вероятность того, что выполняется условие gi (х)Ј b.

6. Дискретное программирование, если на переменные xj наложено условие дискретности (например, целочисленности): xj -- целое, j=1,2,…,n1Јп.

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

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

3. Линейное программирование

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

Основные теоремы линейного программирования

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

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

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

Из теоремы 2.1 следует, что при отыскании оптимального решения достаточно просмотреть только крайние точки допустимого множества решений R.

Теорема 2.2. Каждое допустимое базисное решение соответствует крайней точке R.

Справедлива также следующая теорема, обратная к теореме 2.2. Теорема 2.3. Если -- крайняя точка допустимого множества решений R, то соответствующее решение x0 -- является допустимым базисным решением системы ограничений задачи линейного программирования.

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

Определение оптимального ассортимента. Имеется р видов ресурсов в количествах а1, а2, ..., аi, ..., аp и q видов изделий. Задана матрица А=||aik||, где аik характеризует нормы расхода i-го ресурса на единицу k-го изделия (k = 1, 2, ..., q).

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

Определить план выпуска изделий (оптимальный ассортимент), при котором суммарный показатель эффективности принимает наибольшее значение.

4. Нелинейное программирование

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

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

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

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

Основные понятия НЛП:

* целевую функция;

* ограничения;

* допустимый план;

* множество допустимых планов;

* модель нелинейного программирования;

* оптимальный план.

Необходимо уметь:

* определять, является ли функция выпуклой;

* строить функцию Лагранжа задачи НЛП;

* проверять оптимальность полученных решений.

Модели НЛП

В общем виде задача НЛП описывается с помощью следующей модели нелинейного программирования:

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

где х = (x1, х2, ..., хn) -- вектор переменных задачи.

Задача (1)--(3) называется задачей нелинейного программирования в стандартной форме на максимум.

Может быть сформулирована также задача НЛП на минимум.

Вектор х = (x1, х2, ..., хn), компоненты хj которого удовлетворяют ограничениям (2) и (3), называется допустимым решением или допустимым планом задачи НЛП.

Совокупность всех допустимых планов называется множеством допустимых планов.

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

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

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

Точка границы множества допустимых планов};

Точка множества допустимых планов, в которой функция F(x) недифференцируема}.

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

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

В экономических приложениях рассматриваются следующие классы задач НЛП.

На рисунке приводится классификация задач и методов нелинейного программирования.

Рисунок. Классификация задач и методов нелинейного программирования

Большинство существующих методов в нелинейном программировании можно разделить на два больших класса:

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

2. Недостаток: трудно получить свойство глобальной сходимости.

3. Задачи с ограничениями в виде равенств.

4. Метод замены переменных (МЗП)

5. Двойственные методы - методы, использующие понятие двойственности. В этом случае легко получить глобальную сходимость.

6. Недостаток: не дают решения исходной задачи в ходе решения - оно реализуемо лишь в конце итерационного процесса.

o Метод множителей Лагранжа (ММЛ)

o Методы штрафов

o Метод множителей

o Методы линеаризации для задач условной оптимизации

o Алгоритм Франка-Вульфа

o Метод допустимых направлений Зойтендейка

o Метод условного градиента

o Метод проекции градиента

o Сепарабельное программирование.

o Квадратичное программирование

1. Оптимизация нелинейной функции с ограничениями на неотрицательность значений переменных:

где х = (х1, х2,..., хn) -- вектор переменных задачи.

Пусть F(x) -- дифференцируемая функция.

Необходимые условия того, что в точке х0 достигается максимум функции F(x):

Это означает, что:

Если F(x) вогнутая функция (для задачи минимизации -- выпуклая), то эти условия являются также достаточными.

Функция F(x) с числовыми значениями, определенная на выпуклом множестве точек К, называется вогнутой, если для любой пары точек х1, х2 и для всех чисел l, 0 Ј l Ј 1, выполняется неравенство

то функция F(x) называется выпуклой. Если имеют место строгие неравенства, то говорят, что функция строго вогнута или строго выпукла.

Данное определение вогнутости (выпуклости) годится для любого типа функции. Практически, однако, применять его трудно.

Для дважды дифференцируемой функции F(x) имеет место следующий критерий. Дифференцируемая функция F(x) строго вогнута в некоторой окрестности точки если выполняются следующие условия:

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

Здесь -- частная производная второго порядка, вычисленная в точке х0.

Матрица размера п ґ п, составленная из элементов, называется матрицей Хессе (Hesse). По значениям ее главных миноров можно судить о выпуклости или вогнутости функции. Функция F(x) строго выпукла в малой окрестности точки х0, если все главные миноры ее матрицы Хессе строго положительны. Если имеют место нестрогие неравенства (і), то функция в окрестности точки х0 выпукла. Если при этом главные миноры матрицы Хессе от х не зависят, то функция всюду (строго) выпукла.

Весьма распространены относящиеся к данному типу модели квадратичного программирования, в которых целевая функция F(x) является квадратичной функцией переменных х1, х2, ..., хn. Существует большое число алгоритмов решения такого типа задач, в которых функция F(x) вогнутая (для задач минимизации -- выпуклая).

2. Модели выпуклого программирования. К такого рода моделям относятся задачи НЛП (1)--(3), в которых F(x) -- вогнутая (выпуклая) функция, a gi(x) -- выпуклые функции. При данных условиях локальный максимум (минимум) является и глобальным.

Пусть F(x) и gi(x), i= 1,..., т, -- дифференцируемые функции.

Необходимые и достаточные условия оптимальности решения -- выполнение условий Куна -- Таккера.

Рассмотрим задачу НЛП (1)--(3) и функцию Лагранжа

Условия Куна -- Таккера оптимальности решения х0 для задачи максимизации F(x) имеют вид

где -- частная производная функции Лагранжа по переменной хj при х = х0 и l = l0. Пусть максимальное значение F(x) равно F(x0) = F0. Числа связаны с F0 следующими соотношениями:

Из этих соотношений видно, что числа характеризуют реакцию значения F0 на изменение значения соответствующего bi. Например, если < 0, то при уменьшении bi (в пределах устойчивости) значение F0 увеличится, а = 0 указывает на несущественность соответствующего ограничения gi(х) Ј bi, которое может быть без ущерба для оптимального решения из системы ограничений исключено.

3. Сепарабельное программирование. Специальный случай выпуклого программирования при условии, что F(x) и все gi(х) -- сепарабельные функции, т.е.

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

4. Дробно-нелинейное программирование. Максимизировать (минимизировать) функцию

F(x) = F1(x)/F2(x).

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

5. Невыпуклое программирование. Функция F(x) и (или) какие-либо gi(x) не выпуклы. Надежных методов решения задач такого типа пока не существует (3, стр. 74-77)

Как пример, рассмотрим нелинейную модель оптимального распределения ресурсов:

Описание задачи распределения ресурсов

Задача распределения ресурсов рассматривается для n предприятий. Центр осуществляет управление этими промышленными предприятиями, выпускающими однотипную продукцию. Обозначим через Рi объем продукции, выпускаемой предприятием i, i=1,. ..,n. Результат функционирования центра определяется результатами функционирования отдельных производителей, т.к. центр сам не производит продукции.

Считаем, что величина продукции, произведенной i-м предприятием, определяется объемом фондов Fi и количеством рабочей силы Li, согласие производственной функции Кобба- Дугласа:

Где i=1,..,n (4)

В выражении (4) di и ki характеристики предприятия i (i=1,.. .,n), удовлетворяющие условиям: di > 0 , i=1,...,n.

Пусть wi - ставка заработной платы на предприятии i. Тогда доля дохода предприятия i в общей сумме прибыли объединения определится так:

Gi =ci*Pi-wi*Li , i=1,. . .,n.

Если величина фондов предприятия фиксирована, то объем продукции Pi однозначно определяется количеством рабочей силы.

Центр влияет на работу предприятий распределением дополнительного ресурса, который полностью находиться в его распоряжении. Если предприятие i получит дополнительный ресурс в количестве Vi, то оно сможет произвести продукцию в объеме

Задача центра состоит в распределении имеющегося в его распоряжении ресурса В, т. е. в определении оптимальных значений величин Vi, i =1,...,n, обеспечивающих максимум суммарной прибыли объединения в целом.

Математическая форма модели

В данной задаче считаем, что используется схема централизованного планирования, в рамках которой центр рассчитывает оптимальное распределение ресурсов, оптимальные величины рабочей силы при заданных параметрах модели. Конкретно центр изменяет Vi и Li, i = 1,...,n, из условий:

z = max (G1 + G2 + ,..., + Gn) (6)

Vi, Vimin, Li 0,i=1,...,n (7)

Анализ чувствительности модели как способ восстановления финансового равновесия.

Основой сохранения и восстановления финансового равновесия предприятия и снижения уровня риска является анализ чувствительности предложенной модели. Анализ чувствительности состоит из следующих этапов:

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

2. Выбор факторов, которые влияют на эти показатели.

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

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

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

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

Недостатки метода анализа чувствительности:

1. Метод не рассчитан на все случайное и возможное обстоятельства.

2. Метод не уточняет вероятность реализации альтернативных проектов.

Анализ чувствительности оптимального решения

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

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

1. Текущее базисное решение остается неизменным.

2. Текущее решение становится недопустимым.

3. Текущее решение становится неоптимальным.

4. Текущее решение становится неоптимальным и недопустимым.

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

Список литературы

1. «Исследование операций в экономике» учебное пособие для Вузов, 3-е издание, переработанное и дополненное, под ред. Н.Ш.Кремера, М.: Юрайт, 2013.

2. T.В. Алесинская « Основы логистики. Общие вопросы логистического управления» .Учебное пособие. Таганрог: Изд-во ТРТУ, 2005.

3. Афанасьев М.Ю., Суворов Б.П. Исследование операций в экономике: модели, задачи, решения. Учебное пособие, М, Инфра-М, 2003 г.

4. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. -М.: Мир,1984.

5. Грешилов А.А. Как принять наилучшее решение в реальных условиях. - М.: Радио и связь, 1991.

6. Попов Ю.Д. Линейное и нелинейное программирование. Учебное пособие. - Киев, 1988.

7. Зайченко Ю.П. Исследование операций. Учебное пособие для студентов вузов. - Киев: Вища школа. Головное издательство, 1979

8. Таха Х.. Введение в исследование операций: в 2-х книгах. - М.: Мир, 1985.

9. Акоф Р., Сасиени М. Основы исследования операций. - М.: Мир, 1997.

10. Акулич И.Л. Математическое программирование в примерах и задачах. - М.: Высшая школа, 1986.

11. Данко. Высшая математика в примерах и задачах.

12. Алексеев В. М., Голеев В. М., Тихомиров В. М. Сборник задач по оптимизации: Теория, примеры, задачи. М., Наука, 1984.

13. Берман Г. Н. Сборник задач по курсу математического анализа. М., Наука, 1985.

14. Ильин В.А.., Позняк Э.Г. Линейная алгебра. М., Наука, 1983.

15. Ильин В.А.., Позняк Э.Г. Основы математического анализа. М., Наука, Ч.1,2, 1980.

16. Клетеник Д..В. Сборник задач по аналитической геометрии. М., Наука, 1984.

17. Кудрявцев Л.Д.. Курс математического анализа. М., Высш. шк., Т. 1-3, 1988.

18. Кудрявцев Л.Д.. Краткий курс математического анализа. М., Наука, 1989.

19. Кудрявцев Л.Д.., Кутасов А..Д., Чехлов В.И., Шабунин М.И. Сборник задач по математическому анализу. Предел. Непрерывность. Дифференцируемость. М., Наука, 1984.

20. Кремер Н. Ш., Путко Б. А.., Тришин И.М., Фридман М. Ф. Высшая математика для экономистов. М., Банки и биржи, ЮНИТИ, 1998.

21. Гмурман В.Е. Теория вероятностей и математическая статистика. Учебное пособие для вузов. М., Высш. шк., 1999.

22. Ниворожкина Л.И., Морозова З.А. Основы статистики с элементами теории вероятностей для экономистов. Руководство для решения задач. Ростов н/Д., Феникс., 1999.

23. Данко П.Е. Высшая математика в упражнениях и задачах. Ч.2. М., Высш. шк., 1997.

24. Чистяков В.П. Курс теории вероятностей. М., Наука., 1987.

25. Севастьянов Б. А. Курс теории вероятностей и математической статистики. М., Наука., 1982.

26. Севастьянов Б.А., Чистяков В.П., Зубков А.М. Сборник задач по теории вероятностей. М., Наука., 1980.

27. Вентцель Е.С Исследование операций. Задачи. Принципы. Методология, 1980.

28. Горелик В.А., Ушаков И.А. Исследование операций. - М.: Машиностроение, 1986.

29. Исследование операций/ Под редакцией М.А. Войтенко и Н.Ш. Кремера.-М.: Экономическое образование, 1992.

30. Карасев А.И., Аксютин З.М., Савельева Т.И. Математические методы и модели в планировании М.: Экономика, 1987.

31. Исследование операций / Н. Н. Писарук. Минск: БГУ, 2013.272 c.

Размещено на Allbest.ru

...

Предприятие 1

Предприятие 2

Предприятие 3

Графическое решение задач линейного программирования. Решение задач линейного программирования симплекс-методом. Возможности практического использования математического программирования и экономико-математических методов при решении экономических задач.

курсовая работа , добавлен 02.10.2014

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

реферат , добавлен 11.02.2011

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

курсовая работа , добавлен 21.12.2010

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

курсовая работа , добавлен 17.02.2010

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

учебное пособие , добавлен 07.10.2014

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

курсовая работа , добавлен 07.05.2013

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

курсовая работа , добавлен 31.03.2014

Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования. Математическая постановка задачи линейного программирования. Общий вид задачи линейного программирования.

реферат , добавлен 28.12.2008

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

дипломная работа , добавлен 06.08.2013

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

КУРСОВОЙ ПРОЕКТ

Исследование операций в экономике

Введение

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

Решение задач линейного программирования симплекс-методом

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

Задача о назначениях

Задача о ранце

Заключение

Литература

Введение

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

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

В настоящее время существует две группы методов принятия управленческих решений:

) логический (когда решение принимается на основании опыта, интуиции и других личностных качеств лица, принимающего решение);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решить графически задачу

4x1+x2 → max,

при следующих ограничениях:

x1+7x2≤140

x1+10x2≤150

x1+20x2≤100

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

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

Обозначим границы области многоугольника решений.

Рассмотрим целевую функцию задачи F = 4x1+x2 → max.

Построим прямую, отвечающую значению функции F = 0: F = 4x1+x2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

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

Прямая F(x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

x1+7x2=140

x1+20x2=100

Решив систему уравнений, получим: x1 = 5.7534, x2 = 3.5616

Откуда найдем максимальное значение целевой функции:

(X) = 4*5.7534 + 1*3.5616 = 26.5753

2. Решение задач линейного программирования симплекс - методом.

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

Определим максимальное значение целевой функции F(X) = 5x1 + 5x2 + 11x3+9 при следующих условиях-ограничений.

При вычислениях значение Fc = 9 временно не учитываем.

линейный программирование математический экономический

x1 + x2 + x3 + x4≤0

x1 + 5x2 + 3x3 + 2x4≤0

x1 + 5x2 + 10x3 + 15x4≤0

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (≤) вводим базисную переменную x5. В 2-м неравенстве смысла (≤) вводим базисную переменную x6. В 3-м неравенстве смысла (≤) вводим базисную переменную x7.

x1 + 1x2 + 1x3 + 1x4 + 1x5 + 0x6 + 0x7 = 0

x1 + 5x2 + 3x3 + 2x4 + 0x5 + 1x6 + 0x7 = 0

x1 + 5x2 + 10x3 + 15x4 + 0x5 + 0x6 + 1x7 = 0

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

11111007532010351015001

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

Решим систему уравнений относительно базисных переменных: x5, x6, x7

Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,0,0,0,0)

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

БазисBx1x2x3x4x5x6x7x501111100x607532010x70351015001F(X0)0-5-5-110000

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

Определение новой базисной переменной.

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

Определение новой свободной переменной.

Вычислим значения Di по строкам как частное от деления: bi / ai3

и из них выберем наименьшее:(0: 1, 0: 3, 0: 10) = 0

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.

БазисBx1x2x3x4x5x6x7minx5011111000x6075320100x703510150010F(X1)0-5-5-1100000

Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x5 в план 1 войдет переменная x3.

Строка, соответствующая переменной x3 в плане 1, получена в результате деления всех элементов строки x5 плана 0 на разрешающий элемент РЭ=1

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x3 плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x3 и столбец x3.

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

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

Bx 1x 2x 3x 4x 5x 6x 70: 11: 11: 11: 11: 11: 10: 10: 10-(0 3):17-(1 3):15-(1 3):13-(1 3):12-(1 3):10-(1 3):11-(0 3):10-(0 3):10-(0 10):13-(1 10):15-(1 10):110-(1 10):115-(1 10):10-(1 10):10-(0 10):11-(0 10):10-(0 -11):1-5-(1 -11):1-5-(1 -11):1-11-(1 -11):10-(1 -11):10-(1 -11):10-(0 -11):10-(0 -11):1

Получаем новую симплекс-таблицу:

БазисBx1

МИНИСТЕРСТВО ОБРАЗОВАНИЯРОССИЙСКОЙ ФЕДЕРАЦИИ

Московский государственный университет экономики, статистики и информатики

Московский международный институт эконометрики, информатики, финансов и права

И.Н. Мастяева Г.Я. Горбовцов О.Н. Семенихина

ИССЛЕДОВАНИЕ ОПЕРАЦИЙ В ЭКОНОМИКЕ

Москва, 2001

УДК 519.6 ББК 22.18 М - 327

И.Н. Мастяева, Г.Я. Горбовцов, О.Н. Семенихина. ИССЛЕДОВАНИЕ ОПЕРАЦИЙ В ЭКОНОМИКЕ: Учебное пособие / Московский Государственный Университет Экономики, Статистики и Информатики. М.: МЭСИ, 2001. с.116


Программа курса «Исследование операций в экономике»........................
	Моделирование в экономике.....................................................................
	Теория двойственности в линейном программировании.
Двойственный симплексметод. .................................................................
2.1. Определение и экономический смысл двойственной ЗЛП...........
2.2.Основные положения теории двойственности..................................
2.3.Анализ решения ЗЛП с помощью теории двойственности.............
2.4. Анализ решения ЗЛП на основе отчётов MS EXCEL .....................
2.5. Двойственный симплекс-метод (Р-метод)........................................
	Целочисленные модели исследования операций...................................
	Экономические задачи, сводящиеся к транспортной модели..............
	Нелинейные модели................................................................................
5.1. Методы одномерной оптимизации..................................................
5.2. Методы безусловной оптимизации. ................................................
Литература. ..................................................................................................

Программа курса «Исследование операций в экономике»

Тема 1. Моделирование в экономике. Определение экономикоматематической модели, ее свойства. Классификация моделей по различным признакам.

Тема 2. Теория двойственности в линейном программировании. Двойственный симплекс-метод. Определение и правила постро-

ения двойственных задач, их экономический смысл. Теоремы двойственности. Различные способы отыскания решения двойственной задачи по решению прямой. Экономический анализ линейных моделей на основе теории двойственности. Двойственный симплекс-метод. Р- матрица, псевдоплан, условия перехода от одного псевдоплана к другому. Алгоритм двойственного симплекс-метода.

Тема 3. Целочисленные модели исследования операций.

Примеры задач целочисленного линейного программирования. Метод ветвей и границ решения задачи целочисленного линейного программирования: идея и алгоритм. Постановка задачи коммивояжера. Применение метода ветвей и границ для решения задачи коммивояжера.

Тема 4. Экономические задачи, сводящиеся к транспортным моделям. Транспортная задача (ТЗ) линейного программирования. Математическая модель. Закрытая и открытая модели ТЗ. Опорный план ТЗ. Методы построения первоначальных опорных планов. Метод потенциалов решения ТЗ, его обоснование и алгоритм. ТЗ с запрещенными перевозками. Задача оптимального распределения оборудования. Формирование оптимального штата фирмы. Задача календарного планирования. Задача о назначениях, венгерский метод ее решения. Оптимальное исследование рынка. Оптимальное использование рабочих агентов.

Тема 5. Нелинейные модели исследования операций.

Постановка задачи нелинейного программирования (ЗНП). Одномерная оптимизация. Алгоритм Свенна поиска отрезка, содержащего точку максимума. Метод золотого сечения решения задачи одномерной оптимизации. Безусловная оптимизация. Метод скорейшего подъема (спуска). Условная оптимизация. Метод Зойтендейка.

1. Моделирование в экономике

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

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

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

Микроэкономические; - одно-, двухсекторные (одно-, двухпродуктовые);

Многосекторные (многопродуктовые); - макроэкономические; - глобальные.

По учету фактора времени различают модели: - статические; - динамические.

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

По цели создания и применения различают модели: - балансовые; - эконометрические;

Оптимизационные; - сетевые;

Систем массового обслуживания; - имитационные (экспертные).

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

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

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

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

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

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

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

По учету фактора неопределенности различают модели:

- детерминированные (с однозначно определенными резуль-

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

- линейного и нелинейного программирования;

- корреляционно-регрессионные;

Матричные;

Сетевые;

Теории игр;

- теории массового обслуживания и т.д .

Домашнее задание 1.

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

		Распределение
	капиталовложений
			год 2 год 3





Максимальный
капиталовложений

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

2. Совет директоров фирмы изучает предложения по наращиванию производственных мощностей на трех принадлежащих фирме предприятиях. Для расширения всех трех предприятий фирма выделяет средства в объеме 5 млн. руб. Каждое предприятие представляет на рассмотрение проекты, которые характеризуются величинами суммарных затрат (C) и доходов (R), связанных с реализацией каждого из проектов. Соответствующие данные приведены в таблице, в которую включены также проекты с нулевыми затратами. Это позволяет учесть возможность отказаться от расширения какого-либо предприятия.

Цель фирмы состоит в получении максимального дохода от инвестиций.

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

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

Показатели			Варианты



Прибыль, д.е./ед.
Материальные

Трудовые ресурсы

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

4. Некоторая фирма переводит свой главный завод на производство определенного вида изделий, которые будут выпускаться в течение четырех месяцев. Величины спроса в течение этих четырех месяцев составляют 100, 200, 180 и 300 изделий соответственно. В каждый месяц спрос можно удовлетворить за счет

1) избытка произведенных в прошлом месяце изделий, сохраняющихся для реализации в будущем;

2) производства изделий в течение текущего месяца; 3) избытка производства изделий в более поздние месяцы в счет

невыполненных заказов.

Затраты на одно изделие в каждый месяц составляют 4 долл. Изделие, произведенное для более поздней реализации, влечет за собой дополнительные издержки на хранение в 0,5 долл. в месяц. С другой стороны, каждое изделие, выпускаемое в счет невыполненных заказов, облагается штрафом 2 долл. в месяц. Объем производства изделий меняется от месяца к месяцу в зависимости от выпуска других изделий.

В рассматриваемые четыре месяца предполагается выпуск 50, 180, 280 и 270 изделий соответственно. Требуется составить план, имеющий минимальную стоимость производства и хранения изделий.

5. Известен рыночный спрос на определенное изделие в количестве 180 штук. Это изделие может быть изготовлено двумя

предприятиями по различным технологиям. При производстве x1 изделий первым предприятием его затраты составят (4x1 + x1 2 ) руб., а

при изготовлении x2 изделий вторым предприятием они составят (8x2 + x2 2 ) руб. Определить, сколько изделий, изготовленных по каждой технологии, может предложить концерн, чтобы общие издержки его производства были минимальными.

6. На двух предприятиях холдинга необходимо изготовить 200

изделий некоторой продукции. Затраты, связанные с производством x1 изделий на первом предприятии, равны 4x1 2 руб., а затраты,

обусловленные изготовлением x2 изделий на втором предприятии, составляют (20x2 + 6x2 2 ) руб.

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

7. Для производства двух видов изделий А и В используется три типа технологического оборудования. Известны затраты времени и других ресурсов на производство ед. изделия каждого вида (см. табл.)

	Нормы времени	Огр. по фонду времени
оборудования		Верхний предел	Нижний предел




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

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

8.Имеется в наличии b = 5 единиц одного ресурса, который в начале планового периода необходимо распределить между тремя предприятиями. Известны аk – количество единиц ресурса, идущего на изготовление единицы продукции k-м предприятием (k = 1,2,3), а2 =а3 =1, а1 =2 и gk (yk ) – доход от выпуска yk единиц продукции k-м предприятием.

g1 (y1 )=1,4y1 – 0,2y1 2 g2 (y2 )=2y2 g3 (y3 )=2y3 – 0,3y3 2

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

9.Требуется разместить n производственных агрегатов на n различных производственных участках. Количество материалов, транспортируемых между агрегатами i и j, равно dij ; удельные затраты на транспортировку материалов с участка p на участок q составляют cqp . Построить модель целочисленного программирования, минимизирующую суммарные затраты на транспортировку.

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

Накладные		Производительность
	производство	(в единицах продукции)
	единицы продукции

Сформулировать задачу целочисленного программирования.

2. Теория двойственности в линейном программировании. Двойственный симплексметод.

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