Для того, чтобы составить математическую модель задачи линейного программирования, необходимо выполнить четыре действия, исходя из условий задачи: 1. Записать исходные данные. 2. Определить переменные. 3. Сформулировать целевую функцию. 4. Записать систему ограничений. ### Производственная задача Изучение линейного программирования чаще всего начинают с производственной задачи, самой простой и понятной. Ее суть сводится к следующему: есть некое производственное предприятие, выпускающее несколько видов продукций. Обозначены ресурсы и их количество, необходимое для производства продукции. Количество ресурсов ограничено. Известно, за какую цену можно продать ту или иную продукцию. Необходимо понять, какие производственные изделия следует произвести и в каком количестве, чтобы прибыль предприятия была максимальной. Разберем задачу на примере. Рассмотрим столярный цех, который производит кухни и офисную мебель. Для каждого из двух типов продукции у нас используются следующие материалы: ДСП, стекло и фурнитура (дверные ручки, петли и прочее). В итоге мы имеем номенклатуру продукции (кухня и офисный комплект) и номенклатуру материалов, из которых они изготавливаются. Теперь мы можем составить матрицу, в которой будут описаны расходы материалов на изготовление одной кухни или одного офисного комплекта Исходные данные производственной задачи Например, для изготовления кухни нам нужно а11 листов ДСП, а12 квадратных метров стекла и а13 элементов фурнитуры. Для производства офисного комплекта нужно другое количество материалов: а21 листов ДСП, а22 м2 стекла и а23 элементов фурнитуры. В таком случае матрица примет следующий вид: | |ДСП|Стекло|Фурнитура| |---|---|---|---| |Кухня | а11 | а12 | а13 | | Офисный комплект | а21 | а22 | а23 | Далее, в производственной задаче задаются ограничения по складу, в котором хранятся материалы Ограничения по складу в производственной задаче | |ДСП|Стекло|Фурнитура| |---|---|---|---| |Склад | b1 | b2 | b3 | Стоимость продажи готовой продукции | Кухня |Стоимость продажи| |---|---| |Кухня | с1 | |Офисный комплект | с2 | Если объединить все исходные данные то их можно записать в виде следующей таблицы: | | ДСП|Стекло|Фурнитура|Стоимость продажи| |---|---|---|---|---| |Кухня | а11 | а12 | а13 | c1 | |Офисный комплект | а21 | а22 | а23 | c2 | |Материалов на складе | b1 | b2 | b3 | | | Следующим шагом нам нужно определить искомые переменные. В данном случае мы будем искать оптимальное количество каждого вида продукции, которые нужно изготовить. Обозначим переменные х1 – количество кухонных гарнитуров, х2 — количество офисных комплектов. ||ДСП|Стекло|Фурнитура|Стоимость продажи| Количество продукции | |---|---|---|---|--| |Кухня | а11 | а12 | а13 | c1 | x1 | |Офисный комплект | а21 | а22 | а23 | c2 | x2 | |Материалов на складе | b1 | b2 | b3 | | | Вид целевой функции отвечает на вопрос: «Какое соотношение количества произведенной продукции разных видов можно назвать оптимальным?». В нашем случае целевая функция будет выглядеть следующим образом: ``` C=c1x1 + c2x2 →max ``` Целевая функция имеет линейный вид, следовательно, мы можем использовать задачу линейного программирования. Теперь можно перейти к описанию ограничений, которые не позволяют целевой функции устремиться в бесконечность. В качестве ограничений в этой задаче выступает вместимость склада материалов. Ограничения будут выглядеть следующим образом: ``` a11x1 + a21x2 ≤ b1 a12x1 + a22x2 ≤ b2 a13x1 + a23x2 ≤ b3 ``` Опишем ограничения. Первое ограничение строится по первому столбцу таблицы. Данное ограничение говорит нам о том, что количество материала ДСП, израсходованного на производство x1 кухонь и x2 офисных комплектов, должно быть не больше b1, то есть запасов данного материала на складе. Второе и третье ограничения строятся аналогично: по второму и третьему столбцу таблицы, соответственно. Часто в задачах линейного программирования встречается еще одно ограничение — неотрицательность искомых переменных, в нашем случае, x1 и x2. На этом задачу можно считать сформулированной. Остается теперь найти способ ее решения, то есть отыскания таких значений переменных , x1 и x2, которые доставляют максимум целевой функции С и при этом не нарушают ограничений. В общем виде такая математическая модель получила название «стандартная форма записи задачи линейного программирования»: