Глава 4. оптимизационные методы экономического анализа

Глава 4. оптимизационные методы экономического анализа

4.1. Линейное программирование

4.1.1. Область применения линейного

программирования в экономическом анализе

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

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

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

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

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

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

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

4.1.2. Постановка и методика решения ассортиментной задачи симплексным методом

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

n

L(х) = X ПjXj — max,

j=i

при ограничениях

n

Ъ^Х] < b (i = l,2,...,m), dk < Xk < Dk (k < n),

xj > 0 (1, 2, n),

где — прибыль, получаемая от производства единицы продукцииj-го вида;

Xj — количество производимой продукции j-го вида;

йд — расход /'-го вида ресурса (сырья и материалов, производственной мощности, трудовых ресурсов) на единицу j-го вида продукции в процессе производства;

bi — ограничения по z'-му виду ресурса;

Dk — максимальное ограничение на объем производства k-го вида продукции;

dk — минимальный объем производства k-го вида продукции (это ограничение обычно относится к малорентабельным видам продукции, пользующимся спросом у населения).

Общее условие ассортиментной задачи представлено в виде табл. 4.1.

Количество производимого продукта обозначают через х1, х2, х3, х4, х5. В задаче некоторые Xj могут быть равны нулю. Отрицательных Xj быть не может, так как переход продукта в сырье и материалы невозможен.

В качестве примера условия задачи даны в табл. 4.2. Потребление первых видов сырья (материалов) составляет:

5х1 + 4х2 + 6х3 + 10х4 + 3х5.

Потребление сырья не может быть больше имеющегося в наличии количества сырья (материалов) данного вида, т.е. 2700 т. Рассуждая аналогично, можно выразить задачу в виде следующих неравенств:

5х1 + 4х2 + 6х3 + 10х4 + 3х5 < 2700, 3х1 + 3х2 + х3 + 2х4 + 3х5 < 1000, 4х1 + х2 + 5х3 + 4х4 + х5 < 1000, Xj > 0 (j = 1, 2, 3, 4, 5).

Необходимо определить такие Xj > 0, чтобы получить максимум прибыли:

Z(x) = 5x1 + 3x2 + 4x3 + 6x4 + 4x5 ^ max.

Неравенства обращают в равенства, добавляя дополнительные переменные:

5х1 + 4х2 + 6х3 + 10х4 + 3х5 + х6 = 2700,

3х1 + 3х2 + х3 + 2х4 + 3х5 + х7 = 1000,

4х1 + х2 + 5х3 + 4х4 + х5 + х8= 1000,

х] > 0 (j = 1, 2, ... 8),

Ь(х) = 5х1+ 3х2 + 4х3 + 6х4 + 4х5 + + 0х7 + 0х8 ^ max.

Дополнительные переменные показывают количество соответствующего неиспользованного сырья, которое может остаться на складе. Например, х6 — количество неиспользованного сырья первого вида, х7 — сырья второго вида, х8 — неиспользованная мощность предприятия. Дополнительные переменные х6, x7, х8 не способствуют увеличению прибыли, так как не участвуют в производстве, поэтому в линейной форме L(x) эти переменные записывают с коэффициентом прибыли, равным нулю.

Составляют симплексную таблицу (табл. 4.3). В столбце с. записывают нули, так как за базис принимают дополнительные переменные, которые равны соответственно 2700, 1000, 1000, т.е.:

x = ( х6; х7; х8 ) = (2700; 1000; 1000).

В столбце Xj проставляют коэффициенты при соответствующих неизвестных в уравнениях. Значение последней строки L(x) получается при вычислении разности между суммой произведений элементов столбца с. для базисных переменных на соответствующие элементы столбца Xj (j = 1, 2, 8) и значением с.в линейном функционале L(x) для данной переменной.

Для следующих столбцов:

х0 L(x) = 0 х 2700 + 0 х 1000 + 0 х 1000 = 0,

х1 L(k) = 0 х 5 + 0 х 3 + 0 х 45 = -5,

х2 1(х) = 0 х 4 + 0 х 3 + 0 х 13 = -3

и т.д.

Переменную, которая находится в колонке, выделенной жирным шрифтом (табл. 4.3), вводят в базис, так как она способствует большому увеличению прибыли. Такой переменной в данном случае является х4, у которой значение L^) = -6. Чтобы выяснить, какую переменную необходимо удалить из базиса для введения х4, находят положительные значения делением соответствующих элементов столбца х0 на элементы ключевого столбца (на нуль и на отрицательные числа ключевого столбца не делят).

Є2700 27 0

Є2 -= 500,

93 -1000 250. 3 4

