Для того, чтобы составить математическую модель задачи линейного программирования, необходимо выполнить четыре действия, исходя из условий задачи:
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, которые доставляют максимум целевой функции С и при этом не нарушают ограничений.
В общем виде такая математическая модель получила название «стандартная форма записи задачи линейного программирования»: