Симплексный метод /qualihelpy

Симплексный метод

Справочник / Студент / Линейное программирование /

Справочный материал Примеры Обратите внимание! Видео Модели Пройти тесты

Предпочтительный вид модели ЗЛП

Каноническая модель ЗЛП имеет предпочтительный вид, если в каждом из уравнений системы ограничений присутствует предпочтительная переменная.

Переменная называется предпочтительной, если она присутствует только в одном из уравнений системы ограничений и только с коэффициентом, равным единице.

Н а п р и м е р, рассмотрим задачу:

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: -M

, а в случае минимизации – с коэффициентом, равным LaTeX formula: +M

Н а п р и м е р, рассмотрим задачу:

; $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: \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}$ .

Построение начального опорного плана задачи

Рассмотрим задачу:

. ( 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

, …,

, которые назовем оценками ресурсов.
Оценки должны быть установлены исходя из следующих соображений:

1) общая стоимость ресурсов должна быть минимизирована;

2) в случае продажи ресурса выручка должна быть не меньше стоимости продукции при организации производства.

Математическая модель задачи примет вид:

; (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 называют парой симметричных двойственных задач.

Если одна из двойственных задач имеет оптимальное решение, то и другая задача имеет оптимальное решение, причем оптимальные значения целевых функций совпадают:

Канонический вид задачи 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

, …,

показывают объемы выпуска продукции;

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

, …,

показывают, насколько увеличится значение целевой функции, при использовании в процессе производства дополнительной единицы соответствующего ресурса;

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_{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)

;

ден. ед.

Послеоптимизационный анализ

На основании 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: \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

Составим симплексную таблицу и выполним симплексные преобразования:

Пояснения к нулевой итерации.

По формуле 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

Ответ:

;

1. Оценки базисных переменных всегда равны нулю.

2. Отрицательные элементы разрешающего столбца и элементы, равные нулю, не образуют симплексных отношений.

3. Задача с искусственным базисом называется М-задачей. При решении М-задачи по мере выведения искусственных переменных из базиса они выводятся и из симплексной таблицы.

4. Графическое решение Примера 2 приведено в разделе Графический метод / Примеры.

Программа для просмотра моделей (МК-плеер) Файлы для скачивания

Симплексный метод