Справочный материал Примеры Обратите внимание! Модели
Предпочтительный вид модели ЗЛП
Каноническая модель ЗЛП имеет предпочтительный вид, если в каждом из уравнений системы ограничений присутствует предпочтительная переменная. 
Переменная называется предпочтительной, если она присутствует только в одном из уравнений системы ограничений и только с коэффициентом, равным единице.
Например, рассмотрим задачу:
 LaTeX formula: max(min) f(X)=x_1-3x_2+7x_3 ; LaTeX formula: \begin{cases} \underline{x_1}-2x_3=0, \\ \underline{x_2}+5x_3=6, \\ x_3+\underline{x_4}=9; \end{cases}   LaTeX formula: x_i\geq 0 , LaTeX formula: i=\overline{1,4} .
Переменные LaTeX formula: x_1 , LaTeX formula: x_2  и  LaTeX formula: x_4 являются предпочтительными. 
Если в канонической модели задачи отсутствуют предпочтительные переменные, то вводим неотрицательные искусственные переменные. В целевую функции эти переменные в случае ее максимизации вводим с коэффициентом, равным LaTeX formula: -M, а в случае минимизации – с коэффициентом, равным LaTeX formula: +M
Например, рассмотрим задачу:
 LaTeX formula: max f(X)=x_1-3x_2+7x_4 ;   LaTeX formula: \begin{cases} \underline{x_1}-2x_3+3x_4=0, \\ \underline{x_2}+5x_3=6, \\ x_3+x_4=9; \end{cases}   LaTeX formula: x_i\geq 0 , LaTeX formula: i=\overline{1,4} .