Среди 9,выбирают наименьшее положительное (/ = 1, 2, 3 — номера строк). Ключевая строка показывает, что необходимо вывести переменную х8. После составления первоначальной программы приступают к следующей. В табл. 4.4 в базисе х6, х7, х4 (введена вместо х8 со значением с4 = +6). Преобразуют ключевую строку, производя деление элементов ключевой строки на главный элемент 4. Результат записывают в шестую строку табл. 4.4. Это правило можно представить в виде формулы

Элементы преобразованной ключевой строки =

Элементы ключевой строки . Главный элемент

Заполняют шестую строку табл. 4.4.

Для столбца x0: —= 250,

где 1000 — элемент столбца х0 в третьей строке;

4 — главный элемент, лежащий на пересечении третьей строки и четвертого столбца.

Для небазисных переменных следующих столбцов

для x1: 4 = 1, для x4:

для x2: — — 0,25, для x5: — — 0,25,

2 4 5 4

для x3: — — 1,25,и т.д. Остальные значения для других строк определяют по формуле

Элементы новой строки =

Ключевой „

Элементы

Элементы элемент .

= — „х преобразованной.

старой строки преобразуемой

ключевой строки

строки

Ключевой элемент преобразуемой строки лежит на пересечении преобразуемой строки и ключевого столбца (табл. 4.3). Элемент преобразованной ключевой строки берется в том же столбце (j = 1, 2, 8), для которого определяют новый элемент в новой таблице (табл. 4.4).

Заполняют четвертую строку для базисной и небазисных переменных в табл. 4.4:

для x0: 270 -101000 = 200, 4

для Ху 5-Ю-4 = -5, для x2: 4 -10-4 = 1,5, для x3: 6 -105 = -6,5,

для x5: 3 -10 4 = 0,5, для x6: 1 -10-4 = 1,

для x7: 0 -10 44 = 0,

для x8: 0 -10-4 = -2,5.

для x4: 10 Ю4 = 0,

Аналогично вычисляют пятую строку для табл. 4.4.

После выбора ключевой строки и ключевого столбца переходят к заполнению следующей симплексной таблицы (табл. 4.5). Необходимо отметить, что в ней значение линейной функции L(x) возрастает до 1500, причиной чего служит переменная x4, которая вошла в базис. Экономический смысл нового допустимого плана, приведенного в табл. 4.5, состоит в том, что по нему рекомендуется производить продукцию В4 в объеме 250 ед.

При переходе от одной симплексной таблицы к другой возможны следующие случаи:

а) если строка L(x) имеет отрицательные числа, над которыми

имеются положительные элементы, то программа требует улучшения;

б) если над отрицательными числами в строке L(x) нет положительных элементов, то max L(x) находится в бесконечности (задача

не решается);

в) если нет ни одного значения L(x) < 0, то max L(x) достигнут

(задача решена).

В табл. 4.5 в строке L(x) нет отрицательных чисел, поэтому достигнут max L(x) при x5 = 200, x4 = 200. Следовательно, если будут производить продукт В4 и В5 в объеме по 200 ед., то получат максимальную прибыль в размере 2000 руб.; x6 = 100, значит, что 100 кг сырья (материалов) первого вида осталось неиспользованным.

Полученное решение проверяют. Для этого найденные значения неизвестных табл. 4.5 подставляют в симплексные уравнения и в значение L(x).

5 х 0 + 4 х 0 + 6 х 0 + 10 х 200 + 3 х 200 + 100 = 2700,

х 0 + 3 х 0 + 1 х 0 + 2 х 200 + 3 х 200 + 0 = 1000,

х 0 + 1 х 0 + 5 х 0 + 4 х 200 + 1 х 200 + 0 = 1000,

L(x) = 5 х 0 + 3 х 0+ 4 х 0 + 6 х 200 + 4 х 200 + 3 х 0 + 0 + 0 = 2000.

Ценную дополнительную информацию представляют значения строки L(x), т.е. двойственные оценки в оптимальном решении. Значение строки L(x) для столбца x7, равное единице, показывает, сколько единиц прибыли приносит единица сырья (материала) II вида при производстве продукции. Значение строки L(x) для столбца x8, равное единице, показывает, сколько единиц прибыли приносит единица производственной мощности при производстве продукции.

С помощью двойственных оценок не сложно проверить значение L(x) для столбца x0, для чего следует вычислить прибыль, получаемую от производства продукции как за счет использования сырья (материалов), так и за счет производственной мощности. Сырье II вида позволило получить прибыль при производстве продукции:

для В4: 1 х 200 х 2 = 400;

для В5: 1 х 200 х 3 = 600,

где первые сомножители представляют двойственные оценки;

вторые сомножители показывают количество производимой продукции по оптимальному варианту;

третьи сомножители показывают нормы расхода сырья II вида на производство продукции В4 и В5 соответственно.

В сумме прибыль составит: 400 + 600 = 1000.

Количество прибыли, получаемой при производстве продукции за счет использования производственной мощности, равно:

для В4:1 х 200 х 4 = 800; для В5:1 х 200 х 1 = 200.

Общая сумма прибыли, полученной при производстве продукции за счет использования производственной мощности, составит:

800 + 200 = 1000.

Общая сумма прибыли, получаемой за счет полного использования сырья II вида и производственной мощности, равна: 1000 +

+ 1000 = 2000.

Значение L(x) для столбца x6 равно нулю, это означает, что ресурсы сырья I вида не лимитируют производство продукции, и сырье данного вида осталось неиспользованным.

Оценки в строке L(x) для основных неизвестных, не вошедших в оптимальный план, представляют не менее интересную экономическую информацию. Цифра 2 в столбце x1 показывает, сколько единиц прибыли пришлось бы потерять, если была бы произведена одна единица продукции В1. Оценка 1 в столбце x2 показывает, что, если бы была произведена единица продукции В2, то прибыль в оптимальном решении уменьшилась бы на одну единицу. Аналогичные рассуждения относятся и к оценке в столбце x3. Все эти предположения нетрудно проверить. Если предположить, что будет произведено 20 ед. продукции В2 и 180 ед. продукции В5, то общий объем прибыли, вычисленный с помощью двойственных оценок, составит: 1980 (2000 — 20 х 1). Этот же объем прибыли получится, если в качестве исходных условий для данного расчета взять объем производства продукции и прибыль, получаемую от производства единицы продукции. Прибыль, получаемая от производства продукции В2, составляет 60 (3 х 20); от производства продукции В5 составит 720 (4 х 180); от В4 — 1200 (6 х 200). В сумме прибыль от произведенной продукции составит 1980 (60 + 720 + 1200).

Как видно из проведенных расчетов, производство единицы продукции В2 снизило получение прибыли на одну единицу. Оценку 2 для столбца x1 можно интерпретировать и так, чтобы производство продукции В1 не было невыгодным, цена на нее должна быть увеличена на 2 руб. прибыли. Нулевая оценка основных неизвестных x4 и x5 соответствует тому, что продукция В4 и В5 входит в оптимальный план.

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

В системе симплексных уравнений должна содержаться единичная подматрица (в задаче она образована переменными x7, x8), свободные члены уравнений должны быть неотрицательными. Система симплексных уравнений должна быть совместна, т.е. уравнения не должны быть противоречивыми.

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

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

Например, требуется определить опорный план для задачи со следующими условиями:

L(x) = 2x1 + 4x2 + 5x3 + x4 + 6x5 — max.

x1 + x2 + 3x3 = 10,

3x2 + 5x3 +2x4 < 15, 6x2+ 4x3 + x5 = 20, x > 0 (j = 1, 2, 5).

Сначала вводят дополнительную переменную x6 в уравнение:

L(x) = 2x1 + 4x2+ 5x3 + x4 + 6x5+ x6 — max.

x1 + x2+ 3x3 = 10,

3x2+ 5x3+ 2x4 + x6 = 15, 6x2+ 4x3 + x5 = 20, x. > 0 (j = 1, 2, 6).

Учитывая, что в первом и третьем уравнениях имеется единичный вектор, в качестве опорного плана можно взять вектор:

x = ( х1; х6; х5 ) = (10; 15; 20).

В решениях задач, вычисляемых симплексным методом, есть одна неслучайная особенность: каким бы ни было количество основных неизвестных, в оптимальном варианте решения число ненулевых значений неизвестных не превышает количества исходных ограничений. Эта особенность формально вытекает из построения симплексной таблицы. В основании таблицы ровно столько строк, сколько в задаче ограничений. Каждая строка представляет только одно неизвестное. Поэтому в план входят только те неизвестные, которые представлены в таблице, остальные неизвестные равны нулю. Следовательно, о количестве неизвестных, имеющих в решении ненулевое значение, можно знать еще до решения задачи, но при условии полной формулировки условий. Однако все это верно для случая, когда имеется только одно оптимальное решение. Если же задача имеет множество оптимальных решений, то часть этого множества вариантов может иметь больше положительных значений неизвестных. (Аналогичный случай существует для транспортной задачи, когда из части множества число вариантов оптимального плана будет больше m + n — 1.)