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

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

Доступные файлы (2):
tan11_1.xls26kb.12.04.2007 20:52скачать
n2.doc274kb.12.04.2007 20:52скачать

n2.doc




Содержание





Содержание 1

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

1.1. Задачи математического программирования, их классификация и примеры экономических систем. 2

1.2. Математический инструментарий исследования операций 5

1.3. Допустимое и оптимальное решение 7

1.4. Задачи линейного программирования. Допустимое и оптимальное решение. 8

2. Геометрическая интерпретация ЗЛП и графический метод решения. 11

Задача 11 15

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

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




1.1. Задачи математического программирования, их классификация и примеры экономических систем.



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

Методы решения задач распределения ресурсов позволяют:

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

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

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

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

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

Задачи ремонта и замены оборудования позволяют определить:

- такие сроки восстановительного ремонта и моменты замены оборудования, при которых минимизируются затраты на ремонт, замену за все время его эксплуатации;

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

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

- что выгоднее производить товар или закупать его;

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

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

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

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

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

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

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



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

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

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

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

1.3. Допустимое и оптимальное решение



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

Точка, в которой достигается максимальное(минимальное) на значение целевой функции

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

1.4. Задачи линейного программирования. Допустимое и оптимальное решение.



В общем виде задача линейного программирования (в дальнейшем ЗЛП) может быть сформулирована как задача нахождения наибольшего значения линейной функции
(1)
на некотором множестве D Rn ,где x D удовлетворяют сис­теме ограничений







(2)
и, возможно, ограничениям
(3)
He умаляя общности, можно считать, что в системе (2) первые т ограничений являются неравенствами, а последующие — l-уравнениями. Очевидно, этого всегда можно добиться за счет простого переупорядочения ограничений. Относительно направления знака неравенства будем предполагать, что левая часть меньше или равна правой. Добиться этого можно, умножив на (-1) обе части тех неравенств, которые имеют противоположный знак. Ограничения (3), вообще говоря, могут быть рассмотрены как частный случай ограничений в форме неравенств, но в силу особой структуры их обычно выделяют отдельно и называют условиями неотрицательности (или тривиальными ограничениями).

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

эквивалентна задаче поиска минимума функции



Часто условия задачи (1) - (3), содержащей ограничения только типа неравенств, бывает удобно записывать в сокращенной матричной форме

где с и xвекторы из пространства Rn, bвектор из простран­ства Rm, a А — матрица размерности mп.

Задачу линейного программирования, записанную в форме (1) - (3), называют общей задачей линейного программирования (ОЗЛП).

Если все ограничения в задаче линейного программирования являются уравнениями и на все переменные xj наложены условия неотрицательности, то она называется задачей линейного программирования в канонической форме, или канонической задачей линейного программирования (КЗЛП). В матричной форме КЗЛП можно записать в следующем виде:


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

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

Планом ЗЛП называется всякий вектор х из пространства Rn.

Допустимым планом называется такой план ЗЛП, кото­рый удовлетворяет ограничениям (1.2)-(1.3), т. е. содержится в области D. Сама область D называется при этом областью допустимых планов. Оптимальным планом х* называется такой допустимый план, при котором целевая функция достига­ет оптимального (в нашем случае — максимального) значения, т. е. план, удовлетворяющий условию
max f(x) = f(x*).
Величина f* = f(x*) называется оптимальным значением целевой функции.

Решением задачи называется пара *, f*), состоящая из оптимального плана и оптимального значения целевой функ­ции, а процесс решения заключается в отыскании множества всех решений ЗЛП.


2. Геометрическая интерпретация ЗЛП и графический метод решения.




Рассмотрим следующий пример. Пусть дана задача максимизации линейной целевой функции

f(x) = x1 + Зх2 max
на множестве
D = {xR2х1 + х 6

х1 - х  2

х1 3

х1  0, х2  0}
Так как количество переменных в неравенствах, задающих область допустимых планов задачи, равно двум, то ее можно изобразить на координатной плоскости (см. рис. 1.1).

На рис. 1.1 показано, что каждое неравенство определяет некоторую полуплоскость. Соответствующие области для каж­дого ограничения отмечены штрихами. Пересечение D данных полуплоскостей (т. е. множество точек, которые одновременно принадлежат каждой их них) является областью допустимых планов задачи. Поведение целевой функции f(x) = х1+ Зх2 в рамках двумерной иллюстрации может быть охарактеризовано с помощью линий уровня.

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




Рис. 1.1



Для линейной функции двух переменных линия уровня пред­ставляет собой прямую, перпендикулярную вектору с, который служит градиентом данной функции. Следовательно, если линия уровня определяется уравнением f (x) = clxl+c2x2= const , то этот вектор имеет вид
(1.8)
и указывает направление возрастания функции.

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

На рис. 1.1 изображен некоторый частный случай, для кото­рого решение ЗЛП достигается в угловой точке х* =(0, 6) обла­сти D. Нетрудно представить, что возможны и другие варианты. Они изображены на рис. 1.2.

Рисунок (а) иллюстрирует ситуацию неограниченности це­левой функции f(x) = cx на множестве D, т. е. сколько бы мы ни перемещались по линиям уровня в направлении вектора с, ее значение будет возрастать.