Поскольку в третьем уравнении системы ограничений отсутствует предпочтительная переменная, то вводим искусственную переменную LaTeX formula: \omega \geq 0 . Получим: 
LaTeX formula: maxf(X)=x_1-3x_2+7x_4-M\omega ; LaTeX formula: \begin{cases} \underline{x_1}-2x_3+3x_4=0, \\ \underline{x_2}+5x_3=6, \\ x_3+x_4+\underline{\omega }=9; \end{cases}   LaTeX formula: x_i\geq 0, i=\overline{1,4} . 
Например, рассмотрим задачу:
LaTeX formula: min f(X)=x_1-3x_2+7x_4 ;  LaTeX formula: \begin{cases} x_1-2x_3=0, \\ x_1-x_2+5x_3=6, \\ x_3+\underline{x_4}=9; \end{cases}   LaTeX formula: x_i\geq 0, i=\overline{1,4} .
Поскольку в первых двух уравнениях системы ограничений отсутствуют предпочтительные переменные, то вводим искусственные переменные LaTeX formula: \omega _1\geq 0  и LaTeX formula: \omega _2\geq 0 . Получим: 
LaTeX formula: min f(X)=x_1-3x_2+7x_4+M\omega _1+M\omega _2 ;  LaTeX formula: \begin{cases} x_1-2x_3+\underline{\omega _1}=0, \\ x_1-x_2+5x_3+\underline{\omega _2}=6, \\ x_3+\underline{x_4}=9; \end{cases}   LaTeX formula: x_i\geq 0, i=\overline{1,4} .
Построение начального опорного плана задачи
Рассмотрим задачу:
LaTeX formula: X=(x_1;x_2;...;x_n) . ( 12.1)
LaTeX formula: max f(X)=c_1x_1+c_2x_2+...+c_nx_n . (12.2)
LaTeX formula: \begin{cases} 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{cases} (12.3)
LaTeX formula: x_i\geq 0, i=\overline{1,n}  . (12.4)
1. Приведем математическую модель задачи к каноническому и предпочтительному виду. Введем дополнительные переменные LaTeX formula: x_{n+1} , LaTeX formula: x_{n+2} , ... LaTeX formula: x_{n+m}  и получим: 
LaTeX formula: maxf(X)=c_1x_1+c_2x_2+...+c_nx_n+0\cdot x_{n+1}+ 0\cdot x_{n+2}+... LaTeX formula: +0\cdot x_{n+m}; (12.2.1)
LaTeX formula: \begin{cases} a_{11}x_1+a_{12}x_2+...+a_{1n}x_n+\underline{x_{n+1}}=b_1, \\ a_{21}x_1+a_{22}x_2+...+a_{2n}x_n+\underline{x_{n+2}}=b_2,\\ ... \\ a_{m1}x_1+a_{m2}x_2+...+a_{mn}x_n+\underline{x_{n+m}}=b_m. \end{cases} (12.3.1
LaTeX formula: x_i\geq 0 , i=\overline{1,n+m} . (12.4.1)
В нашем случае дополнительные переменные являются и предпочтительными.
2. Предпочтительные переменные являются базисными, а остальные переменные – свободными. Свободные переменные считаем равными нулю. Чтобы найти значения базисных переменных, необходимо в систему ограничений подставить значения свободных переменных. Получим: свободные переменные  LaTeX formula: x_{1}=0 , LaTeX formula: x_{2}=0 , …, LaTeX formula: x_{n}=0 ; базисные переменные LaTeX formula: x_{n+1}=b_1 , LaTeX formula: x_{n+2}=b_2 , …, LaTeX formula: x_{n+m}=b_m .
3. Составляем симплексную таблицу нулевой итерации:
4. Заполняем индексную строку.
Оценка целевой функции (значение целевой функции): 
LaTeX formula: \Delta _0=\sum_{k=n+1}^{n+m}C_k\cdot A_{0k} . (12.18)
Оценки переменных: 
LaTeX formula: \Delta _i=\sum_{k=n+1}^{n+m}C_k\cdot A_{ik}-c_i . (12.19)
Критерий оптимальности опорного плана задачи:
а) если при максимизации целевой функции все оценки переменных неотрицательные, то план оптимален;
б) если при минимизации целевой функции все оценки переменных неположительные, то план оптимален.
Переход к не худшему плану ЗЛП
Если опорный план задачи не удовлетворяет критерию оптимальности, то выполняем следующие действия.
1. Выбираем наихудшую оценку переменной. В случае максимизации целевой функции – наименьшую отрицательную, а в случае минимизации – наибольшую положительную. Столбец, в которой находится эта переменная, называется разрешающим
2. Для каждой базисной переменной составляем симплексные отношения – находим отношения элементов столбца LaTeX formula: A_0 и соответствующих элементов разрешающего столбца (отрицательные элементы разрешающего столбца и элементы, равные нулю, не образуют симплексных отношений): 
LaTeX formula: \theta _j=\frac{b^0_j}{a^0_{jP}} . (12.20)
Из полученных отношений выбираем наименьшее. Строку, которой соответствует это отношение, называем разрешающей. Элемент, который находится на пересечении разрешающих столбца и строки, называется разрешающим элементом LaTeX formula: a^0_{PP} . 
3. Переходим к первой итерации симплексной таблицы. 
Вносим изменения в базис: переменную, находящуюся в разрешающей строке нулевой итерации заменяем переменной из разрешающего столбца. 
Все элементы разрешающей строки делим на разрешающий элемент и записываем в строку первой итерации (номер строки совпадает с номером строки нулевой итерации). 
Все остальные элементы столбца, номер которого совпадает с номером разрешающего столбца нулевой итерации, считаем равными нулю. 
Остальные элементы таблицы находим по правилу прямоугольника (рис. 12.5): 
LaTeX formula: a^1_{ji}=\frac{a^0_{ji}\cdot a^0_{PP}-a^0_{jP}\cdot a^0_{Pi}}{a^0_{PP}} . (12.21)
По формулам 12.18 и 12.19 заполняем индексную строку таблицы первой итерации. 
Если выполняется критерий оптимальности нового плана задачи, то данная задача решена. В противном случае аналогично заполняем таблицу второй итерации.
Постановка двойственной задачи
Рассмотрим задачу 12.1 – 12.2 – 12.3 – 12.24 об определении оптимального плана выпуска продукции, данные которой приведены в таблице:  
Введем новые переменные LaTeX formula: y_1 , LaTeX formula: y_2 , …, LaTeX formula: y_m , которые назовем оценками ресурсов. Оценки должны быть установлены исходя из следующих соображений:
1) общая стоимость ресурсов должна быть минимизирована;
2) в случае продажи ресурса выручка должна быть не меньше стоимости продукции при организации производства.
Математическая модель задачи примет вид:
LaTeX formula: Y=(y_1;y_2;...y_m) ; (12.22)
LaTeX formula: min f(Y)=b_1y_1+b_2y_2+...+b_my_m ; (12.23)
LaTeX formula: \begin{cases} a_{11}y_1+a_{21}y_2+...+a_{m1}y_m\geq c_1, \\ a_{12}y_1+a_{22}y_2+...+a_{m2}y_m\geq c_2,\\ ... \\ a_{1n}y_1+a_{2n}y_2+...+a_{mn}y_m\geq c_n. \end{cases} (12.24)
LaTeX formula: y_j\geq 0, j=\overline{1,m} . (12.25)
Задачи 12.1 – 12.2 – 12.3 – 12.4 и 12.22 – 12.23 – 12.24 - 12.25 называют парой симметричных двойственных задач.
Если одна из двойственных задач имеет оптимальное решение, то и другая задача имеет оптимальное решение, причем оптимальные значения целевых функций совпадают
LaTeX formula: f(X^*)=f(Y^*) .
Канонический вид задачи 12.1 – 12.2 – 12.3 – 12.4 представлен формулами 12.2.1 – 12.3.1 – 12.4.1.
Канонический вид задачи 12.22 – 12.23 – 12.24 – 12.25:
LaTeX formula: min f(Y)=b_1y_1+b_2y_2+...+b_my_m+0\cdot y_{m+1}+0\cdot y_{m+2}+...+0\cdot y_{m+n}  ; (12.23.1)
LaTeX formula: \begin{cases} a_{11}y_1+a_{12}y_2+...+a_{1m}y_m-y_{m+1}= c_1, \\ a_{21}y_1+a_{22}y_2+...+a_{2m}y_m-y_{m+2}= c_2,\\ ... \\ a_{1n}y_1+a_{2n}y_2+...+a_{nm}y_m-y_{m+n}= c_n. \end{cases} (12.24.1)
LaTeX formula: y_j\geq 0, j=\overline{1,m+n} . (12.25.1)
Установим соответствие между переменными двойственных задач:
 LaTeX formula: \begin{matrix} x_1\leftrightarrow y_{m+1}\\ x_2\leftrightarrow y_{m+2}\\ ...\\ x_n\leftrightarrow y_{m+n}\\ x_{n+1}\leftrightarrow y_1\\ ...\\ x_{n+m}\leftrightarrow y_m \end{matrix} (12.26)
