ЭМиКМ (МУ)

11

абсцисс, полагая в (1.8) х2=0: x1(0) =14,4/0,06=240. Этим же способом строятся

прямые, соответствующие ограничениям (1.9) и (1.10).

В результате получается шестиугольник, вершины которого обозначены цифрами от 0 до 5. Этот шестиугольник, включая ограничивающие его линии, и есть область допустимых решений рассматриваемой задачи – симплекс. Любая точка с соответствующими ей координатами х1 и х2, лежащая внутри или на границе симплекса, удовлетворяет системе ограничений (1.7) – (1.11). Теперь необходимо из всех точек найти ту, в которой критерий эффективности (1.6) имеет наибольшее из всех возможных значений. Строится прямая, соответствующая (1.6). Для этого правой части (1.6) дается некоторое конкретное значение, например, в рассматриваемом случае – 400. Тогда целевая функция пройдет через точки х10 = 108,108 и х20 = 100 (положение I на рис. 1.1). Эта прямая проходит под углом α к оси абсцисс, который определяется

соотношением прибылей от обоих видов продукции

tgα = 3,7/4 = 0,925. Если изменять величины прибылей (одной или обеих), угол наклона α также будет меняться. Если полученную прямую I перемещать параллельно самой себе в сторону увеличения х1 и х2 (это соответствует увеличению правой части), то она в итоге займет положение II, в котором имеет с симплексом единственную общую точку (точку 3). Именно эта точка с координатами х1=90 и х2=90 доставляет максимальное значение критерию эффективности. Суммарная прибыль в этой точке достигает максимального значения 90×3,7+90×4=693 р.

В табл. 1.2 приведены координаты всех точек – вершин симплекса, полученные из рис. 1.1, а также значения критерия эффективности в этих точках, вычисленные по формуле (1.6).

Таблица 1.2

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

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

12

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

Таблица 1.3

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

Впроцессе выполнения принятой производственной программы (плана)

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

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

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

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

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

Ограничения линейной модели для решения задачи анализа чувствительности классифицируются следующим образом:

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

13

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

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

1.Анализ сокращения или увеличения ресурсов.

2.Анализ изменения коэффициентов ЦФ.

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

Первая задача. Рассмотрим вопрос регулирования запасов ресурсов, используемых для выполнения производственной программы. Анализ оптимального решения позволяет сделать вывод, что связывающими ограничениями являются ограничения 2 и 3, соответственно, дефицитными ресурсами будут: пиломатериалы и оборудование. Согласно табл. 1.3 они

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

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

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

В нашем случае при прохождении прямой 3 (оборудование) через точку В ограничение 3 становится избыточным и возникает новый симплекс с вершинами 0–1–2–3–В–5, в котором оптимальной будет точка В, а связывающими ограничениями становятся 4 (древплита) и 2 (пиломатериалы).

Аналогично, увеличение объема ресурса 2 (пиломатериалы) целе- сообразно до точки А, в которой образуется новый симплекс 0–1–А–4–5, а связывающими ограничениями становятся 1 (ткань) и 3 (оборудование).

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

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

2)подставить координаты (х1; х2) в левую часть соответствующего ограничения.

50 3,73.x7x1+41+4x2x®2®maxmax

4

Координаты точки В (130;66) находятся путем решения системы уравнений прямых 4 и 2. При подстановке полученных значений в левую часть ограничения 3 получается допустимый объем ресурса оборудование равный 914. Дальнейшее увеличение не изменит симплекса и не приведет к другому оптимальному решению. Полная прибыль в новой оптимальной точке будет равна 745 р. Аналогично, рассчитываются: координаты точки А (66;120), максимально допустимый объем ресурса пиломатериалы (15,96) и полная прибыль (724 р.).

Ограничения 1 и 4 являются не связывающими, а соответствующие им ресурсы недефицитными. С экономической точки зрения это означает, что в

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

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

15

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

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

В ограничение 1 (ткань) подставляются координаты точки 3, получается новое значение 297 р. Аналогично проводится исследование возможного снижения запаса древплиты.

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

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

Анализируя полученные результаты, ЛПР может сделать вывод, что при

наличии средств дополнительные вложения следует направить на увеличение объема ресурса 2, а лишь затем на увеличение ресурса 3.

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

Вторая задача. Рассмотрим вопрос о возможности снижения

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

16

себестоимости. Таким образом, если меняется себестоимость продукции, то при неизменной цене меняется прибыль и, следовательно, угол наклона α. При этом пределы изменения угла α, обеспечивающие оптимальность выбранного плана, таковы, что положение прямой II (см. рис. 1.1), соответствующей критерию оптимальности, заключено между прямыми 2–3 и 3–4, соответствующими ограничениям на пиломатериалы и оборудование.

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

