Двойственная задача
Если же есть реальный лимит на численность рабочих данной профессии, то соответствующее ограничение должно появиться среди неравенств, описывающих множества допустимых планов. Наконец, оборудование в среднесрочном плане можно рассматривать как фиксированный ресурс, объем которого не может меняться при варьировании плана.
Таким образом, получаем, что обязательно следует учитывать ограничения на оборудование и, возможно, следует учитывать ограничения на некоторые трудовые ресурсы. В нашем примере учтены только ограничения на оборудование.
Объем оборудования оценивается как мощность. (Этот вопрос рассмотрен в главе 4.) Ограничение но мощности формулируется следующим образом:
плановая потребность в мощности плановая наличная мощность.
Плановая потребность в мощности на производственную программу была рассчитана ранее:
пм,= ? нв./х,,
j
где і номер (шифр, код) группы взаимозаменяемого оборудования или профессии основных производственных рабочих на ручных операциях;
j номер (шифр, код) изделия;
тг потребность в мощности номер і;
нвц норма времени і-ой группы взаимозаменяемого оборудования или профессии основных производственных рабочих на ручных операциях на единицу изделия);
х( плановый объем производства изделия).
Плановая наличная мощность (плановое наличие мощности) это вектор, элементами которого являются плановые фонды времени групп взаимозаменяемого оборудования и профессий основных производственных рабочих на ручных операциях. Эти величины также были рассчитаны ранее. Таким образом, множество допустимых планов описывается системой неравенств:
ПМ, НВу * Xj НМ| ч
j
где нм( наличие мощности.
Требуется ввести еще одну группу ограничений:
х. 0.
і
Это значит, что продукция производится, а не покупается.
В качестве критерия оптимальности выбирается один из итоговых показателей деятельности предприятия. Говорить об оптимальности плана без указания конкретного критерия оптимальности бессмысленно так же бессмысленно, как говорить: Самый оптимальный план или Наиболее оптимальный план. По определению оптимальный план это план, наилучший из допустимых. Множество допустимых планов описано выше.
Чтобы поставить задачу оптимального планирования, надо указать конкретный критерий оптимальности, или целевую функцию. (Целевая функция и критерий оптимальности синонимы.) Обычно в качестве целевой функции (или критерия оптимальности) используют прибыль от реализации продукции. Возможны альтернативы: объем реализации, чистая прибыль, балансовая прибыль, рентабельность продукции, рентабельность капитала.
Не оспаривая, что в определенных условиях один из перечисленных выше показателей наиболее адекватен конкретной ситуации, мы в примере будем использовать балансовую прибыль. Сделаем только одно замечание. На наш взгляд, использование в оптимальном планировании относительных величин в качестве критерия оптимальности, таких как рентабельность, нецелесообразно: относительной величиной сыт не будешь. Реализация, прибыль это показатели эффекта, который распределяется по различным направлениям.
Рентабельность это эффективность. Сама по себе она не распределяется, хотя может быть очень полезна для целей экономического анализа.
Балансовая прибыль равна:
^рсал ^ннсрсдл’
где ПГал балансовая прибыль;
Ир™ ~ прибыль от реализации продукции и услуг;
П1иерв|Л прибыль от внереализационных операций.
Прибыль от внереализационных операций это полученные дивиденды, прибыль от долевого участия в других предприятиях, полученные штрафы, пени и санкции, полученные арендные платежи (за вычетом расходов по содержанию сдаваемого в аренду имущества) и т. п. Она не зависит от объема производства и при определении оптимального плана производства может быть опущена. (Тогда целевой функцией становится прибыль от реализации продукции.) В развернутой форме балансовая прибыль записывается как
п6ш = *х; ~ ?z, * *, - znoct+n.HqKM
I j
или
Пбая = ?(Uj -Zj)!*xj - Zn0CI + Пвнсрсш
где j код изделия;
^ цена j-го изделия;
г, прямые затраты на производство единицы j-ro изделия;
Xj объем производства j-ro изделия;
Zjioct постоянные затраты.
Поскольку постоянные затраты не зависят от объема производства, они также могут быть опущены при определении оптимального плана производства.
Величина ?(ц. z.) * х; называется маргинальной (предельной) прибылью, а величины (ц z;) удельными маргинальными прибылями. Слово маргинальная, т. е. предельная, появляется потому, что в экономической литературе производные от функций принято называть предельными (маргинальными) величинами. Если взять от маргинальной прибыли производную по объему производства, получится удельная маргинальная прибыль соответствующего изделия:
^-?(Uj-Zj)*Xj=Uj-zJ-
Теперь можно записать задачу оптимального планирования:
Найти Xj такие, что
тахП^, =^(uJ-zj)*xj-Z„0C1+n^4)ea„,
X
ПМІ HBii*xj -нмі
І
х. 0. j
Получилась задача линейного программирования. Линейного потому что и целевая функция, и ограничения линейно зависят от искомых переменных х.. Слово программирование также появилось не случайно. К составлению программ для ЭВМ это слово в данном случае имеет косвенное отношение (чтобы не сказать, никакого отношения не имеет).
Задачи линейного программирования можно решать и без применения ЭВМ. Линейное программирование это просто вычислительный метод для решения определенного класса задач и теоремы о свойствах решений этих задач. Линейное программирование было изобретено Л. В. Канторовичем в 30-х гг. XX в., а затем в 40-х гг. заново (и независимо от Л. В. Канторовича) открыто американским математиком Дж. ван Данцигом.
Заслуга Л. В. Канторовича никем не оспаривалась, и впоследствии ему была присуждена Нобелевская премия по экономике за изобретение этого метода. Но широкую известность и популярность линейное программирование приобрело благодаря усилиям американских математиков и экономистов. В 40-х гг. слово планирование ассоциировалось на Западе с коммунизмом и было неприемлемо.
Его и заменили словом программирование.
Алгоритмы решения задачи линейного программирования довольно сложны. Достаточно сказать, что сформулирована эта задача была еще в XVIII в. Г. Монжем, но более 150 лет не существовало общего способа решения таких задач.
В настоящее время задача линейного программирования практически любой разумной размерности может решаться средствами Excel. Для этого используется надстройка ПОИСК РЕШЕНИЯ
Прежде всего надо подготовить лист Excel для размещения данных. К сожалению, надстройка ПОИСК РЕШЕНИЯ требует, чтобы целевая функция, искомые переменные и левая часть ограничений располагались на одном листе.
Поэтому задача может быть решена на листе Произв в книге Показатели.
Но, чтобы не испортить ранее полученное неоптимальное решение, книга Показатели скопирована в книгу ПоказателиОпт (вместе со всеми формулами и расчетами, которые есть в этой книге). Далее пало открыть команду Сервис. Появится выпадающее меню, как это показано на рис.
10.1. В этом меню надо выбрать ПОИСК РЕШЕНИЯ. Если этой надстройки не окажется в выпадающем меню Сервис, то это значит, что она не установлена. Надо ее установить.
В стандартном комплекте Excel надстройка ПОИСК РЕШЕНИЯ есть.
На рис. 10.2 показан результат вызова надстройки ПОИСК РЕШЕНИЯ и Заполнения ее окон. В окне Установить целевую ячейку указывается адрес ячейки, в которой вычислена балансовая прибыль. В нашем примере это ячейка G9.
В окне Равной: следует установить максимальному значению, прибыль максимизируется, а не минимизируется. Данные в окно Ограничения вводятся следующим образом. Надо щелкнуть мышью в самой верхней части окна Ограничения п нажать кнопку Добавить.
Откроется диалоговое окно Добавление ограничений, как показано на рис. 10.3.
Рис. 10.3. Добавление ограничений
Рис. 10.4. Диалог Параметры поиска решений
В среднем окне установить знак неравенства . (При открытии окна требуемый знак уже установлен.) В окно Ограничение нужно ввести адреса массива наличия мощности (правые части ограничений). В нашем примере это ячейки L6:L9. Затем нажать ОК.
Снова появится диалог Поиск решения, как на рис. 10.2.
После этого надо нажать клавишу Параметры. Появится диалог Параметры поиска решений, как показано на рис.
10.4.
Здесь надо поставить птички в окнах Линейная модель и Неотрицательные значения, после чего нажать ОК. Снова появится окно Поиск решения. Для работы этой надстройки все готово.
Остается только нажать клавишу Выполнить.
Результаты работы надстройки сообщаются в диалоге Результаты поиска решения (рис. 10.5).
Если решение найдено, нажать ОК, в противном случае искать ошибку.
Балансовый методи оптимальное планирование
Вплоть до главы 10 речь шла о построении плана балансовым методом. Балансовый метод планирования иногда противопоставляют оптимальному планированию.
Это неверно.
Рассмотрим результаты построения плана балансовым методом и оптимального планирования в нашем примере. Прибыль, вычисленная балансовым методом, равна 91 739 тыс. р„ а оптимальная прибыль 81 758 тыс. р. Получается парадоксальная ситуация: оптимальный план менее эффективен, чем план, построенный балансовым методом!
В действительности парадокса нет. Чтобы в этом убедиться, надо посмотреть, какие ресурсы используют тот и другой план.
Потребность в мощности для обоих планов показана в табл. 10.1.
Потребность в мощности в оптимальном плане не больше, чем наличие мощности. Ограничения по мощности выполняются строго.
| Таблица 10.1 | |||||||||||||||||||||||||
|
На практике такое превышение вполне допустимо этот вопрос уже рассматривался в п. 4.2, когда обсуждалась балансировка мощности. В балансовом методе ограничения мягче, их можно немного нарушить. Но в результате приведенные выше планы оказываются несопоставимы: они рассчитаны как бы при разном наличии мощности. Балансовый план в табл. 10.1 просто-напросто недопустим. Этим и объясняется то, что он дает большую прибыль, чем оптимальный план. Если уравнять наличие мощности в обоих способах планирования, результат получится совсем другой. Оптимальная прибыль равна 96 924 тыс. р., когда наличие мощности равно потребности в ней в балансовом методе планирования.
Итак, ограничения в оптимальном планировании более жесткие, чем в балансовом методе. Отметим еще некоторые особенности оптимального планирования. Обычно (не обязательно, но почти всегда) количество ненулевых решений (ненулевых объемов выпуска) равно наименьшему из двух чисел: числу ограничений или числу наименований продукции. В нашем примере прибыль равна 96 924 тыс. р., если объемы выпуска таковы, как в табл. 10.2.
| Таблица 10.2 | |||||||||
|
Двойственная задача
Каждой прямой задаче оптимального планирования соответствует двойственная задача. Двойственность в математической экономике появляется очень естественно, пожалуй, более естественно, чем в физике.
Поясним это на примере.
Возьмем матрицу норм расхода материалов в нашем сквозном примере:
| 1,5 | 1,8 |
| 9 | 7 |
| 6 | 6 |
| 3,5 | 3,5 |
| 1 | 1 |
| 0,4 | 0,6 |
| 1,5 | 1,8 | '330 ' | |||
| 9 | 7 | 1600 | |||
| 6 | 6 | * | '100) | 1200 | |
| 3,5 | 3,5 | 100 | 700 | ||
| 1 | 1 | 200 | |||
| 0,4 | 0,6 | 100 / |
А что произойдет, если оператор будет действовать справа? Умножить матрицу норм расхода материалов справа на тот же вектор объема производства в данном случае просто невозможно не хватит элементов этого вектора.
Вектор-сомножитель должен иметь столько же элементов, сколько строк в матрице норм расхода материалов. Каждая строка этой матрицы соответствует определенному материалу.
Подходящим вектором оказывается вектор цен на материалы: (24 37 16 9 750 26). Если этот вектор умножить на матрицу норм расхода материалов (так, что матрица расположена справа), получится вектор стоимости материалов на одно изделие:
|
= (1256,9 1195,3). |
(24 37 16 9 750 26)*
Таким образом получается, что каждой матрице-оператору соответствуют две операции правая и левая, причем обе имеют экономический смысл. Именно в этом и состоит содержательная идея двойственности.
В задаче оптимального планирования матрица норм времени умножалась слева на вектор объема выпуска, причем объем выпуска был искомым вектором. В двойственной задаче матрица норм времени умножается справа на неизвестный вектор. Симметрия присутствует и при записи целевой функции и ограничений. Обозначим искомый вектор (он называется вектором двойственных оценок, или вектором множителей Лагранжа) как у. Каждому ресурсу, т. е. каждой группе взаимозаменяемого оборудования, соответствует свой элемент этого вектора. Экономический смысл этого вектора будет определен позже. Двойственная задача к задаче оптимального планирования записывается так:
тіп?уі *HMj,
у ^
ХУ‘*нвч-(Ц)-2))’
Уі0.
Здесь по-прежнему і номер (шифр, код) группы взаимозаменяемого оборудования или профессии основных производственных рабочих на ручных операциях;
Здесь по-прежнему і номер (шифр, код) группы взаимозаменяемого оборудования или профессии основных производственных рабочих на ручных операциях;
j номер (шифр, код) изделия;
пм. потребность в мощности номер і;
нв.. норма времени і-й группы взаимозаменяемого оборудования или профессии основных производственных рабочих на ручных операциях на единицу изделия);
ц. цена j-ro изделия;
z. прямые затраты на производство единицы j-ro изделия.
Для решения двойственной задачи в Excel используется надстройка ПОИСК РЕШЕНИЯ. Рассмотрим процесс решения по шагам.
Шаг 1. Подготовка листа для решения двойственной задачи, как показано на рис. 10.6. Для решения двойственной задачи использован лист Произв в книге ПоказателиОпт. В ячейки, отведенные под двойственные оценки, записываются нули. В табл. 10.3 показаны формулы, введенные в ячейки на этом шаге.
Рис. 10.6. Подготовка листа для решения двойственной задачи
Двойственную задачу необязательно решать на том же листе, на котором решена задача оптимального планирования. Однако обязательно, чтобы сами двойственные оценки, целевая функция двойственной задачи и вычисленные левые части ограничений располагались на одном листе.
Шаг 2. Вычисление значения целевой функции. В ячейку L24 вводится формула: =МУМНОЖ (J18:M18;L6:L9)/1000. Вектор Л 8 : Ml 8 -это вектор двойственных оценок, в ячейках L6: L9 хранится массив
| Таблица 10.3 | ||||||||||
|
наличия мощности. Делить произведение двойственных оценок на наличие мощности надо потому, что целевая функция измеряется в тысячах рублей.
Шаг 3. Вычисляются левые части ограничений. Для этого используется функция МУМНОЖ. В ячейки К22 : L22 введена формула
=МУМНОЖ(Л8:Ml 8;'С:\ПЛАН\[Нормы и цены.хіs]НорВр' !$ С$7:$ DS10)/100.
Разумеется, адреса массивов в окно функции МУМНОЖ введены с помощью мыши. Поскольку результат операции массив, надо нажимать клавишу Enter при нажатых клавишах Shift и Ctrl.
Шаг 4. В меню Сервис выбирается надстройка ПОИСК РЕШЕНИЯ. Окна надстройки заполняются так, как показано на рис. 10.7.
В окне Установить целевую ячейку указать адрес ячейки, в которой вычисляется целевая функция. В нашем примере это L24. В двойственной задаче целевая функция минимизируется. Поэтому надо установитъ: Рапной минимальному значению. В окне Изменяя ячейки указать адрес массива двойственных оценок. В нашем случае это SJS18 : $м$ 18. В окне Ограничения (с помощью клавиши Добавить) записать ограничения: К22 :L22 К20 : L20.
В диалоге Параметры установить птички в окнах Линейная модель и Неотрицательные значения. После этого выполнить ПОИСК РЕШЕНИЯ. Результат решения двойственной задачи показан на рис. 10.8.
Двойственные оценки ресурсов имеют важный экономический смысл. Они являются предельными эффективностями ресурсов. Это значит, что двойственная оценка некоторого ресурса равна приросту прибыли при увеличении объема этого ресурса на единицу. В нашем примере один дополнительный станко-ч станка РТ2505 увеличит оптимальную прибыль на 4845 р. в год. В то же время только эта группа оборудования является лимитирующей. По остальным группам оборудования наличная мощность используется не полностью. Увеличение наличной мощности этих групп оборудования не приведет к росту прибыли. Их двойственные оценки равны пулю. Двойственные оценки дают ясное представление о том, насколько важен тот или иной ресурс.
Оптимальные значения целевых функций прямой и двойственной задач должны совпадать. Это одна из теорем линейного программирования. Такое свойство оптимального решения задач линейного программирования имеет смысл использовать для проверки правильности постановки и решения задачи оптимального планирования.
На первый взгляд может показаться, что задача в нашем примере решена неверно. Действительно, оптимальное значение целевой функции двойственной задачи равно 86 296, а оптимальная прибыль 81 758. Дело в том, что в таблице План производства и основные показатели в строке Прибыль указана балансовая прибыль, которая включает не только прибыль от реализации продукции, но и дивиденды, и доходы по депозитам, и прибыль от прочих операций. Прибыль от реализации равна 519 474 - 438 357 = 81 116 тыс. р. (объем реализации минус себестоимость). Эта величина вычислена в ячейке М2 б, в которую введена формула: =G7 - G8. В ячейке L26 вычислено модифицированное значение целевой функции двойственной задачи по формуле =L24 -L25 (из целевой функции вычитаются постоянные затраты). Значения в ячейках L26 и М26 совпадают, т. е. задача решена правильно.
ИСХОДНЫЕ ДАННЫЕ ДЛЯ ПРИМЕРА
В этом приложении приведены исходные данные для примера, который описан в главе 1, и формы документов. Таблицы формы документов не всегда помещаются на экране компьютера, поэтому они вынесены в приложение. Пользователь может, конечно, изменить таблицы но своему усмотрению.
В этом заключается одно из преимуществ самостоятельной разработки автоматизированной системы планирования: формы документов можно изменять в процессе работы.
| Таблица П1.1 | |||||||||||||||||||||||||||||||||||||||||||||||||
|