Значения переменных  LaTeX formula: y_j равны оценкам переменных LaTeX formula: x_i :
LaTeX formula: y_1=\Delta _{n+1} , LaTeX formula: y_2=\Delta _{n+2} , …, LaTeX formula: y_{n+1}=\Delta _{1} , …, LaTeX formula: y_{n+m}=\Delta _{n} . 
Прямая задача 12.1 – 12.2 – 12.3 – 12.4
1) основные переменные LaTeX formula: x_1 , LaTeX formula: x_2 , …, LaTeX formula: x_n  показывают объемы выпуска продукции; 
2) дополнительные переменные LaTeX formula: x_{n+1} , LaTeX formula: x_{n+2} , …, LaTeX formula: x_{n+m}  показывают остатки ресурсов.
Двойственная задача 12.22 – 12.23 – 12.24 – 12.25
1) основные переменные LaTeX formula: y_1 , LaTeX formula: y_2 , …, LaTeX formula: y_m  показывают, насколько увеличится значение целевой функции, при использовании в процессе производства дополнительной единицы соответствующего ресурса; 
2) дополнительные переменные LaTeX formula: y_{m+1} , LaTeX formula: y_{m+2} , …, LaTeX formula: y_{m+n}  показывают, насколько уменьшится значение целевой функции при условии дополнительного выпуска одной единицы соответствующей продукции.
Пример 1. Решите симплексным методом задачу линейного программирования: 
LaTeX formula: maxf(X)=16x_1+9x_2+4x_3+6x_4  ; 
 LaTeX formula: \begin{cases} 4x_1+x_2+3x_4\leq 200,\\ 2x_1+3x_2+4x_3\leq 300; \end{cases}   LaTeX formula: x_i\geq 0, i=\overline{1,4} 
Выполните послеоптимизацонный анализ.
Решение. Приведем модель задачи к каноническому и предпочтительному виду: 
LaTeX formula: maxf(X)=16x_1+9x_2+4x_3+6x_4+0x_5+0x_6  ;  LaTeX formula: \begin{cases} 4x_1+x_2+3x_4+\underline{x_5}=200,\\ 2x_1+3x_2+4x_3+\underline{x_6}=300. \end{cases}
Базисные переменные: LaTeX formula: x_5=200 , LaTeX formula: x_6=300 .
Свободные переменные: LaTeX formula: x_{1}=0 , LaTeX formula: x_{2}=0 , LaTeX formula: x_{3}=0 , LaTeX formula: x_{4}=0 .
Составим симплексную таблицу и выполним симплексные преобразования: 
Пояснения к нулевой итерации
По формуле 12.18 получим: LaTeX formula: \Delta_0 =0\cdot 200+0\cdot 300=0 .
По формуле 12.19 получим:
LaTeX formula: \Delta _1=0\cdot 4+0\cdot 2-16=-16 ; LaTeX formula: \Delta _2=0\cdot 1+0\cdot 3-9=-9 ; 
LaTeX formula: \Delta _3=0\cdot 0+0\cdot 4-4=-4 ; LaTeX formula: \Delta _4=0\cdot 3+0\cdot 0-6=-6 ; 
LaTeX formula: \Delta _5=0\cdot 1+0\cdot 0-0 =0 ; LaTeX formula: \Delta _6=0\cdot 0+0\cdot 1-0 =0 .
Поскольку присутствуют отрицательные оценки переменных, то опорный план задачи не оптимальный. В качестве разрешающего столбца выбираем столбец LaTeX formula: A_1, так как переменная  LaTeX formula: x_1 имеет наименьшую оценку. 
По формуле 12.20 находим симплексные отношения: LaTeX formula: \theta _1=200:4=50 ; LaTeX formula: \theta _2=300:2=150 . 
Так как LaTeX formula: \theta _2<\theta _1 , то первая строка будет разрешающей. Разрешающий элемент LaTeX formula: a_{PP}=4 .
Пояснения к первой итерации. Вносим изменения в базис: переменную LaTeX formula: x_5  заменяем переменной LaTeX formula: x_1 . Все элементы разрешающей строки нулевой итерации делим на LaTeX formula: a_{PP}=4  и результаты записываем в первую строку первой итерации. Элемент  LaTeX formula: a^1_{21} считаем равным нулю. Остальные элементы второй строки находим по формуле 12.21 (рис. 12.5): 
LaTeX formula: a^1_{20}=\frac{300\cdot 4-200\cdot 2}{4}=200 , LaTeX formula: a^1_{22}=\frac{3\cdot 4-2\cdot 1}{4}=2,5 , LaTeX formula: a^1_{23}=\frac{4\cdot 4-2\cdot 0}{4}=4 , 
LaTeX formula: a^1_{24}=\frac{0\cdot 4-2\cdot 3}{4}=-1,5 , LaTeX formula: a^1_{25}=\frac{0\cdot 4-2\cdot 1}{4}=-0,5 , LaTeX formula: a^1_{26}=\frac{1\cdot 4-2\cdot 0}{4}=1 .
Заполняем индексную строку. По формуле 12.18 получим: LaTeX formula: \Delta _0=16\cdot 50+0\cdot 200=800  .
По формуле 12.19 получим:
LaTeX formula: \Delta _1=0 ; LaTeX formula: \Delta _2=16\cdot 0,25+0\cdot 2,5-9=-5 ; LaTeX formula: \Delta _3=16\cdot 0+0\cdot 4-4=-4 ; 
LaTeX formula: \Delta _4=16\cdot 0,75-0\cdot1,5-6=6 ; LaTeX formula: \Delta _5=16\cdot 0,25-0\cdot 0,5-0=4 ; LaTeX formula: \Delta _6=0 .
Поскольку присутствуют отрицательные оценки переменных, то опорный план задачи не оптимальный. В качестве разрешающего столбца выбираем столбец LaTeX formula: A_2, так как переменная  LaTeX formula: x_2 имеет наименьшую оценку. 
По формуле 12.20 находим симплексные отношения: LaTeX formula: \theta _1=50:0,25=200 ; LaTeX formula: \theta _2=200:2,5=80 . Так как LaTeX formula: \theta _2<\theta _1 , то вторая строка будет разрешающей.  Разрешающий элемент LaTeX formula: a_{PP}=2,5 .
Вторая итерация. Аналогично заполняем таблицу второй итерации. Поскольку все оценки переменных неотрицательные, то опорный план второй итерации оптимальный: 
LaTeX formula: X^*=(16;80;0;0;0;0) ; LaTeX formula: f(X^*)=1200 ден. ед.
Послеоптимизационный анализ
На основании 12.26 установим соответствие между двойственными переменными:
 LaTeX formula: \begin{matrix} x_1\leftrightarrow y_3\\ x_2\leftrightarrow y_4\\x_3\leftrightarrow y_5\\ x_4\leftrightarrow y_6\\ x_5\leftrightarrow y_1\\ x_6\leftrightarrow y_2 \end{matrix}
Следовательно, LaTeX formula: y_1=\Delta _5=3 , LaTeX formula: y_2=\Delta _6=2 , LaTeX formula: y_3=\Delta _1=0 , LaTeX formula: y_4=\Delta _2=0 , LaTeX formula: y_5=\Delta _3=4 , LaTeX formula: y_6=\Delta _4=3 .
План выпуска продукции: продукцию первого вида выпускаем в объеме LaTeX formula: 16 ед, второго вида – в объеме LaTeX formula: 80 ед., продукцию третьего и четвертого видов выпускать не следует.
Оптимальное значение целевой функции (максимальная выручка) составит LaTeX formula: 1200 ден. ед.
Оценки ресурсов: каждая использованная единица первого ресурса увеличивает доход на LaTeX formula: 3 ден. ед., а каждая единица второго ресурса – на LaTeX formula: 2 ден. ед. Первая и вторая продукция не убыточные. Выпуск одной единицы продукции третьего вида приносит убыток в размере LaTeX formula: 4 ден. ед., а четвертого – в размере LaTeX formula: 3 ден. ед. 
Пример 2. Решите симплексным методом задачу линейного программирования:
LaTeX formula: minf(X)=3x_1+2x_2  ; LaTeX formula: \begin{cases} -3x_1+5x_2\leq 5,\\ 4x_1+5x_2\geq 40; \end{cases}   LaTeX formula: x_1\geq 0, x_2\geq 0 .   
Решение. Приведем модель задачи к каноническому виду: 
 LaTeX formula: minf(X)=3x_1+2x_2+0 \cdot x_3+0 \cdot x_4 ; 
LaTeX formula: \begin{cases} -3x_1+5x_2+x_3=5,\\ 4x_1+5x_2-x_4+= 40. \end{cases}
Приведем модель задачи к предпочтительному виду: 
LaTeX formula: minf(X)=3x_1+2x_2+0 \cdot x_3+0 \cdot x_4+M\omega  ; 
 LaTeX formula: \begin{cases} -3x_1+5x_2+\underline{x_3}=5,\\ 4x_1+5x_2-x_4+\underline{\omega}= 40. \end{cases}
