Справочный материал Примеры Обратите внимание! Модели
Математическое программирование – область математики, разрабатывающая теорию и численные методы решения задач на экстремум функции многих переменных с ограничениями на область определения этих переменных.
Основные виды задач линейного программирования (ЗЛП)
Математической моделью задачи называют отражение реальной (производственной, экономической) ситуации в виде функций, уравнений и неравенств.
Линейным программированием (ЛП) называют раздел математического программирования, если все функции математической модели задачи линейные.
К основным видам задач ЛП, как правило, относят: задачи о наилучшем использовании ресурсов, задачи о выборе оптимальных технологий, задачи о размещении заказа, задачи о смесях, задачи о раскрое материалов, транспортные задачи и т. п. 
Рассмотрим постановку одной из задач и составим ее математическую модель. 
Постановка задачи. Предприятие пытается наладить выпуск n видов продукции: LaTeX formula: \Pi _{1}, \Pi _{2}, ..., \Pi _{n}. Для этого оно располагает LaTeX formula: m видами ресурсов LaTeX formula: P_{1},P_{2},...,P_{m}, объемы которых соответственно составляют: LaTeX formula: b_{1},b_{2},...,b_{m}. Известна прибыль, которую можно получить от реализации одной единицы каждого вида продукции: LaTeX formula: c_{1},c_{2},...,c_{n}.Расход LaTeX formula: j-го вида ресурса на выпуск одной единицы LaTeX formula: i-го вида продукции   LaTeX formula: a_{ij}представлен в технологической матрице:
LaTeX formula: A=\begin{pmatrix} a_{11} & a_{12} &... & a_{1n}\\ a_{21} &a_{22} &... & a_{2n}\\ ... &... & ...&... \\ a_{m1} &a_{m2} &... & a_{mn} \end{pmatrix}.
Необходимо определить план выпуска продукции, обеспечивающий максимальную прибыль.
Представим данные задачи в таблице:
Составим математическую модель задачи.
План:  LaTeX formula: X=(x_{1};x_{2};...;x_{n}). LaTeX formula: (12.1)
Целевая функция качества: 
LaTeX formula: max f(X)=c_{1}x_{1}+c_{2}x_{2}+...+c_{n}x_{n}. LaTeX formula: (12.2)
Система ограничений:
LaTeX formula: \left\{\begin{matrix} a_{11}x_{1} + a_{12}x_{2} +...+a_{1n}x_{n} \leq b_{1} ,& \\ a_{21}x_{1} + a_{22}x_{2} +...+a_{2n}x_{n} \leq b_{2},& \\...\\a_{m1}x_{1} + a_{m2}x_{2} +...+a_{mn}x_{n} \leq b_{m}. \end{matrix}\right. LaTeX formula: (12.3)
Условия не отрицательности переменных: 
LaTeX formula: x_{i}\geq 0, i=\overline{1,n}. LaTeX formula: (12.4)
Основные виды записи ЗЛП
Симметричной формой записи называют задачу 12.1 – 12.2 – 12.3 – 12.4 или задачу:
LaTeX formula: min f(X)=c_{1}x_{1}+c_{2}x_{2}+...+c_{n}x_{n}; LaTeX formula: (12.5)
LaTeX formula: \left\{\begin{matrix} a_{11}x_{1} &+ a_{12}x_{2} +...+a_{1n}x_{n} & \geq b_{1} ,& \\ a_{21}x_{1} &+ a_{22}x_{2} +...+a_{2n}x_{n} & \geq b_{2}, \\ & ...& & \\ a_{m1}x_{1} &+ a_{m2}x_{2} +...+a_{mn}x_{n} & \geq b_{m}. \end{matrix}\right.  LaTeX formula: (12.6)
 LaTeX formula: x_{i}\geq 0, i=\overline{1,n}. LaTeX formula: (12.7)                                       
Каноническая форма записи ЗЛП:
LaTeX formula: max (min) f(X)=\sum_{i=1}^{n}c_{i}x_{i}; LaTeX formula: (12.8)
LaTeX formula: \sum_{i=1}^{n}a_{ij}x_{i}=b_{j}, LaTeX formula: j=\overline{1,m}; LaTeX formula: (12.9)
LaTeX formula: x_{i}\geq 0, i=\overline{1,n}. LaTeX formula: (12.10)
Чтобы привести модель задачи к каноническому виду, при условии, что все правые части неравенств-ограничений неотрицательные, необходимо:
1) к левым частям неравенств типа  LaTeX formula: \leq прибавить неотрицательные дополнительные переменные, а из левых частей неравенств типа LaTeX formula: \geq  вычесть неотрицательные дополнительные переменные;
2) в целевую функцию дополнительные переменные ввести с коэффициентами, равными нулю.
Общая форма записи ЗЛП:
LaTeX formula: max (min) f(X)=\sum_{i=1}^{n}c_{i}x_{i}; LaTeX formula: (12.11)
LaTeX formula: \sum_{i=2}^{n}a_{ij}x_{i}=b_{j}, j=\overline{1,k_{1}}; LaTeX formula: (12.12)
LaTeX formula: \sum_{i=2}^{n}a_{ij}x_{i}\leq b_{j}, j=\overline{k_{1}+1,k_{2}}; LaTeX formula: (12.13)
LaTeX formula: \sum_{i=2}^{n}a_{ij}x_{i}\geq b_{j}, j=\overline{k_{2}+1,m}; LaTeX formula: (12.14) 
LaTeX formula: x_{i}\geq 0, i=\overline{1,n_{1}};    LaTeX formula: x_{i} - произвольные,  LaTeX formula: i=\overline{n_{1}+1,n}. LaTeX formula: (12.15)
Пример 1. При изготовлении продукции LaTeX formula: \Pi _{1} и LaTeX formula: \Pi _{2} используются токарные и фрезерные станки, а также сталь и цветные металлы. На производство единицы продукции LaTeX formula: \Pi _{1} требуется LaTeX formula: 120 и LaTeX formula: 210 станко-часов соответственно токарного и фрезерного оборудования, а также LaTeX formula: 30 кг стали и LaTeX formula: 5 кг цветных металлов. Для производства единицы продукции LaTeX formula: \Pi _{2} требуется соответственно LaTeX formula: 200, 100, 70 и LaTeX formula: 50 единиц тех же ресурсов. Цех располагает LaTeX formula: 22400 и LaTeX formula: 16800 станко-часами оборудования, LaTeX formula: 4800 кг и LaTeX formula: 500 кг металлов. Прибыль от реализации единицы продукции LaTeX formula: \Pi _{1} составляет LaTeX formula: 360 тыс. ден. ед., а продукции LaTeX formula: \Pi _{2} – LaTeX formula: 890 тыс. ден. ед. Необходимо определить план выпуска продукции, обеспечивающий максимальную прибыль.
Составьте математическую модель задачи и приведите ее к каноническому виду.
Решение. Составим таблицу данных:  
Составим математическую модель 12.1 – 12.2 – 12.3 – 12.4 данной задачи: 
LaTeX formula: max f(X)=360x_{1}+890x_{2};
LaTeX formula: \left\{ \begin{array}{lcl} 120x_{1} +200x_{2}\leq 22400, & & & \\ 210x_{1} +100x_{2}\leq 16800, & & & \\ 30x_{1} +70x_{2}\leq 4800, & & & \\ 5x_{1} +50x_{2}\leq 500; & & & \end{array} \right.  LaTeX formula: x_{1}, x_{2}\geq 0.
Приведем модель задачи к каноническому виду 12.8 – 12.9 – 12.10 с помощью дополнительных переменных  LaTeX formula: x_{3},x_{4},x_{5} и LaTeX formula: x_{6} . Получим:
LaTeX formula: max f(X)=360x_{1}+890x_{2}+0\cdot x_{3}+0\cdot x_{4}+0\cdot x_{5}+0\cdot x_{6};
LaTeX formula: \left\{ \begin{array}{lcl} 120x_{1} +200x_{2}+x_{3}= 22400, & & & \\ 210x_{1} +100x_{2}+x_{4}= 16800, & & & \\ 30x_{1} +70x_{2}+x_{5}= 4800, & & & \\ 5x_{1} +50x_{2}+x_{6} =500. & & & \end{array} \right. x_{i}\geq 0, i=\overline{1,6}.
Пример 2. В опытном хозяйстве установили, что откорм животных выгоден тогда, когда животное будет получать в дневном рационе не менее LaTeX formula: 8 ед. питательного вещества LaTeX formula: A, не менее LaTeX formula: 15 ед. вещества LaTeX formula: B и не менее LaTeX formula: 5 ед. вещества LaTeX formula: C. Для кормления животных используются три вида корма: LaTeX formula: K_{1}, K_{2} и LaTeX formula: K_{3}. В таблице показано сколько единиц каждого питательного вещества содержит LaTeX formula: 1 кг корма каждого вида:
Составьте суточный рацион кормления скота.
Решение. Составим математическую модель 12.1 – 12.5 – 12.6 – 12.7 данной  задачи:
план закупки корма:  LaTeX formula: X=(x_{1};x_{2},x_{3});
LaTeX formula: min f(X)=15x_{1}+18x_{2}+9x_{3};LaTeX formula: \left\{ \begin{array}{lcl} 3x_{1}+x_{2} \geq 8,& & \\ 2x_{1}+4x_{2}+3x_{3} \geq 15, & & \\ 5x_{2}+2x_{3} \geq 5; & & \end{array} \right.  LaTeX formula: x_{i}\geq 0, i=\overline{1,3}.
Приведем модель задачи к каноническому виду 12.8 – 12.9 – 12.10 с помощью дополнительных переменныхLaTeX formula: x_{4},x_{5}  и LaTeX formula: x_{6} . Получим:
LaTeX formula: min f(X)=15x_{1}+18x_{2}+9x_{3}+0\cdot x_{4}+0\cdot x_{5}+0\cdot x_{6};
LaTeX formula: \left\{ \begin{array}{lcl} 3x_{1}+x_{2} -x_{4}= 8,& & \\ 2x_{1}+4x_{2}+3x_{3}-x_{5} = 15, & & \\ 5x_{2}+2x_{3}-x_{6} = 5; & & \end{array} \right. x_{i}\geq 0, i=\overline{1,6}.
Пример 3. В цех распила поступило LaTeX formula: 520 бревен длиной LaTeX formula: 5 м. Их необходимо разрезать на заготовки LaTeX formula: A и LaTeX formula: B длиной соответственно LaTeX formula: 2м и LaTeX formula: 1,5м и составить из них комплекты. В каждый комплект входит LaTeX formula: 3 заготовки LaTeX formula: A и LaTeX formula: 2 заготовкиLaTeX formula: B. Составьте план распила бревен, гарантирующий минимизацию отходов.
Решение. Составим таблицу данных: 
Составим математическую модель задачи: 
План: LaTeX formula: X=(x_{1};x_{2},x_{3}); где 
LaTeX formula: x_{1}  – количество бревен, подлежащих распилу по варианту LaTeX formula: I,
LaTeX formula: x_{2}  – количество бревен, подлежащих распилу по варианту LaTeX formula: II,
LaTeX formula: x_{3}  – количество бревен, подлежащих распилу по варианту LaTeX formula: III;
LaTeX formula: x_{1},x_{2},x_{3}\geq 0.
Целевая функция: LaTeX formula: min f(X)=1x_{1}+0x_{2}+0,5x_{3}.
Система ограничений: 
LaTeX formula: \left\{ \begin{array}{lcl} x_{1} +x_{2}+x_{3}\leq 520,& \\ \frac{2x_{1}+x_{2}}{3}=\frac{2x_{2}+x_{3}}{2}& \end{array} \right. или  LaTeX formula: \left\{\begin{matrix} x_{1} +x_{2}+x_{3}\leq 520,& \\ 4x_{1}-4x_{2}-9x_{3}=0.& \end{matrix}\right.
Приведем модель задачи к каноническому виду 12.8 – 12.9 – 12.10
LaTeX formula: min f(X)=1x_{1}+0x_{2}+0,5x_{3}+0x_{4}.
LaTeX formula: \left\{ \begin{array}{lcl} x_{1} +x_{2}+x_{3}+x_{4}= 520,& \\ 4x_{1}-4x_{2}-9x_{3}=0.& \end{array} \right.
LaTeX formula: x_{i}\geq 0,i=\overline{1,4}.
Прежде, чем приводить модель задачи к каноническому виду, необходимо убедиться (а в случае необходимости выполнить преобразования), что все правые части неравенств-ограничений неотрицательные. 
Например,  приведем модель задачи к каноническому виду: 
LaTeX formula: min (max) f(X)=15x_{1}+18x_{2}+9x_{3};
LaTeX formula: \left\{ \begin{array}{lcl} 3x_{1}-x_{2}\geq -8, & & \\ 2 x_{1}-4x_{2}+3x_{3}\geq 15,& & \\ - x_{2}+2x_{3}\leq -5;& & \end{array} \right. x_{i}\geq 0, i=\overline{1,3}.
Поскольку правые части первого и третьего неравенств системы ограничений отрицательные, то, умножим эти неравенства на число LaTeX formula: -1 и получим: 
LaTeX formula: \left\{ \begin{array}{lcl}-3x_{1}+x_{2}\leq 8, & & \\ 2 x_{1}-4x_{2}+3x_{3}\geq 15,& & \\ x_{2}-2x_{3}\geq 5.& & \end{array} \right.
Приведем модель задачи к каноническому виду 12.8 – 12.9 – 12.10:
LaTeX formula: min(max) f(X)=15x_{1}+18x_{2}+9x_{3}+0\cdot x_{4}+0\cdot x_{5}+0\cdot x_{6};
LaTeX formula: \left\{ \begin{array}{lcl} -3x_{1}+x_{2}+x_{4}= 8, & & \\ 2 x_{1}-4x_{2}+3x_{3}-x_{5}= 15,& & \\ x_{2}-2x_{3}-x_{6}= 5.& & \end{array} \right. x_{i}\geq 0, i=\overline{1,6}.
formula