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

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

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

Если - доход от произведенного изделия i-го типа и каждое произведенное изделие покупается по одной и той же цене, то суммарный доход предприятия является простой суммой

,(1)

что отражает присутствие слова ''линейное'' в названии ''линейное программирование''.

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

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

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

,(2)

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

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

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

Чаще всего это так называемые ресурсные ограничения, описывающие тот факт что

· для производства товаров приходиться тратить ресурсы;

· количество ресурсов, которое можно затратить на производство товаров, ограничено.

Если считать, что в нашем производстве используются i=1,2,…,m ресурсы (труд, различные виды сырья, энергия и т.д. ), то в модели линейного программирования эти два факта описываются с помощью коэффициентов , которые задают затраты i-го ресурса на производство единицы j-го продукта.

Если затраты ресурсов линейно возрастают в зависимости от роста объемов производства, то для выпуска продукта j в количестве единиц требуется единиц i-го ресурса. Выпуск всего плана потребует при этом

единиц i-го ресурса.

Когда в наличии имеется не более единиц этого ресурса, то ясно, что любой реализуемый план производства x должен удовлетворять ограничению

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

(3)

где - запасы соответствующих ресурсов. Эту систему можно записать компактнее, как

чем мы и будем в дальнейшем пользоваться.

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

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

(4)

Последний тип ограничений может отражать, например, требования заказчика на удовлетворение определенных стандартов. Например, если - составляющие кормовой смеси для рациона животных на сельскохозяйственной ферме, а - пищевая ценность j-го продукта относительно i-го критерия ( например, калорийность ), то условие (4) может означать требование, что суммарная пищевая ценность компонент смеси была не меньше, чем определенный стандарт .

С точки зрения практического экономиста, применение линейного программирования означает, таким образом:

1. определение структуры задачи - что в ней является критерием, какие в ней присутствуют ограничения, какими переменными величинами () мы можем управлять, в чем заключается желаемый экономический эффект;

2. сбор необходимой информации - определение, часто путем статистических исследований, анализа рынка, прогнозов и пр., значений коэффициентов задачи: стоимостных коэффициентов , расходных , объемов доступных ресурсов .

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

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

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

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

2. Задача о раскрое материала

2.2 Общие сведения

Необходимо из кусков материала длиной d _i ( i = 1, 2, …, m ) выкроить заготовки длиной a _j ( j = 1, 2, …, n ) в указанном ассортиментном наборе, заданном вектор-столбцом [b _jo]. Требуется определить оптимальный план раскроя материала, т.е. получить максимум ассортиментных наборов с минимальными отходами т.е. найти матрицу [x _{i j} ] ( количество j - х заготовок в i - х кусках).

Рассмотрим в качестве основного критерий максимума ассортиментных наборов при заданном ограничении по минимуму отходов (для всех видов раскроя есть норматив отходов Z). Эта разница в критериях приводит к разнице в методах решения задачи.

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

Пусть ? _i - отходы, получаемые от i - го куска материала. Тогда сумма отходов равна

= - (2.1)

Итак, требуется найти матрицу оптимального решения [x_ijо], максимизирующую линейную форму L при условиях

L = (2.2)a_j x _{i j} d _i (2.3)

x _{i j} b _jo (2.4)x _{i j} 0 (2.5)

a _j > 0 , b _{j o} > 0 (2.6) ? _i = d _i - Z (2.7)

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

Например, заготовки после разреза дополнительно обрабатываются. С тем, чтобы при разрезе не допустить брака, между заготовками при раскрое вводятся перемычки (припуски, зазоры и т.п.) между заготовками с определяющим размером p.

Таким образом, сумма длин перемычек q _i в кусках материала равна

q _i = 0 , если x _{i j} 1; q _i = p (x _{i j} - 1) , если x _{i j} > 1 (2.8)

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

Неравенство (2.3) будет выглядеть следующим образом:

a _j x _{i j} + q _i d _i (2.9)

Неравенство (2.7) будет:

? _i = d _i - Z (2.10)

Задача (2.2), (2.4) - (2.6), (2.8) -(2.10) является принципиально нелинейной, область изменения переменных невыпукла и представляет собой форму "ежа".

Существенным моментом в рассматриваемом методе решения задачи является следующее.

Первоначально находится максимум ассортиментных наборов заготовок. При этом равенство (2.7) может не соблюдаться, т.е. отходы могут превышать норматив. Для выхода из этой ситуации используется следующий подход. При вводе информации указывается в какой последовательности количество отдельных видов заготовок может превышать пропорцию, указанную вектором [b j o]. В этом случае уже решается задача с использованием неравенства (2.7) для остатков после нахождения максимума ассортиментных наборов. Если и в этом случае (2.7) не удовлетворяется, то полученный максимум ассортиментных наборов заготовок уменьшается на 1 и процесс повторяется до нахождения решения.

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