Базисные переменные: LaTeX formula: x_3=5 , LaTeX formula: \omega=40 .
Свободные переменные: LaTeX formula: x_{1}=0 , LaTeX formula: x_2=0 , LaTeX formula: x_4=0 .
Составим симплексную таблицу и выполним симплексные преобразования: 
Пояснения к нулевой итерации
По формуле 12.18 получим: LaTeX formula: \Delta _0=0\cdot 5+M\cdot 40=40M .
По формуле 12.19 получим:
LaTeX formula: \Delta _1=0\cdot (-3)+M\cdot 4-3=4M-3 ; LaTeX formula: \Delta _2=0\cdot 5+M\cdot 5-2=5M-2 ; 
LaTeX formula: \Delta _3=0\cdot 1+M\cdot 0-0=0 ; LaTeX formula: \Delta _4=0\cdot 0-M\cdot 1-0=-M ; LaTeX formula: \Delta _5=0\cdot 0+M\cdot 1-M=0 .
Поскольку присутствуют положительные оценки переменных, то опорный план задачи не оптимальный. В качестве разрешающего столбца выбираем столбец LaTeX formula: A_2, так как переменная  LaTeX formula: x_2 имеет наибольшую оценку. 
По формуле 12.20 находим симплексные отношения: LaTeX formula: \theta _1=5:5=1 ; LaTeX formula: \theta _2=40:5=8 . 
Так как LaTeX formula: \theta _1<\theta _2 , то первая строка будет разрешающей. Разрешающий элемент LaTeX formula: a_{PP}=5 .
Пояснения к первой итерации. Вносим изменения в базис: переменную LaTeX formula: x_3  заменяем переменной LaTeX formula: x_2 . Все элементы разрешающей строки нулевой итерации делим на LaTeX formula: a_{PP}=5  и результаты записываем в первую строку первой итерации. Элемент  LaTeX formula: a^1_{22} считаем равным нулю. Остальные элементы второй строки находим по формуле 12.21 (рис. 12.5): 
LaTeX formula: a^1_{20}=\frac{40\cdot 5-5\cdot 5}{5}=35 , LaTeX formula: a^1_{21}=\frac{4\cdot 5+3\cdot 5}{5}=7 , LaTeX formula: a^1_{23}=\frac{0\cdot 5-1\cdot 5}{5}=-1 , 
LaTeX formula: a^1_{24}=\frac{-1\cdot 5-0\cdot 5}{5}=-1 , LaTeX formula: a^1_{25}=\frac{1\cdot 5-0\cdot 5}{5}=1 .
Заполняем индексную строку. По формуле 12.18 получим:  LaTeX formula: \Delta _0=2\cdot 1+M\cdot 35=35M+2 .
По формуле 12.19 получим: LaTeX formula: \Delta _1=2\cdot (-0,6)+M\cdot 7-3=7M-4,2 ; LaTeX formula: \Delta _2=2\cdot 1+M\cdot 0-2=0 ; LaTeX formula: \Delta _3=2\cdot 0,2-M\cdot 1-0=-M+0,4 ; LaTeX formula: \Delta _4=2\cdot 0-M\cdot 1-0=-M ; LaTeX formula: \Delta _5=2\cdot 0+M\cdot 1-M=0 .
Поскольку оценка переменной LaTeX formula: x_1  положительная, то опорный план задачи не оптимальный. В качестве разрешающего столбца выбираем столбец LaTeX formula: A_1
Так как отрицательный элемент разрешающего столбца не образует симплексного отношения, то вторая строка будет разрешающей.  Разрешающий элемент LaTeX formula: a_{PP}=7 .
Вторая итерация. Аналогично заполняем таблицу второй итерации. Поскольку все оценки переменных неположительные, то опорный план второй итерации оптимальный: LaTeX formula: x_1=5 , LaTeX formula: x_2=4 , LaTeX formula: f^*(5;4)=23 . 
ОтветLaTeX formula: X^*=(5;4) ; LaTeX formula: f(X^*)=23 .
1. Оценки базисных переменных всегда равны нулю.
2. Отрицательные элементы разрешающего столбца и элементы, равные нулю, не образуют симплексных отношений.
3. Задача с искусственным базисом называется М-задачей. При решении М-задачи по мере выведения искусственных переменных из базиса они выводятся и из симплексной таблицы.
4. Графическое решение Примера 2 приведено в разделе Графический метод / Примеры.

formula