Итак, угол α может меняться в пределах α2 £ α £ α3, где α2 – угол наклона прямой, соответствующей ограничению на пиломатериалы, а α3 – угол прямой, соответствующей ограничению на оборудование. Как известно, тангенс угла

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

k2 = tgα2 = 0,06/ 0,1 = 0,6,

k3 = tgα3 = 5/ 4 =1,25,

kz = tgα = p1 / p2 = 3,7 / 4 = 0,925,

таким образом

Подставляя числа, получим 0,6£0,925£1,25. Снижая себестоимость шкафа на p1, тем самым можно на p1 увеличить прибыль p1. Так как значение p1 находится в числителе отношения, определяющего значение tgα, то увеличение прибыли на шкаф приведет к увеличению угла наклона α прямой, соответствующей критерию эффективности. Как следует из (1.12), предельное увеличение значения tgα, не нарушающее условия оптимальности выбранного плана, возможно до значения k3=1,25, т.е.

где p1 = k3 p2 – p1 = 1,25×4 – 3,7 = 1,3 р.

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

17

Если снижать себестоимость кровати на p2, то tgα уменьшится. Предельное снижение себестоимости, не нарушающее условия оптимальности выбранного плана, составит

где p2 = p1/k2 – p2 = 3,7/0,6 – 4 = 2,17 р.

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

Контрольные вопросы

1.Какая система уравнений называется совместной? Определенной? Несовместной? Неопределенной?

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

3.Какие системы уравнений называются эквивалентными?

4.Какие преобразования системы уравнений приводят к эквивалентной системе?

5.Является ли умножение обоих частей уравнения на одно и то же число, отличное от нуля, эквивалентным преобразованием?

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

7.Какая система уравнений называется системой с базисом?

8.Что такое базисные неизвестные (переменные)?

9.Какое решение системы уравнений называется базисным?

10.Можно ли привести совместную систему линейных уравнений к эквивалентной системе уравнений? Если да, то как?

11.Что такое общая задача линейного программирования?

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

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

14.Что включает в себя математическая модель задачи линейного программирования?

15.Что такое допустимое решение задачи линейного программирования?

16.Что такое оптимальное решение задачи линейного программирования?

17.Что такое симплекс?

18

18.Какие задачи решаются при выполнении анализа чувствительности

решения?

19.Какие ресурсы называются дефицитными? Недефицитными?

ЛАБОРАТОРНАЯ РАБОТА № 2 (2 часа)

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

Содержание работы и порядок ее выполнения

Лабораторная работа включает в себя знакомство с методикой формулировки и решения задач математического программирования с использованием процедуры «Поиск решения» (Solver) табличного процессора Excel, а также практическое приложение полученных знаний для решения

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

Студент на занятии знакомится с процедурой «Поиск решения» табличного процессора Excel и использует её для формулировки и решения

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

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

Пример постановки задачи оптимизации в Excel

Рассмотрим задачу оптимального планирования выпуска продукции (лабораторная работа №1). Производственному участку поручено выпускать мебель двух видов: кровати и шкафы, на производство которых выделены сырьевые и производственные ресурсы (табл. 2.1). Требуется составить оптимальный по прибыли план выпуска продукции.

19

Обозначим искомое число шкафов через х1, а число кроватей – через х2.

Тогда математическая модель задачи запишется так

Z = 3,7x1 + 4x2 → max

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

Рис. 2.1

Ячейки С4:С5 – изменяемые ячейки, в которые записываются некоторые начальные значения (в данном примере 1). Расход ресурсов на единицу изделия помещен в ячейках D4:G5, объем ресурсов – в ячейках D7:G7, прибыль на единицу изделия – в ячейках I4:I5. Ячейка J8 выбрана в качестве целевой ячейки, содержащей формулу =СУММ(J4:J5). Она связана с изменяемыми ячейками через ячейки J4:J5, в которых содержатся формулы: =I4*С4 и =I5*С5.

Расход ресурсов (ячейки D4:G5) связан с изменяемыми ячейками формулами: =D4*C4+D5*C5, =E4*C4+E5*C5, =F4*C4+F5*C5 и =G4*C4+G5*C5,

помещенными во влияющие ячейки D8:G8 соответственно.

Задание 1. В соответствии с данными индивидуального задания лабораторной работы № 1 сформировать в ячейках листа Excel шаблон решения

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