Решение задач линейного программирования на примере оптимизации и транспортной задачи, анализ чувствительности с помощью ms excel.
 Скачать 1.06 Mb.
|
|
1 Лабораторная работа №1 Тема Решение задач линейного программирования на примере оптимизации и транспортной задачи, анализ чувствительности с помощью MS Excel. Цель Обеспечить качество и сократить время решения задач поиска максимума и минимума целевой функции при условии, что переменные принадлежат некоторой области, имеющей ограничения, с использованием надстройки Поиск решения пакета MS Excel как инструментальных средств моделирования (на примере решения однокритериальных задач. Порядок выполнения работы 1. Изучение теории и примера. 2. Построение математической модели задачи в форме задачи линейного программирования. 3. Решение задачи линейного программирования с использованием надстройки Поиск решения пакета MS Excel. 4. Анализ чувствительности решения к изменению параметров с использованием сценариев. 5. Составление отчёта по лабораторной работе, в котором представляется • формулировка индивидуального задания • математическая модель и пояснение к её построению • снимок экрана монитора, содержащий табличную модель задачи, снимки отчетов по результатам, устойчивости и пределам, а также снимок отчета по сценариям с содержательными пояснениями к ним • выводы по лабораторной работе. Теория Процесс принятия управленческого решения можно представить как последовательность выполнения следующих действий (этапов выработки решения. I. Анализ ситуации и формализация исходной задачи. На этом этапе надо просто четко сформулировать задачу, понять и сформулировать цели, которые хочется достичь при решении задачи. Другими словами, надо поставить задачу, четко определить цели, возможные решения и факторы, влияющие на решение задачи. Часто результат этого этапа представляют в виде формальной модели задачи (в условии задачи заданы в текстовой форме на естественном языке, где были бы собраны воедино цели, решения и факторы и где бы присутствовала основа для формализации отношений между ними. II. Построение математической модели, те. перевод формальной текстовой модели, построенной на предыдущем этапе, на язык математических отношений. III. Анализ математической модели и получение математического решения задачи. На этом этапе анализируется построенная математическая модель, проверяется адекватность модели и находится решение математической задачи, вытекающей из этой модели. Для решения математической задачи используется ПЭВМ. Для ее использования предварительно строится компьютерная модель задачи. Обычно этот этап наиболее простой из всех этапов процесса принятия решения, поскольку здесь, как правило, используются известные и апробированные алгоритмы решения математических задач. IV. Анализ математического решения проблемы и формирование управленческого решения. На этом этапе анализируется полученное математическое решение (выполняется так называемый анализ чувствительности, и затем на основе этого математического решения формируются рекомендации для управленческого решения. После выполнения этих этапов моделирования, собственно и следует этап реализации принятого решения. I. Рассмотрим первый этап процесса принятия решения анализ проблемы и формализация исходной проблемы. Этот этап можно рассматривать как первую стадию перехода от реального мира к компьютерному представлению проблемы. На данном этапе надо четко сформулировать свою задачу, понять и сформулировать цели, которые хочется достичь входе решения задачи. Другими словами, надо четко поставить задачу. Поэтому на данном этапе на простом русском языке надо ♦ сформулировать задачу, по возможности максимально четко ♦ сформулировать цели, которые должны быть достигнуты в результате реализации найденного решения ♦ указать, что считать решением задачи (решение должно гарантировать достижение целей ♦ выявить и описать возможности достижения целей ♦ выявить и описать факторы, от которых может зависеть решение задачи ♦ выявить и описать ограничения, препятствующие достижению целей ♦ описать возможные альтернативные способы решения задачи. Эти пункты и составляют формальную модель задачи. Таким образом, формальная модель — это просто четкое описание вашей конкретной задачи, в котором необходимо выделить перечисленные пункты. 2 Пусть некий лакокрасочный завод Олимп, в связи с изменившейся конъюнктурой рынка хочет разработать новый производственный план для выпуска краски типов Аи Б, не трогая пока производство другой продукции. Допустим, что Олимп имеет месячный цикл производства. Таким образом, нужно определить, сколько в месяц следует производить краски типа Аи сколько — типа Б. Ответ вроде бы простой чем больше, тем лучше, конечно, с учетом производственных возможностей. Итак, вот первая цель — увеличить до максимума производство как продукции Атаки продукции Б. Допустим, производственные мощности позволяют выпускать в месяц суммарно 500 т краски всех типов. Вот появилось первое ограничение — общее количество краски типов Аи Б не должно превышать 500 т. Как видно, первую цель достичь можно, однако задача остается плохо поставленной, поскольку дает неоднозначное решение. Поэтому вспомним, что всякое производство должно приносить прибыль. Теперь можно сформулировать вторую цель — производственный план должен приносить максимальную прибыль. Пусть одна тонна краски А приносит в среднем 2000 руб. прибыли, а одна тонна краски Б — 2500 руб. Здесь величины удельной прибыли те. прибыли на одну тонну краски) являются факторами, которые влияют наконечную цель. На этом шаге мы сделали огромное упрощение реальной ситуации, т. кудельная прибыль любого производимого изделия зависит от многих факторов (конъюнктуры рынка, стоимости исходных материалов, себестоимости производства, уровня рентабельности и т. дине является величиной постоянной даже на протяжении относительно небольшого временного промежутка. Тем более сложно предсказать и трудоемко подсчитать ее значение на будущий более-менее продолжительный период времени. Можно только оценить будущую удельную прибыль, да и то с определенной степенью точности. Пусть в нашем примере получены оценки будущей удельной прибыли производства краски типа А от 1500 до 2300 руб, а краски типа Бот до 3000 руб. Приведенные выше величины удельных прибылей 2000 и 2500 руб. являются наиболее вероятными ожидаемыми значениями. Далее именно эти величины примем за значения удельных прибылей, а возможные последствия от их неточного задания рассмотрим при проведении анализа полученного решения. Очевидно, что для достижения второй цели надо производить только краску типа Б и забыть окраске типа А. Однако отдел маркетинга требует, чтобы краски типа А производилось не менее 200 т в месяц, поскольку есть договоры на такое количество, а краску типа Б нельзя производить болеет, поскольку большее количество трудно реализовать. Итак, имеем еще два ограничения произведенное количество краски А должно быть не меньше 200 та краски Б — не болеет. При таких ограничениях даже начальник производства составит план надо производить 350 т краски Аи т краски Б. Этот план учитывает только ограничения по производственным мощностями маркетинговые ограничения. Но для производства любой продукции нужны еще исходные материалы. Пусть на изготовление красок Аи Б необходимо сырье трех видов согласно следующей таблице. Краска А, кг Краска Б, кг Месячный запас, т Сырье 1 50 100 50 Сырье 2 70 80 30 Сырье 3 40 70 25 В этой таблице показано, сколько и какого сырья необходимо для производства одной тонны краски Аи одной тонны краски Б, а также величины месячных запасов этого сырья. Очевидно, что общее количество сырья, используемого для производства краски, не должно превышать их месячные запасы. Таким образом, имеем еще три ограничения — по одному для каждого типа сырья. С учетом этих ограничений производственный план на пальцах уже не подсчитаешь. Здесь сделано еще одно существенное упрощение реальной ситуации. Реальный процесс производства чего бы тони было зависит не только от наличия исходных материалов, необходимых для создания конечного продукта, но и от многих других факторов наличия достаточных производственных мощностей, наличия рабочей силы, периодичности поступления исходных материалов, качества этих материалов и т.д. Здесь эти факторы отброшены, оставлены только ограничения на сырье трех видов. При этом сделано еще одно неявное допущение, что другие компоненты, необходимые для производства краски, имеются в достаточном количестве и не влияют на объемы производства. Итак, что же мы имеем после небольшого анализа задачи. ♦ Постановка задачи разработать производственный план, который максимизировал бы прибыль с учетом всех видов представленных ограничений. ♦ Цель максимизировать прибыль. ♦ Решение количество тонн краски Аи Б, производимых в месяц. ♦ Факторы, от которых зависит решение значения удельной прибыли каждого типа краски, предельное число производимой краски, предельные числа производимых красок типов Аи Б (маркетинговые ограничения, количества сырья (необходимых для производства одной тонны краски, значения запасов сырья (всего 14 факторов. ♦ Факторы, влияющие на прибыль все перечисленные факторы, кроме значений количества сырья, необходимого для производства одной тонны краски. (Считаем, что на рецептуру красок мы влиять не можем) ♦ Ограничения на предельное общее количество производимой краски, на предельные количества производимых красок Аи Б в отдельности, на предельные количества используемого сырья (всего 6 ограничений. Мы выделили факторы, влияющие на прибыль отдельно, чтобы в дальнейшем провести анализ чувствительности решения именно по этим факторам. И еще одно замечание при такой размытой постановке исходной задачи можно сформулировать много разных целей. Например, можно составить производственный план, который бы минимизировал себестоимость продукции. Можно сформулировать более сложные цели (что обычно имеет место в реальных ситуациях, например, максимизировать прибыль и одновременно минимизировать использование каких-то исходных материалов, которые являются дорогими или дефицитными. При этом в зависимости от сформулированных целей могут выделяться разные факторы, влияющие на эти 3 цели, и могут формироваться разные ограничения. В нашем примере мы ограничимся сформулированной целью максимизации прибыли. II. Построение математической модели означает перевод формальной модели, построенной на предыдущем этапе, на четкий язык математических отношений. Математическая модель должна содержать три основных компонента. 1. Переменные, значения которых необходимо вычислить (это переменные решения из формальной модели. 2. Целевая функция — это цель, записанная математически в виде функции от переменных. Обязательно указывается, что необходимо сделать с этой функцией для решения задачи найти ее максимум, минимум или конкретное заданное значение. 3. Ограничения — записанные математически ограничения из формальной модели. Если определены переменные, то построение целевой функции и ограничений обычно не вызывает затруднений, поскольку на предыдущем этане и цель и ограничения уже формулировались с привязкой к переменным решения. В нашем примере обозначим через хи х переменные, которые определяют месячные объемы производства краски (в тоннах) типа Аи Б соответственно. Напомним, что 1 тонна краски А приносит прибыль 2000 руб, а 1 тонна краски Б — 2500 руб. Тогда суммарная прибыль z при производстве х тонн краски Аи х тонн краски Б составит z = х + х (руб) Это и есть целевая функция, которую необходимо максимизировать. Теперь запишем ограничения. Первое ограничение говорит о том, что суммарный объем производства краски обоих типов не должен превышать 500 т. Это запишется так х + х. Маркетинговые ограничения записываются просто хи х. Теперь надо записать ограничения на сырье. Напомним, что сырья 1 на производство 1 т краски А расходуется 0,05 т (50 кг) и 0,1 т (100 кг) на производство 1 т краски Б. Таким образом, всего на производство x1, тонн краски Аи тонн краски Б потребуется х + х тонн сырья 1. Эта величина не должна превышать 50 т. Отсюда получаем ограничение х + х 50. Подобным способом получаем еще два ограничения на сырье 2 и сырье 3: 0,07*x1 + 0,08*x2 30 и 0,04*x1 + 0,07*x2 25. Еще одно неявное ограничение состоит в том, что переменные хи х должны быть неотрицательными (если не вдаваться в мистику, то отрицательные объемы производства физически просто невозможны. Это ограничение называется условием не отрицательности переменных и записывается так хи х 0. Однако заметим, что условие не отрицательности для переменной х здесь излишне, поскольку имеем более сильное ограничение х 200. Поэтому неравенство х 0 исключаем из списка ограничений. Обратите особое внимание на то, что размерности всех переменных и параметров должны быть согласованы. Поэтому в нашем примере удельные расходы сырья переведены из килограммов в тонны, поскольку переменные измеряются в тоннах. Обычно ограничение записывают таким образом, чтобы в левой части неравенства находилось выражение с переменными, а в правой части неравенства — только числа. Тогда левую часть неравенства называют функцией ограничения. Окончательно математическая модель нашей задачи запишется следующим образом максимизировать z = х + х при выполнении ограничений х + х, х 200, х, х + х 50, 0,07*x1 + 0,08*x2 30, 0,04*x1 + 0,07*x2 25, х 0. Любое решение (те. пара значений переменных хи х, удовлетворяющее всем ограничениям модели, называется допустимым. В нашем примере решение хи х = 150 будет допустимым, поскольку не нарушает ни одного ограничения, включая условия не отрицательности. Чтобы убедиться в этом, надо подставить значениях их в левые части ограничений, выполнить вычисления и проверить, что ни одно неравенство не нарушается. Значение целевой функции при этом решении будет равно z = 2000*200 + 2500*150 = 775 000 (руб. Итак, математическая модель построена, осталось найти решение модели. Для выполнения этого дела мы привлечем программу электронных таблица еще точнее — надстройку Поиск решения Прежде чем начать выполнение каких-либо вычислений в Excel, надо перевести нашу построенную математическую модель на рабочий лист Excel. Для этого следует определить, в каких ячейках будут располагаться переменные решения, записать в нужные ячейки формулы, по которым будут вычисляться целевая функция и функции ограничений (левые части ограничений, надо записать в отдельные ячейки значения правых частей ограничений. Всю эту совокупность значений и формул, записанных на рабочем листе, назовем моделью представления задачи в Excel. Для оптимизации моделей представления задачи вне существует общепринятых канонов их построения. Вот некоторые рекомендации, которые облегчат дальнейшее применение средства Поиск решения. ♦ Значения переменных располагаются в отдельных ячейках и группируются в отдельный блок ячеек. ♦ Каждому ограничению отводится отдельная строка или столбец таблицы. Ограничения группируются в отдельный блок ячеек. ♦ Желательно, чтобы ячейки, содержащие переменные и значение целевой функции, а также все ограничения, имели заголовки. 4 ♦ Коэффициенты целевой функции должны храниться в отдельной строке, располагаясь непосредственно под или над соответствующими переменными формула для вычисления целевой функции должна находиться в соседней ячейке. ♦ В каждой строке ограничений за ячейками, содержащими коэффициенты данного ограничения, следует ячейка, в которую записывается вычисленное значение функции ограничения (значение левой части ограничения. За ней может следовать ячейка, в которой стоит соответствующий знак неравенства или равенства ограничения, а затем ячейка, содержащая значение правой части ограничения. Желательно, чтобы правые части ограничений были константами, а не формулами. Дополнительно можно иметь ячейку, в которой вычислена разность между значениями левой и правой частей неравенства. ♦ Условия не отрицательности переменных решения необязательно включать в модель представления задачи в Excel. Как правило, они опускаются и указываются непосредственно в диалоговом окне средства Поиск решения. В результате выполнения этих рекомендаций все основные коэффициенты модели содержатся в отдельных ячейках, поэтому их легко изменять, не меняя формул модели. Благодаря группированию упрощается работа со средством Поиск решения, поскольку для указания переменных или ограничений можно использовать диапазоны ячеек, те. задавать переменные и ограничения группой, а не по отдельности. Наличие заголовков сделает понятной эту модель представления задачи вне только вам, но и другим людям. Пример модели представления задачи в Excel для нашего варианта показан на рис. 1. Здесь значения переменных решения записаны в ячейках В и С с соответствующими заголовками в ячейках В и С. Вначале значения переменных произвольные. Коэффициенты, стоящие перед переменными в формуле целевой функции, записаны в ячейки В и С, а само значение целевой функции вычисляется в ячейке D8 (соответствующие заголовки записаны над этими ячейками. Ниже в диапазоне В11:С17 записаны коэффициенты функций ограничений, в диапазоне D11:D17 вычисляются значения левых частей ограничений, в диапазоне ЕЕ записаны знаки неравенств ограничений, а в диапазоне Fl1:F17 — значения правых частей ограничений. Наконец, внизу в строке 20 под левым заголовком Решение еще раз повторены значения переменных и целевой функции. Рис. 1. Модель представления задачи в Excel для вычисления производственного плана Формулы, по которым выполняются все вычисления на данном рабочем листе, показаны на рис. 2. Для вычисления линейных функций подходит функция СУММПРОИЗВ(массив1;массив2), которая суммирует попарные произведения элементов двух диапазонов, заданных аргументами функции массив и массив. Например, формула =СУММПРОИЗВ($В$4:$С$4;В8:С8), вычисляющая значение целевой функции в ячейке D8, эквивалентна такой формуле =В4*В8+С4*С8. Абсолютные ссылки $В$4:$С$4 на диапазон В4:С4, содержащий значения переменных хи х2,сделаны для того, чтобы можно было скопировать эту формулу из ячейки D8 в ячейки D11:D17 для вычисления левых частей неравенств, где также участвуют значения переменных решения. Рис. 2. Задание формул модели представления задачи в Excel 5 Левые части ограничений, поскольку это линейные функции, также вычисляются с помощью функции |