Моделей линейного программирования

 

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

 

 

2.5.1. МАТЕМАТИЧЕСКИЕ МОДЕЛИ УПРАВЛЕНИЯ

ПРОИЗВОДСТВОМ

 

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

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

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

В общем виде такая задача математически формулируется следующим образом

F(x) ® max

при ограничениях g_j(x) £ b_j j = 1,2,3,... m (3.10)

 

Здесь:

F(x) – целевая функция, выражающая главную цель данной задачи – максимизировать прибыль. Таким образом, F(x) представляет собой математическое выражение, описывающее прибыль через управляющие переменные x. Переменные же x = (x₁, x₂,... x_n) – это искомые объемы выпуска соответствующего вида продукции;

b_{j =} (b₁, b₂,...,b_m) – величины соответствующих ресурсов предприятия;

g_j(x) = (g₁(x), g₂(x),..., g_m(x)) – текущие суммарные расходы ресурсов предприятия при фиксированных объемах выпуска каждого вида продукции. Эти расходы не должны превышать величин соответствующих ресурсов, которыми располагает предприятие.

При известных расчетных величинах прибыли на единицу объема выпуска каждого вида продукции целевая функция F(x), отражающая величину суммарной прибыли предприятия по всем видам продукции в зависимости от объемов выпуска x = (x₁, x₂,... x_n), может быть представлена в виде

 

F(x) = c₁x₁ + c₂x₂ + c₃x₃ +... + c_nx_n, (3.11)

где c₁, c₂, c₃,..., c_n – удельные (рассчитанные на единицу объема выпуска) величины прибыли по каждому виду продукции;

n – количество видов выпускаемой продукции (номенклатура).

Система ограничений по ресурсам может быть записана следующим образом

 

- ограничение по 1- му ресурсу: a₁₁x₁ +a₁₂x₂ + a₁₃x₃ +...+ a_1nx_n £ b₁

- ограничение по 2 - му ресурсу: a₂₁x₁ +a₂₂x₂ + a₂₃x₃ +...+ a_2nx_n £ b₂ (3.12)

- ограничение по 3- му ресурсу: a₃₁x₁ +a₃₂x₂ + a₃₃x₃ +...+ a_3nx_n £ b₃

......................................................

- ограничение по m- му ресурсу: a_m1x₁ +a_m2x₂ + a_m3x₃+...+ a_mnx_n £ b_m

(всего m ресурсов).

 

В системе ограничений (3.12) a₁₁, a₁₂, a₁₃,..., a₂₁, a₂₂, a₂₃... и т.д. – расходы соответствующих ресурсов на единицу объема выпуска каждого вида продукции. Система ограничений (3.12) должна быть дополнена требованиями неотрицательности всех x, так как объемы выпуска по смыслу задачи не могут выражаться отрицательными числами

Таким образом, математическая модель оптимизации объемов выпуска продукции по критерию максимума прибыли записывается в виде

 

c₁x₁ + c₂x₂ + c₃x₃ +... + c_nx_n ® max

a₁₁x₁ +a₁₂x₂ + a₁₃x₃ +... + a_1nx_n £ b₁

a₂₁x₁ +a₂₂x₂ + a₂₃x₃ +... + a_2nx_n £ b₂ (3.13)

a₃₁x₁ +a₃₂x₂ + a₃₃x₃ +... + a_3nx_n £ b₃

..............................

a_m1x₁ +a_m2x₂ + a_m3x₃ +... + a_mnx_n £ b_m

 

x_j ³ 0 (j = 1,n)

 

Математическая модель (3.13) предполагает неограниченные потребности рынка на все виды продукции (не ограничены объемы выпуска сверху) и отсутствие обязательных поставок (не ограничены объемы выпуска снизу). Если же запросы рынка (возможность сбыта) по каким-либо (или по каждому) видам продукции ограничены, а также имеются ограничения снизу в виде обязательных объемов выпуска по заключенным договорам или в связи с внутренними потребностями (данная продукция как сырье или материалы используется в собственном производстве), то математическая модель должна быть дополнена соответствующей группой ограничений по минимальным и максимальным объемам поставок по каждому виду продукции. Такие ограничения имеют вид

 

V_imin £ x_i £ V_imax (3.14)

Возможна и другая формулировка задачи управления: найти оптимальные объемы выпускаемой продукции x = (x₁, x₂,... x_n), обеспечивающие минимум издержек (затрат производства) при сохранении установленного суммарного уровня прибыли (или выручки) A _min.

В этом случае целевая функция математической модели управления имеет вид, по структуре аналогичный формуле (3.11), с той однако разницей, что в этом случае целевая функция представляет собой суммарные издержки производства при объемах выпуска продукции x = (x₁, x₂,... x_n).

 

F(x) = c₁x₁ + c₂x₂ + c₃x₃ +... + c_nx_n,(3.15)

Здесь c₁, c₂, c₃,..., c_{n –} удельные (рассчитанные на единицу объема выпуска) величины затрат по каждому виду продукции (то есть величины затрат на единицу подвижного состава соответствующего маршрута).

Ограничение по установленному уровню прибыли может быть записано следующим образом

 

a₁x₁ +a₂x₂ + a₃x₃ +... + a_nx_n £ A _min(3.16)

 

В формуле (3.16) a₁, a₂, a₃,..., a_n– удельные (рассчитанные на единицу объема выпуска) величины прибыли по каждому виду продукции, а левая часть неравенства представляет собой суммарную прибыль за заданный промежуток времени при объемах выпуска продукции x = (x₁, x₂,... x_n)за этот промежуток времени.

Ограничения по минимальным и максимальным объемам поставок продукции, как и ранее, имеют вид (3.14)

 