В случае, изображенном на рисунке (b), линия уровня, со­ответствующая максимальному значению f(x), касается грани множества D, и, соответственно, все точки, лежащие на этой гра­ни, являются оптимальными планами.

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

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

Несмотря на свою очевидную ограниченность, графический метод решения ЗЛП часто оказывается полезным. В частности, он может быть применен не только к задачам с двумя перемен­ными и ограничениями в виде неравенств, но и к каноническим задачам вида (1.7), у которых п - т = 2, где п — количество пе­ременных, a m — ранг матрицы А.

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


Рис. 1.2


(1.9)
где — линейные функции.

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

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

Последняя ЗЛП может быть решена графически.

Задача 11



Для производства 3 видов продукции используется 3 вида сырья. Нормы затрат каждого из видов сырья на единицу продукции данного вида, запасы сырья, а также прибыль с единицы продукции приведены в таблицах.

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

  1. построить математическую модель задачи;

  2. выбрать метод решения и привести задачу к канонической форме;

  3. решить задачу средствами Microsoft Excel;

  4. дать геометрическую интерпретацию решения.




Продукция/Сырье

А

B

C

Запас сырья

I

1

2

0

10

II

2

1

0

8

III

1

0

1

3

прибыль

5

2

1

 


Необходимо, чтобы сырьё вида III было израсходовано полностью.
Решение.


  1. Построение математической модели.

Обозначим количество изделий вида A - ,

количество изделий вида В - ,

количество изделий вида С - .

Тогда прибыль от продажи изделий вида A – 5, B – 2, С - .

Тогда целевая функция будет иметь вид

. (1)

Затраты сырья на изготовление всех видов продукции выражаются следующими формулами

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


  1. Приведём математическую модель к каноническому виду






Введём дополнительные переменные и запишем задачу в канонической форме:






  1. Решим задачу средствами Microsoft Excel.




  1. Заполняем таблицу с исходными данными.

  2. В ячейки B12-D12 заносим допустимые решения , , .

3. Введём формулу для вычисления целевой функции, для этого в ячейки B16:D16 вставим следующие формулы =B12*B6 (согласно (1)), =С12*С6, =D12*D6 соответственно, а в В17 сумму значений по всем видам продукции =СУММ(B16:D16).


  1. В ячейки с F3 по F6 введём формулы для вычисления затрат на производство

=B3*B12+C3*C12+D3*D12

=B4*B12+C4*C12+D4*D12

=B5*B12+C5*C12+D5*D12.
4. Для нахождения значений переменных, при которых целевая функция получает максимальное значение, воспользуемся инструментом «Поиск решения» (Solve).

Сделаем активной ячейку с целевой функцией и выполним команду Сервис>Поиск решения (Solve).

Откроется одноименное диалоговое окно. В поле «Установить целевую ячейку» указываем адрес ячейки с целевой функцией.

По умолчанию программа предлагает вычислить максимальное значение, что требуется в нашей задаче.
5.Поставим курсор в поле с указанием переменных и выделим диапазон B12:D12.
6. Для ввода ограничений поместим курсор в поле «Ограничения»(Add), в открывшемся окне добавления ограничений курсор находится в левой части. Щелкнем по ячейке, в которую введена формула для вычисления левой части ограничения F3, в средней части выберем нужный знак отношения, поместив курсор в правую часть окна щелкнем по ячейке с ограничением Е3.

Щелкнем по кнопке «Добавить»(Add). Введём все ограничения аналогичным образом.

Завершив ввод последнего ограничения, щелкнем по кнопке «ОК».

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

Последнее действие – нажать кнопку «Выполнить».
Ответ: Максимальная прибыль будет получена, если предприятие выпустит 3 единиц изделия А, 2 изделия В, изделия С выпускать не будет.

Максимальная прибыль составит 19 ден.ед.


сырьё/ продукция

А

В

С

Запасы сырья

Затраты

I

1

2

0

10

7

II

2

1

0

8

8

III

1

0

1

3

3

Прибыль

5

2

1

 

 


























































План










x1

x2

x3










3

2

0














































c1x1

c2x2

c3x3










15

4

0













Целевая функция

19






  1. Решим задачу графическим методом






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

функцию . Таким образом мы имеем 2 неизвестных параметра и можем решить задачу графически.

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


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





  1. Акулич.И.Л. Математическое программирование в примерах и задачах: Учебное пособие для студентов эконом. спец. вузов. Москва, 1986г.

  2. Моисеев Н.Н. Методы оптимизации. Москва, 1978г.

  3. Ляшенко И.Н. Линейное и нелинейное программирование. Киев, 1975г.

  4. Моисеев Н.Н. Математические задачи системного анализа. Москва, 1981г.

  5. Крушевский А.В. Справочник по экономико-математическим моделям и методам. Киев, 1982г.

  6. Глушков В.М. О диалоговом методе решения оптимизационных задач – Кибернетика, №4, 1975г.

  7. Пикуза В, Гаращенко А.Экономические и финансовые расчеты в Excel. СПб., 2004.

  8. Дубина А.Г. и др. Excel для экономистов и менеджеров. - СПб., 2004

  9. Internet
Учебный текст
© perviydoc.ru
При копировании укажите ссылку.
обратиться к администрации