Федеральное агентство по образованию
Государственное образовательное учреждение высшего
профессионального образования
«Санкт-Петербургский государственный
политехнический университет»
Факультет «Экономики и менеджмента»
Кафедра «Стратегический менеджмент»
Курсовая работа
«Математические методы и модели исследования операций»
Санкт-Петербург
2010
Оглавление
Введение
1. Задача линейного программирования
2. Построение экономико-математической задачи
3. Решение с помощью пакета WinQSB
3.1 Анализ оптимального решения и его чувствительности
3.2 Графический анализ чувствительности
Заключение
Введение
Известно, что решения, обоснованные математически, значительно эффективнее тех, которые принимаются лишь с опорой на опыт и интуицию. Для математического обоснования решений используются методы исследования операций, требующие громоздких математических расчетов с использованием современной вычислительной техники. За последнее время было создано много новых программ, предназначенных для использования при выработке управленческих решений. Однако, наряду со специальными программами и их пакетами, при обосновании решений по-прежнему широко используется программа Microsoft Ехсеl[1]
, но в данном курсовом проекте работа строится на основе ППП WinQSB специально выпущенном на 64-х битную модель Windows 7.
Цель данного курсового проекта – показать, на каком уровне находится знание ППП WinQSB, а так же конечно найти оптимальное решение поставленной задачи.
В курсовом проекте поставлены точные задачи, которые влекут за собой определенные требования, а именно:
1) Получаемая прибыль должна быть максимальной
2) Используемые ресурса должны быть израсходованы на максимальном уровне.
Для решения поставленных задач используется изначальная таблица, которая любезно была предоставлена преподавателем. Выбранный мною вариант для решения – 15-ый.
Предприятие может выпускать 4 вида продукции (A, B, C, D), используя при этом 3 вида ресурсов (R1, R2, R3). Нормы расхода ресурсов, прибыль, получаемая от реализации единицы продукции, значения ожидаемого спроса на продукцию, наличие ресурсов в планируемом периоде, убытки от недоиспользования ресурсов представлены в таблице 1:
Таблица1. Исходные данные
| Наименование показателей |
Норма расхода ресурсов на единицу продукции, усл. Ед./ед. продукции |
Наличие ресурсов, условных единиц |
Убытки от недоиспользования единицы ресурса, тыс. руб/усл. ед. |
|||
| A |
В |
С |
D |
|||
| Ресурс R1 |
4 |
2 |
1 |
4 |
500 + 2N |
2 |
| Ресурс R2 |
2 |
- |
2 |
3 |
200 + 2N |
3 |
| Ресурс R3 |
2 |
3 |
1 |
- |
540 + 2N |
4 |
| Прибыль от реалии- зации единицы продукции, тыс. руб./ед. прод. |
N |
N – 5 |
N – 6 |
N – 2 |
N = 15 |
|
| Минимальная величина спроса, ед. продукции |
N |
2N |
0 |
N – 5 |
||
| Максимальная величина спроса, ед. продукции |
10N |
20N |
5N |
20N |
||
Мой первый шаг в курсовом проекте – это подставить номер моего варианта вместо N, тем самым мы получаем исходные данные, которые будут использоваться для решения задачи. Данные которые я получаю при подстановке своего варианта приведены в таблице 2.
Таблица 2. Полученные данные для решения задачи
| Наименование показателей |
Норма расхода ресурсов на единицу продукции, усл. ед./ед. продукции |
Наличие ресурсов, условных единиц |
Убытки от недоиспользования единицы ресурса, тыс. руб/усл. ед. |
|||
| A |
В |
С |
D |
|||
| Ресурс R1 |
4 |
2 |
1 |
4 |
530 |
2 |
| Ресурс R2 |
2 |
- |
2 |
3 |
230 |
3 |
| Ресурс R3 |
2 |
3 |
1 |
- |
570 |
4 |
| Прибыль от реалии- зации единицы продукции, тыс. руб./ед. прод. |
15 |
10 |
9 |
13 |
N = 15 |
|
| Минимальная величина спроса, ед. продукции |
15 |
30 |
0 |
10 |
||
| Максимальная величина спроса, ед. продукции |
150 |
300 |
75 |
300 |
||
1. Задача линейного программирования
Линейное программирование
– это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием.
Необходимым условием постановки задачи линейного программирования являются ограничения на наличие ресурсов, величину спроса, производственную мощность предприятия и другие производственные факторы.
Сущность линейного программирования состоит в нахождении точек наибольшего или наименьшего значения некоторой функции при определенном наборе ограничений, налагаемых на аргументы и образующих систему ограничений
, которая имеет, как правило, бесконечное множество решений. Каждая совокупность значений переменных (аргументов функции F
), которые удовлетворяют системе ограничений, называется допустимым планом
задачи линейного программирования. Функция F
, максимум или минимум которой определяется, называется целевой функцией
задачи. Допустимый план, на котором достигается максимум или минимум функции F
, называется оптимальным планом
задачи.
Система ограничений, определяющая множество планов, диктуется условиями производства. Задачей линейного программирования (ЗЛП
) является выбор из множества допустимых планов наиболее выгодного (оптимального).
Математическая модель любой задачи линейного программирования включает в себя:
1) максимум или минимум целевой функции (критерий оптимальности);
2) систему ограничений в форме линейных уравнений и неравенств;
2. Построение экономико-математической задачи
Требуется определить план выпуска четырех видов продукции, обеспечивающий максимальную прибыль от ее реализации. На изготовление этой продукции расходуются три вида ресурсов (R
). С учетом рыночного спроса и производственно-технологических возможностей заданы предельные границы выпуска каждого вида продукции. Эти границы, наличие и нормы расхода ресурсов, а также маржинальная прибыль (разность между выручкой и переменными издержками) на единицу продукции приведены в таблице:
| Ресурсы |
А |
В |
С |
D |
Наличие |
| Ресурс R1 |
4 |
2 |
1 |
4 |
530 |
| Ресурс R2 |
2 |
- |
2 |
3 |
230 |
| Ресурс R3 |
2 |
3 |
1 |
- |
570 |
| Прибыль |
15 |
10 |
9 |
13 |
|
| Нижн. гр. |
15 |
30 |
0 |
10 |
|
| Верхн. гр. |
150 |
300 |
75 |
300 |
Построим математическую модель задачи, обозначив количество выпускаемых изделий через х1
, х2
, х3
, х4
, а целевую функцию (валовую маржинальную прибыль) — через F:
F(х) = 15х1
+ 10х2
+ 9х3
+ 13х4
→ Мах;
Граничные условия:
4х1
+ 2х2
+ 1х3
+ 4х4
<
530;
2х1
+…+ 2х3
+ 3х4
<
230;
2х1
+ 3х2
+ 1х3
+… <
570;
х1,
х2,
х3,
х4
>
0
Ограничения:
15<
x1
<150,
30<
x2
<
300,
x3
<
75,
10<
x4
<
300,
х1,
х2,
х3,
х4
>
0
Решения, удовлетворяющие системе ограничений условий задачи и требованиям не отрицательности, называются допустимыми
, а решения, удовлетворяющие одновременно и требованиям максимизации целевой функции, - оптимальными
.
Выше описанная задача линейного программирования представлена в общей форме, но мне следует представить задачу в канонической форме. В канонической форме задача является задачей на максимум некоторой линейной функции F, ее система ограничений состоит только из равенств (уравнений). Для этого мне необходимо ввести дополнительные переменные.
На данном этапе следует представить задачу в канонической форме. Для того, чтобы реализовать данное действие, следует добавить дополнительные переменные. Получаем систему уравнений:
4х1
+ 2х2
+ х3
+ 4х4
+ х5
= 530;
2х1
+…+ 2х3
+ 3х4
+х6
= 230;
2х1
+ 3х2
+ х3
+…+х7
= 570;
х1,
х2,
х3,
х4,
х5,
х6,
х7
>
0
(4х1
+ 2х2
+ х3
+ 4х4
– мы реально физически используем данное кол-во; х5
– степень использования ресурса R1 (недоиспользованный ресурс). Аналогично будет и для других уравнений).
При этом необходимо ввести в целевую функцию издержки («убытки от недоиспользования ресурса»), которые были нам даны в изначальном условии, поэтому целевая функция будет следующей:
F(х) = 15х1
+ 10х2
+ 9х3
+ 13х4
– 2х5
– 3х6
– 4х7
→ Мах.
3. Решение с помощью пакета WinQSB
На данном этапе я использую ППП WinQSB, с помощью которого я решаю задачу линейного и целочисленного программирования. Следующий шаг – это выбор матричной формы задачи. Был произведен ввод данных на основе ограничений.
Рис. 1. Матричная форма
В строке Variable — имена переменных. У нас это вид производимой продукции.
В строке Mахimize — коэффициенты целевой функции, показывает степень зависимости между изменяемой и целевой ячейками. Т.е. значения, которые мы будем максимизировать.
В строках С1, С2, С3 — названия ограничений. В соответствующих строках вводятся коэффициенты этих ограничений, за которыми следуют их знаки (в столбце Direction) и правые части (в столбце R. Н. S.). Это норма расхода ресурсов на единицу производимой продукции с использованием конкретного ресурса при наличии этих ресурсов.
LowerBound и UpperBound — строки для задания граничных условий: нижние границы переменных и верхние нижние границы переменных, соответственно. Верхние и нижние границы показывают, в каких пределах мы можем изменять количество расхода ресурсов.
В строке Variable Туре указан заданный тип переменных: Continuous (Непрерывная).
Рис. 2. Задача линейного программирования в стандартной форме.
Теперь можно приступить к нахождению решения задачи. При этом задача решается симплексным методом, если все переменные определены как непрерывные. По окончании решения появилось сообщение о том, что задача решена (The Problem is solved.) и получено оптимальное решение (Optimal solution is achieved.). Под оптимальным производственным планом можно понимать такой объем выпуска продукции, при котором будут обеспечиваться планы производства продукции, а также затраты на производство оказываются минимальными.
После того, как завершен этап по построению задачи линейного программирования в стандартной форме, мы получаем сводный отчет, который показывает большие сведения о найденном решении
3.1 Анализ оптимального решения и его чувствительности
Этот анализ позволяет выяснить, как изменения коэффициентов целевой функции и правых частей ограничений могут повлиять на найденное оптимальное решение. При этом, однако, предполагается, что изменяется только один коэффициент целевой функции или правая часть только одного ограничения. Сведений о том, что произойдет при одновременном изменении нескольких входных данных задачи, сводный отчет не дает.
Рис. 3. Сводный отчет о решении задачи линейного программирования
Сводный отчет состоит из двух таблиц.
В первой таблице выводится следующая информация, касающаяся переменных:
В первых двух столбцах — номера и имена переменных.
В столбце Solution Value— найденное решение. В данной работе получаются такие значения:
15;
157,6190;
67,1429;
21,9048;
Следовательно по этим значениям мы делаем вывод о том что, для предприятия самым выгодным будет производить продукцию, чтобы получить максимальную выручку и минимальные затраты/издержки, в объеме равном:
1) 15 единиц продукции 1;
2) 157,6190 единиц продукции 2;
3) 67,1429 единиц продукции 3;
4) 21,9048 единиц продукции 4.
В столбце Unit Cost or Profit c(j) — удельные затраты или удельная маржинальная прибыль (разность между продажной ценой и переменными затратами), являющиеся коэффициентами целевой функции. Опять же в моем случае я получил такие значения:
15;
9;
10;
13;
-2;
-3;
-4.
В столбце Total Contribution — итоговый вклад в оптимальное значение целевой функции, определяемый каждой переменной (произведение коэффициента целевой функции на оптимальное значение этой переменной). В моем примере — это маржинальная прибыль от продажи каждого продукта, т.е. получаем:
Продукция 1 – 225;
Продукция 2 – 1576,19;
Продукция 3 – 604,2858;
Продукция 4 – 284,7619.
В столбце Reduced Cost — нормированные стоимости — двойственные оценки. Такая оценка может быть отлична от нуля только для переменной, имеющей в оптимальном плане нулевое значение, и показывает, на какую величину следует изменить коэффициент этой переменной в целевой функции, чтобы ее значение стало положительным (например, насколько увеличить цену изделия, чтобы его производить стало выгодно).Другими словами, двойственные оценки могут быть использованы для определения приоритета используемых ресурсов в соответствии с их вкладом в величину целевой функции. Кроме того, эта оценка показывает, на какую величину ухудшится значение целевой функции, если уйти от оптимального плана (нулевого значения переменной), добавив в него единицу соответствующей продукции. Т.е. данная оценка показывает ценность от недоиспользования ресурсов. Для продукции 2, 3, 4 идут нулевые значения, т.е. продукты не являются дефицитными и не ограничивают производство продукции. А для продукции 1, 5, 6, 7 программа посчитала отрицательные значения.
В столбце Basis Status — состояние переменных в последней симплекс-таблице: они могут быть либо базисными (basic), либо небазисными и равными своей нижней границе (at bound). (Нижняя граница переменных задана в строке LowerBound матричной формы задачи.). В моем случае продукция 2, 3, 4 – базисные, а остальные – небазисные.
В столбцах Allowable Min. c(j) и Allowable Мах. c(j) — границы интервалов оптимальности, то есть пределы изменения коэффициентов целевой функции, при которых сохраняется прежнее оптимальное решение (М обозначает ∞). В моем примере такими интервалами будут:
1 вид продукции (-∞; 15,333];
2 вид продукции [9,50; 23,75];
3 вид продукции [4,4167; 12,00];
4 вид продукции [12,5; 26,00];
5 вид продукции (-∞; 1,2857];
6 вид продукции (-∞; 2,6190]
7 вид продукции (-∞; 2,4762].
Эти интервалы показывают, что при изменении удельной прибыли от продажи единицы одного вида продукции не изменят структуру оптимального плана.
В последней строке таблицы Objective: Function Max. — оптимальное значение целевой функции (в моем случае Function Max. = 2690,2380). В нашем примере мы производили максимизацию. Определив значения управляемых переменных, мы нашли решение поставленной задачи. Прибыль от реализации всей продукции составляет 2690,2380 единиц.
Во второй таблице сводного отчета содержатся следующие сведения об ограничениях задачи:
В первых двух столбцах — номера и названия ограничений.
В столбце Left Hand Side — левые части ограничений, вычисленные при оптимальных значениях переменных. В моей задаче — это количество ресурсов, которое будет израсходовано при оптимальном выпуске продукции.
В столбце Direction — знаки ограничений.
В столбце Right Hand Side — правые части ограничений. В моей задаче — это количество ресурсов, которое мы имеем по условию задачи.
В столбце Slack or Surplus — остатки или избытки, вычисленные по правилу: «правая часть минус левая» для ограничений типа <= или «левая часть минус правая» для ограничений типа >= Они могут показывать, например, величину неиспользованного ресурса (для лимитирующих ограничений, то есть ограничений сверху) или превышение требуемого уровня (для ограничений-требований, то есть ограничений снизу). Если остаток или избыток равен нулю, то соответствующее ограничение является связанным (активным), а соответствующий ресурс — дефицитным (используемым полностью). В противном случае ограничение несвязанное, а ресурс недефицитен. В моем случае все три ресурса являются дефицитными, т.е. используются полностью. Поэтому можно пожелать производителю делать запасы данных ресурсов для безостановочного производства продукции.
В столбце Shadow Price — теневые цены — двойственные оценки, показывающие, на какую величину изменится оптимальное значение целевой функции при увеличении на единицу правой части соответствующего ограничения, тогда как остальные данные неизменны (например, при добавлении единицы соответствующего ресурса). Кроме того, теневая цена — это максимальная цена, которую стоит платить за дополнительное количество дефицитного ресурса, чтобы приобретение было выгодным, или минимальная цена его продажи. Теневая цена отлична от нуля только для связанных ограничений. В общем, по полученным данным я делаю такой вывод что:
1) При увеличении запаса ресурса R1 на одну единицу моя общая выручка увеличится на 1,2857
2) При увеличении запаса ресурса R2 на одну единицу моя общая выручка увеличится на 2,6190
3) При увеличении запаса ресурса R3 на одну единицу моя общая выручка увеличится на 2,4762
В столбцах Allowable Min. RHS и Allowable Мах. RHS — границы интервалов устойчивости, то есть пределы изменения правых частей ограничений (запасов ресурсов), при которых неизменны соответствующие теневые цены и в оптимальном решении сохраняется прежний набор ненулевых переменных (ассортимент продукции). В моем примере такими интервалами будут: для 1-го ресурса — [511,6667; 686,6667], для 2-го — [112,500; 243,7500], для 3-го — [335,000; 597,500]. Это значит, что оптимальный план производимой продукции не изменится до тех пор, пока запасы/параметры конкретного ресурса не выйдут за рамки его ограничений.
После нахождения решения стало доступным меню Results. С его помощью можно узнать, сколько итераций и времени работы процессора потрачено на поиск решения. Было произведено 5 итераций. Задача была решена за 0,015 секунды (см. рис. 4)
Рис. 4.
После этого была предпринята попытка поиска альтернативного решения, но его не оказалось.
3.2 Графический анализ чувствительности
Если выбран графический метод решения, то построенное графическое изображение можно использовать для анализа чувствительности модели. Анализ моделей на чувствительность — это процесс, реализуемый после получения оптимального решения. В рамках такого анализа выявляется чувствительность оптимального решения к определенным изменениям исходной модели.
По оси Х выбран продукт А, по оси У выбран продут В.Я вводила различные изменения параметров и наблюдала за появлением ограничительных линий. С помощью этого метода можно выяснить, как повлияет изменение количества продукции на оптимальное решение. Жирная белая точка показывает пересечение выбранных параметров, текущую оптимальную точку. Вверху графика отмечены следующие обозначения по цветам: принуждённый - constraint; реальный - objective Funkcion; реально выполнимый план на поле - feasible Area (на графике отсутствует).
Заключение
В данной курсовой работе была сформулирована цель работы, построена экономико-математическая модель задачи линейного программирования с её подробным описанием, получен исчерпывающий отчёт о результатах решения задачи, а также получено графическое решение. Всё это осуществлялось при помощи ППП WinQSB, который является на данный момент одним из основных и самых удобных пакетов реализующих большинство математических методов применяемых в экономике и менеджменте.
Итак, я получил оптимальное решения выпуска продукции при максимальной прибыли в 2690,2380 единиц.
Все необходимые ограничения были выполнены. Были выявлены в каком количестве стоит производить продукцию.
Ценность решения задачи линейного программирования в среде WinQSB объясняется возможностью на основании итогового отчёта принимать важные управленческие решения и моделировать реальную производственную ситуацию. Это особенно ценно сейчас, в век широкого применения информационных технологий при решении реальных задач.
Таким образом, было наглядно представлено и прокомментировано полученное решение задачи и нахождение оптимального плана выпуска продукции, где достигалась максимальная прибыль и ресурсы использовались наиболее полно.
[1]
Кутузов А. Л. Математические методы и модели исследования операций. Учебное пособие стр. 3. СПБ, издательство Политехнического университета 2009г.