V_imin £ x_i £ V_imax (3.17)

 

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

 

c₁x₁ + c₂x₂ + c₃x₃ +... + c_nx_n ® min

a₁x₁ +a₂x₂ + a₃x₃ +... + a_nx_n £ A _min (3.18)

V_imin £ x_i £ V_imax

 

Информационное обеспечение математической модели управления

В качестве исходной информации для решения задачи управления по оптимизации объемов выпуска продукции требуется, прежде всего, матрица расходов ресурсов по каждому виду продукции, то есть коэффициенты a_ji системы ограничений (3.12) (здесь j – номер ресурса, i – номер соответствующего вида выпускаемой продукции).

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

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

 

Вид ресурса	Составляющие	Единицы расхода	Примечание
Люди	Управление Производство Маркетинг	человеко-часы
Материалы (сырье)	Металл Зерно Мука Древесина Доска и т.п.	тонны, кубометры, кв.м и т.п.	В зависимости от структуры материалов
Оборудование	Станки Машины Компьютеры и т.п.	часы, киловатты и т.п.	В зависимости от вида оборудования
Услуги сторонних организаций	Заключение договоров Оформление документов Закупки сырья и т.п.	рубли, тыс.руб, доллары США и т.п.
Энергоносители	Электроснабжение Теплоснабжение Газоснабжение	квтчас, ккал, кубометры и т.п.	В зависимости от вида энергоносителя
Земля	Общая площадь, занимаемая предприятием	кв.м
Здания и сооружения	Производственные площади Площади вспомогательных комплексов (котельная, склады и т.п)	кв.м
Природные ресурсы	Вода Лес Полезные ископаемые Геотермальные источники Ветер и т.п.	кубометры, тонны, ккал, квт и т.п	В зависимости от вида ресурсов

Ресурсы	Удельный расход по 1-му виду продукции	Удельный расход по 2-му виду продукции	Удельный расход по 3-му виду продукции	...	Удельный расход по n-му виду продукции
Ресурс 1	a11	a12	a13	...	a1n
Ресурс 2	a21	a22	a23	...	a2n
...	...	...	...	...	...
Ресурс m	am1	am2	am3	...	amn

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

 

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

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

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

 

 

2.5.2. ДВОЙСТВЕННЫЕ ЗАДАЧИ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ

 

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

Вернемся к задаче оптимизации объемов выпуска продукции. Математическая модель этой задачи управления производством в виде (3.13) и ее содержательная интерпретация представлены ниже в левой части таблицы.

Предположим, что некоторая организация решила закупить ресурсы предприятия, и необходимо установить оптимальные цены на эти ресурсы y₁, y₂,..., y_m. Здесь y_i – единичная стоимость i-того ресурса (например, стоимость одного станка – для единиц оборудования, одного человеко-дня – для трудовых ресурсов, стоимость 1 кв.м. производственной площади – для зданий и т.п.).

Очевидно, что покупающая организация заинтересована в том, чтобы затраты ее на все ресурсы Z, имеющиеся, как известно, в количествах b₁, b₂,..., b_m, были минимальны, то есть

 

Z = b₁y₁ + b₂y₂ + b₃y₃ +... + b_my_m ® min (3.19)

 

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

 

Задача 1 (исходная)

Задача 2 (двойственная)

c1x1 + c2x2 + c3x3 +... + cnxn ® max   при ограничениях a11x1 +a12x2 + a13x3 +... + a1nxn £ b1 a21x1 +a22x2 + a23x3 +... + a2nxn £ b2 a31x1 +a32x2 + a33x3 +... + a3nxn £ b3 .............................. am1x1 +am2x2 + am3x3 +...+ amnxn £ bm   и условии неотрицательности xj ³ 0 (j = 1,n)   Составить такой план выпуска продукции X = (x1, x2,..., xn), который обеспечит максимальную прибыль от реализации продукции при условии, что потребление ресурсов не превзойдет запасов, имеющихся по каждому виду этих ресурсов.

b1y1 + b2y2 + b3y3 +... + bmym ® min   при ограничениях a11y1 +a21y2 + a31y3 +... + am1ym ³ c1 a12y1 +a22x2 + a32x3 +... + am2ym ³c2 a13y1 +a23y2 + a33y3 +... + am3ym ³ c3 .............................. a1ny1 +a2ny2 + a3ny3 +... + amnym ³ cn   и условии неотрицательности yi ³0 (i = 1,m)   Найти такой набор цен (оценок) ресурсов Y = (y1, y2,..., ym), который обеспечит минимальные общие затраты на ресурсы при условии, что затраты на ресурсы при выпуске каждого вида продукции не меньше прибыли от реализации этой продукции

 

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

 

a₁₁y₁ +a₂₁y₂ + a₃₁y₃ +... + a_m1y_m ³ c₁ (3.20)

 

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

Рассмотрим формально две задачи (1 и 2) линейного программирования, представленные в таблице, абстрагируясь от содержательной интерпретации параметров, входящих в их модели. Обе задачи обладают следующими свойствами:

n В одной задаче ищут максимум линейной функции, в другой – минимум.

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

n В задаче максимизации все ограничения-неравенства имеют знак " £ ", а в задаче минимизации все неравенства вида " ³ ".

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

a11	a12	...	a1n
a21	a22	...	a2n
...	...	...	...
am1	am2	...	amn

a11	a21	...	am1
a12	a22	...	am2
...	...	...	...
a1n	a2n	...	amn

 

для задачи1 A = для задачи 2 A =

 

n Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.

n Условия неотрицательности переменных имеются в обеих задачах.

Две задачи 1 и 2 линейного программирования, обладающие указанными свойствами, называются симметричными взаимно двойственными задачами.