МОДЕЛЕЙ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Основной формой деятельности любого предприятия является производство тех или иных видов продукции. При этом в процессе производства предприятие потребляет (расходует) определенные виды ресурсов: труд, сырье, оборудование, денежные средства, природные ресурсы и т.п. Поскольку обычно размеры ресурсов ограничены, возникают определенные проблемы их рационального распределения. Если предприятие выпускает продукцию нескольких видов с использованием одних и тех же ресурсов (например, оборудование, трудовые ресурсы), то администрация должна решить, какое количество продук- ции каждого вида производить. Принятое решение будет направлено на удовлетворение определенной цели администрации. Для удовлетворения этой цели администрация располагает управляющими переменными решения. Переменные решения – это количество продукции каждого вида, которое необходимо произвести за данный период времени.
2.5.1. МАТЕМАТИЧЕСКИЕ МОДЕЛИ УПРАВЛЕНИЯ
ПРОИЗВОДСТВОМ
В общем случае цель администрации состоит в определении наиболее эффективного метода такого распределения ресурсов по соответствующим переменным, которое оптимизирует некоторый результат функционирования системы.
Таким образом, постановка задачи управления высшего уровня (первого лица предприятия) может быть сформулирована так: при сложившейся номенклатуре выпускаемой продукции определить оптимальные объемы выпуска каждого вида продукции за определенный период, обеспечивающие при ограниченных ресурсах максимальную суммарную прибыль предприятия.
Такая задача эффективно решается с использованием математического моделирования в среде информационных технологий.
В общем виде такая задача математически формулируется следующим образом
F(x) ® max
при ограничениях gj(x) £ bj j = 1,2,3, . . . m (3.10)
Здесь:
F(x) – целевая функция, выражающая главную цель данной задачи – максимизировать прибыль. Таким образом, F(x) представляет собой математическое выражение, описывающее прибыль через управляющие переменные x. Переменные же x = (x1, x2, . . . xn) – это искомые объемы выпуска соответствующего вида продукции;
bj = (b1, b2, . . . ,bm) – величины соответствующих ресурсов предприятия;
gj(x) = (g1(x) , g2(x) , . . . , gm(x)) – текущие суммарные расходы ресурсов предприятия при фиксированных объемах выпуска каждого вида продукции. Эти расходы не должны превышать величин соответствующих ресурсов, которыми располагает предприятие.
При известных расчетных величинах прибыли на единицу объема выпуска каждого вида продукции целевая функция F(x), отражающая величину суммарной прибыли предприятия по всем видам продукции в зависимости от объемов выпуска x = (x1, x2, . . . xn), может быть представлена в виде
F(x) = c1x1 + c2x2 + c3x3 + . . . + cnxn , (3.11)
где c1 , c2, c3 , . . ., cn – удельные (рассчитанные на единицу объема выпуска) величины прибыли по каждому виду продукции;
n – количество видов выпускаемой продукции (номенклатура).
Система ограничений по ресурсам может быть записана следующим образом
- ограничение по 1- му ресурсу: a11x1 +a12x2 + a13x3 + ...+ a1nxn £ b1
- ограничение по 2 - му ресурсу: a21x1 +a22x2 + a23x3 + ...+ a2nxn £ b2 (3.12)
- ограничение по 3- му ресурсу: a31x1 +a32x2 + a33x3 + ...+ a3nxn £ b3
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
- ограничение по m- му ресурсу: am1x1 +am2x2 + am3x3+ ...+ amnxn £ bm
(всего m ресурсов).
В системе ограничений (3.12) a11 , a12, a13, . . . , a21 , a22 , a23 . . . и т.д. – расходы соответствующих ресурсов на единицу объема выпуска каждого вида продукции. Система ограничений (3.12) должна быть дополнена требованиями неотрицательности всех x, так как объемы выпуска по смыслу задачи не могут выражаться отрицательными числами
Таким образом, математическая модель оптимизации объемов выпуска продукции по критерию максимума прибыли записывается в виде
c1x1 + c2x2 + c3x3 + . . . + cnxn ® max
a11x1 +a12x2 + a13x3 + . . . + a1nxn £ b1
a21x1 +a22x2 + a23x3 + . . . + a2nxn £ b2 (3.13)
a31x1 +a32x2 + a33x3 + . . . + a3nxn £ b3
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
am1x1 +am2x2 + am3x3 + . . . + amnxn £ bm
xj ³ 0 (j = 1,n)
Математическая модель (3.13) предполагает неограниченные потребности рынка на все виды продукции (не ограничены объемы выпуска сверху) и отсутствие обязательных поставок (не ограничены объемы выпуска снизу). Если же запросы рынка (возможность сбыта) по каким-либо (или по каждому) видам продукции ограничены, а также имеются ограничения снизу в виде обязательных объемов выпуска по заключенным договорам или в связи с внутренними потребностями (данная продукция как сырье или материалы используется в собственном производстве), то математическая модель должна быть дополнена соответствующей группой ограничений по минимальным и максимальным объемам поставок по каждому виду продукции. Такие ограничения имеют вид
Vimin £ xi £ Vimax (3.14)
Возможна и другая формулировка задачи управления: найти оптимальные объемы выпускаемой продукции x = (x1, x2, . . . xn), обеспечивающие минимум издержек (затрат производства) при сохранении установленного суммарного уровня прибыли (или выручки) A min.
В этом случае целевая функция математической модели управления имеет вид, по структуре аналогичный формуле (3.11), с той однако разницей, что в этом случае целевая функция представляет собой суммарные издержки производства при объемах выпуска продукции x = (x1, x2, . . . xn).
F(x) = c1x1 + c2x2 + c3x3 + . . . + cnxn ,(3.15)
Здесь c1 , c2, c3 , . . ., cn – удельные (рассчитанные на единицу объема выпуска) величины затрат по каждому виду продукции (то есть величины затрат на единицу подвижного состава соответствующего маршрута).
Ограничение по установленному уровню прибыли может быть записано следующим образом
a1x1 +a2x2 + a3x3 + . . . + anxn £ A min(3.16)
В формуле (3.16) a1 , a2, a3 , . . ., an– удельные (рассчитанные на единицу объема выпуска) величины прибыли по каждому виду продукции, а левая часть неравенства представляет собой суммарную прибыль за заданный промежуток времени при объемах выпуска продукции x = (x1, x2, . . . xn)за этот промежуток времени.
Ограничения по минимальным и максимальным объемам поставок продукции, как и ранее, имеют вид (3.14)
Vimin £ xi £ Vimax (3.17)
Таким образом, в такой постановке математическая модель верхнего иерархического уровня управления имеет вид
c1x1 + c2x2 + c3x3 + . . . + cnxn ® min
a1x1 +a2x2 + a3x3 + . . . + anxn £ A min (3.18)
Vimin £ xi £ Vimax
Информационное обеспечение математической модели управления
В качестве исходной информации для решения задачи управления по оптимизации объемов выпуска продукции требуется, прежде всего, матрица расходов ресурсов по каждому виду продукции, то есть коэффициенты aji системы ограничений (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) и ее содержательная интерпретация представлены ниже в левой части таблицы.
Предположим, что некоторая организация решила закупить ресурсы предприятия, и необходимо установить оптимальные цены на эти ресурсы y1, y2, . . . , ym. Здесь yi – единичная стоимость i-того ресурса (например, стоимость одного станка – для единиц оборудования, одного человеко-дня – для трудовых ресурсов, стоимость 1 кв.м. производственной площади – для зданий и т.п.).
Очевидно, что покупающая организация заинтересована в том, чтобы затраты ее на все ресурсы Z, имеющиеся, как известно, в количествах b1, b2, . . ., bm, были минимальны, то есть
Z = b1y1 + b2y2 + b3y3 +. . . + bmym ® 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), который обеспечит минимальные общие затраты на ресурсы при условии, что затраты на ресурсы при выпуске каждого вида продукции не меньше прибыли от реализации этой продукции |
Поскольку удельные расходы каждого вида ресурсов при производстве того или иного вида продукции известны (матрица удельных расходов ресурсов), то удовлетворение требований продавца можно записать в виде соответствующей системы ограничений. Например, ограничение, соответствующее удовлетворению этого требования при изготовлении первого вида продукции, выглядит так
a11y1 +a21y2 + a31y3 + . . . + am1ym ³ c1 (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 линейного программирования, обладающие указанными свойствами, называются симметричными взаимно двойственными задачами.