Федеральное агентство пообразованию
Государственноеобразовательное учреждение высшего
профессиональногообразования
«Санкт-Петербургскийгосударственный
политехническийуниверситет»
Факультет «Экономики именеджмента»
Кафедра «Стратегическийменеджмент»
Курсовая работа
«Математические методы имодели исследования операций»
Санкт-Петербург
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 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 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 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
Ограничения:
15x1
30x2300,
x375,
10x4300,
х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.
В столбце ReducedCost — нормированные стоимости — двойственные оценки. Такая оценка может бытьотлична от нуля только для переменной, имеющей в оптимальном плане нулевоезначение, и показывает, на какую величину следует изменить коэффициент этойпеременной в целевой функции, чтобы ее значение стало положительным (например,насколько увеличить цену изделия, чтобы его производить стало выгодно).Другимисловами, двойственные оценки могут быть использованы для определения приоритетаиспользуемых ресурсов в соответствии с их вкладом в величину целевой функции.Кроме того, эта оценка показывает, на какую величину ухудшится значение целевойфункции, если уйти от оптимального плана (нулевого значения переменной),добавив в него единицу соответствующей продукции. Т.е. данная оценка показываетценность от недоиспользования ресурсов. Для продукции 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; реальный — objectiveFunkcion; реально выполнимый план на поле — feasible Area (на графикеотсутствует).
/>
/>
Заключение
В даннойкурсовой работе была сформулирована цель работы, построенаэкономико-математическая модель задачи линейного программирования с еёподробным описанием, получен исчерпывающий отчёт о результатах решения задачи,а также получено графическое решение. Всё это осуществлялось при помощи ПППWinQSB, который является на данный момент одним из основных и самых удобныхпакетов реализующих большинство математических методов применяемых в экономикеи менеджменте.
Итак, яполучил оптимальное решения выпуска продукции при максимальной прибыли в 2690,2380единиц.
Всенеобходимые ограничения были выполнены. Были выявлены в каком количестве стоитпроизводить продукцию.
Ценностьрешения задачи линейного программирования в среде WinQSB объясняетсявозможностью на основании итогового отчёта принимать важные управленческиерешения и моделировать реальную производственную ситуацию. Это особенно ценносейчас, в век широкого применения информационных технологий при решении реальныхзадач.
Такимобразом, было наглядно представлено и прокомментировано полученное решениезадачи и нахождение оптимального плана выпуска продукции, где достигаласьмаксимальная прибыль и ресурсы использовались наиболее полно.