4. Двойственный симплексный метод

Двойственный симплексный метод используется для решения задачи линейного программирования, записанной в форме основной задачи, среди векторов которой имеется m единичных, свободные члены b_i принимают любые значения, а система ограничений задана в виде неравенств смысла «≥», либо смешанных неравенств «≥», «≤», «=».

Если в симплексном методе оптимальный план получается в результате перехода от одного опорного плана к другому, то в двойственном симплексном методе – в результате движения по псевдопланам.

Определение 1

У словно-оптимальным планом или псевдопланом называется план, в котором удовлетворяется признак оптимальности (все коэффициенты индексной строки _j ≤ 0 при решении на максимум и все _j ≤ 0 при решении на минимум целевой функции), а среди значений столбца свободных членов bi имеются отрицательные числа.

Алгоритм двойственной симплексного метода включает следующие этапы.

1. Составление псевдоплана.

Систему ограничений исходной задачи приводим к системе неравенств смысла «≤». Для этого обе части неравенств смысла «≥» умножаем на (-1). Если ограничение исходной задачи задано в виде равенства, необходимо представить его в виде системы двух неравенств противоположного смысла.

От полученной системы неравенств смысла «≤» переходим к системе уравнений, вводя неотрицательные дополнительные переменные, которые становятся базисными. Разрешаем систему уравнений относительно базисных переменных и первый опорный план заносим в симплексную таблицу. Индексную строку таблицы заполняем коэффициентами целевой функции, взятыми с противоположными знаками.

2. Проверка плана.

Если в полученном опорном плане условие оптимальности не выполняется, то осуществляем симплексную процедуру (см. стр.24). В этом случае существует следующее правило: при расчете значений столбца Ө отрицательные значения свободных членов b_i делятся только на отрицательные коэффициенты направляющего столбца, положительные значения b_i – на положительные коэффициенты a_ik, а в строке, имеющей разноименные знаки b_i и a_ik значения Ө_i на существует.

3. Определение направляющих (разрешающих) строки и столбца.

Среди отрицательных значений столбца свободных членов b_i выбираем наибольшее по абсолютной величине. Строка, соответствующая этому значению, является направляющей (i = r).

Симплексную таблицу дополняем строкой Ө, в которую заносим результаты деления, взятые по абсолютной величине, коэффициентов индексной строки на соответствующие отрицательные коэффициенты направляющей строки. В столбцах, имеющих значения a_rj ≥ 0, Ө_j не существует. Столбец с минимальным значением Ө_j является направляющим. Разрешающий элемент находится на пересечении направляющих строки и столбца симплексной таблицы и в двойственном симплексном методе он всегда отрицательный.

4. Определение нового опорного плана.

Новый опорный план получаем в результате пересечения симплексной таблицы методов Жордана-Гаусса (см. стр.24) и далее переходим к этапу 2 алгоритма.

Решение задачи продолжаем до получения оптимального плана.

Е сли все коэффициенты направляющей строки положительны, т.е. a_rj ≥ 0, то задача не имеет решения, так как в этом случае Ө_j, (j = 1, n+m) не существует.

ПРИМЕР

О пределить Х = (Х₁,Х₂,Х₃), который удовлетворяет условиям

Х₁ + Х₂ + 2Х₃ ≥ 12,

Х₁ – Х₂ + 8Х₃ ≥ 6, (4.1)

Х₁ – Х₂ + X₃ ≤ 7.

Х₁ ≥ 0, х₂ ≥ 0, х₃ ≥ 0 (4.2)

и доставляет максимальное значение целевой функции

L (X) = 200 – 5X₁ = 8X₂ – 11X₃ → max. (4.3)

С истему ограничений (4.1) приведем к системе неравенств смысла «≤», умножив обе части 1 и 2 неравенств на (-1).

-Х₁ – Х₂ – 2Х₃ ≤ -12,

-Х₁ + 3Х₂ – 8Х₃ ≤ -6, (4.4)

Х₁ - Х₂ + Х₃ ≤ 7.

П ерейдем к системе уравнений:

-Х₁ – Х₂ – 2Х₃ + Х₄ = -12,

-Х₁ + 3Х₂ – 8Х₃ + Х₅ = -6, (4.5)

Х₁ – Х₂ + Х₃ + Х₆ = 7.

За базис выбираем систему векторов А₄,А₅,А₆, так как эти векторы единичные и линейно независимые. Соответствующие единичным векторам переменные Х₄,Х₅,Х₆ являются базисными.

Р азрешим систему уравнений (4.5) относительно базисных переменных

Х₄ = -12 – (-Х₁ – Х₂ – 2Х₃),

Х₅ = -6 – (– Х₁ –3Х₂ – 8Х₃), (4.6)

Х₆ = 7 – (– Х₁ – Х₂ + Х₃).

Функцию цели запишем в виде:

L (x) = 200 – (5X₁ + 8X₂ + 11X₃). (4.7)

Полагая, что свободные переменные Х₁ – Х₂ = Х₃ = 0, получим первый опорный план, который заносим в симплексную таблицу 5.1.

Х ₁° = (0, 0, 0, -12, -6, 7), L(X₁°) = 200.

В таблице 5.1 получен псевдоплан или условно-оптимальный план, так как условие оптимальности в индексной строке выполняется, а в столбце свободных членов имеются отрицательные значения. Следовательно, переходим к следующему этапу алгоритма-определению направляющих строки и столбца.

Среди отрицательных значений столбца свободных членов выбираем наибольший по абсолютной величине. Так как |-12| > |-6|, то первая строка, соответствующая переменной х₄, является направляющей, а переменную х₄ нужно вывести из базиса.

Д ля выбора направляющего столбца коэффициенты индексной строки делим на соответствующие коэффициенты направляющей строки:

= 5; = 8; = 5,5.

Результаты деления, взятые по абсолютной величине, заносим в строку Ө. Из полученных значений Ө_j выбираем min {5; 8; 5,5} = 5, которое соответствует Первову столбцу с переменной х₁. Данный столбец является направляющим, а переменную х₁ следует ввести а базис. На пересечении направляющих строка и столбца находится разрешающий элемент, равный (-1). Далее выполняем преобразование симплексной таблицы методов Жордана-Гаусса и заполняем таблицу 5.2.

Таблица 5

	Базисные перемен-ные	Свободные члены (зна-чения баз. переменных	Х 1	Х2	Х3	Х4	Х5	Х6
Таблица 5.1	←Х4	-12	-1	-1	-2	1	0	0
	Х5	-6	-1	3	-8	0	1	0
	Х6	7	1	-1	1	0	0	1
	L (X1)	200	5	8	11	0	0	0
	Ө		5	8	5,5	-	-	-
Таблица 5.2	X1	12	1	1	2	-1	0	0
	X5	6	0	4	- 6	-1	1	0
	←X6	-5	0	-2	- 1	1	0	1
	L (X2)	140	0	3	-1	5	0	0
	Ө		-	1,5	1	-	-	-
Таблица5.3	X1	2	1	-3	0	1	0	-2
	X5	36	0	16	0	-7	1	-6
	X3	5	0	2	1	-1	0	-1
	L(X3)	135	0	1	0	6	0	1

Третий опорный план (табл. 5.3) является оптимальным, так как в индексной строке условие оптимальности выполняется и все значения базисных переменных – положительные числа:

Х * = (2; 0; 5; 0; 36; 0), L(X*) = 135. ереходим к системе уравнений, вводя неотрицательные е равенства, неоходимо представить его в виде системы двух неравенств прот

КОНТРОЛЬНЫЕ ЗАДАНИЯ (№ 139+207).

Решить двойственным симплексным методом.

139. 8X₁+3X₂ ≥ 24, 140. 3X₁ + X₂ ≥ 3 _,

3X₁+7X₂≤ 21, 3 X₁ +4 X₂ ≤ 24,

X₁−10X₂ ≤ 0, 5 X₁ −12 X₂ ≤ 20,

0≤ X₁≤5, 7 X₁ − X₂ ≥ 0,

X₂ ≥ 0. X₁ ≥ 0 ,X₂ ≥ 0.

_͟

_͟

L(X) = −2 X₁ +20 X₂ →extr L(X) = 15X₁ +5 X₂ →extr

141. . 4X₁+3X₂ ≤ 24, 142. 5X₁ + 9X₂ ≤ 3 _,

X₁−X₂≤ −3, 3 X₁− 4 X₂ ≥ ,

3X₁−5X₂ ≤ 6, 5 X₁ + 12 X₂ ≥ −6,

0≤ X₁≤3, 0≤ X₁ ≤ 7,

X₂ ≥ 0. X₂ ≥ 0.

_{͟ ͟}

L(X) = −2 X₁ +2 X₂ →extr L(X) = −3 X₁ +18X₂ →extr

143. 2X₁+7X₂ ≥ 14, 144. 4X₁ + X₂ ≥ 5 _,

X₁+X₂≤ 9, X₁− 7X₂ ≤ 0 ,

6X₁−X₂ ≥ 0, 9X₁ + 5 X₂ ≥ −6,

X₁ ≥ 0, 0≤ X₁ ≤ 4,

0≤ X₂ ≤ 5. X₂ ≥ 0.

_{͟ ͟}

L(X) = −3 X₁ + 0,5X₂ →extr L(X) = 18 X₁ +10X₂ →extr

145. X₁−2X₂ ≤ 0, 146. 9X₁ +7 X₂ ≤ 63 _,

3X₁ − X ₂≥ − 3, − 2X₁+3X₂ ≤ 6 ,

3X₁+ X₂ ≤ 15, X₁ + 5 X₂ ≥ 5,

X₁ ≥ 0, X₁ ≥ 0,

0≤ X₂ ≤ 6. 0 ≤ X₂ ≤ 3.

_{͟ ͟}

L(X) = −9 X₁ + 3X₂ →extr L(X) = 3 X₁ +15X₂ →extr

147. X₁+2X₂ ≥6, 148 . X₁ +8X₂ ≥ 8 _,

7X₁ +9X ₂≤ 63, X₁+ X₂ ≤ 9 ,

3X₁−X₂ ≥0, -2X₁ + 3X₂ ≤ 7,

0 ≤ X₁ ≤ 7, X₁ ≥ 0,

X₂ ≥ 0. 0 ≤ X₂ ≤ 4.

_{͟ ͟}

L(X) = 3X₁ + 6X₂ →extr L(X) = -2X₁ -2X₂ →extr

149. 5X₁+X₂ ≤ 20, 150 . 6 X₁ +9X₂ ≥ 8 _,

3X₁− X ₂≥ −4, 3X₁−2X₂ ≥ −10,

3X₁+ 8X₂ ≥ 9, X₁ + X₂ ≤ 8,

X₁ ≥ 0, X₁ −6 X₂ ≤ 0,

X₂ ≥ 0. X_1, X₂ ≥0.

_{͟ ͟}

L(X) = 9X₁−3 X₂ →extr L(X) = -2X₁ +12X₂ →extr

151. 5X₁−X₂ ≥0, 152 . X₁ − X₂ ≤ 0_,

X₁ −3X₂≤ 0, 3X₁+ 2X₂ ≤ 20 ,

6X₁ +11X₂≤ 60, 3X₁ + X₂ ≥3,

X₁ ≥ 0, 0 ≤ X₁ ≤ 3,

0 ≤ X₂≤ 5. X₂ ≥ 0.

_{͟ ͟}

L(X) = 3X₁ + 5,5X₂ →extr L(X) = -2X₁ +2X₂ →extr

153. -X₁+X₂ ≤ 3, 154 . X₁-4X₂ ≤ 0 _,

X₁+4 X ₂ ≥ 7, X₁+X₂ ≤7,

2X₁+ 3X₂≤ 20, 4 X₁− X₂ ≥ −12 ,

0 ≤ X₁ ≤ 8, X₁ ≥0,

X₂ ≥ 0. 0 ≤X₂ ≤5.

_{͟ ͟}

L(X) = 3X₁+ 4,5 X₂ →extr L(X) = -2X₁ +1,5X₂ →extr

155. 2X₁−3X₂ ≤ 6, 156 . −7 X₁+2X₂ ≤ 14 _,

X₁+3 X ₂ ≥ 3, 2X₁+X₂ ≤10,

2X₁−X₂≤ 0, 3X₁+5 X₂ ≥ 15 ,

0 ≤ X₁ ≤ 4, X₁ ≥0,

X₂ ≥ 0. 0 ≤X₂ ≤8.

_{͟ ͟}

L(X) = −X₁+ 0,5 X₂ →extr L(X) = 10X₁ +5X₂ →extr

157. 3X₁−X₂ ≥0, 158 . 4 X₁ +3 X₂ ≤ 24,

X₁ −X₂≤ 3, X₁−X₂ ≥ −4,

5X₁ +2X₂≤ 20, X₁ −X₂ ≤ 0,

X₁ ≥ 0, X₁ ≥ 0,

0 ≤ X₂≤ 4. 2 ≤ X₂ ≤ 5.

_{͟ ͟}

L(X) = −4X₁ + 4X₂ →extr L(X) = -2X₁−1,5 X₂ →extr

159. −X₁+2X₂ ≥ −2, 160 . 3X₁ −2 X₂ ≥ −6,

5X₁ −X₂≥−5, X₁−8X₂ ≤ 0,

2X₁ +X₂≤ 8, 2X₁ +X₂ ≥ 2,

X₁ + X₂ ≥ 2, 0 ≤ X₁ ≤ 3,

X_1, X₂ ≥ 0. X₂ ≥ 0.

_{͟ ͟}

L(X) = −10X₁ + 2X₂ →extr L(X) = -2X₁+16 X₂ →extr

161. X₁+2X₂ ≥ 4, 162. 3X₁ −4 X₂ ≥ −12,

7X₁ +X₂≥7, 5X₁−4X₂ ≤ 25,

X₁ +5X₂≥ 10, 3X₁ +X₂ ≥ 3,

3 X₁ + X₂ ≤ 15, X_1, X₂ ≤ 0,

X_1, X₂ ≥ 0. X₁ + X₂ ≥ 0.

_{͟ ͟}

L(X) = 4X₁ + 4X₂ →extr L(X) = -15X₁+20 X₂ →extr

163. X₁−3X₂ ≤ 0, 164 . 7X₁ +3 X₂ ≥21,

2X₁ +3X₂≤ 30, 7X₁+6X₂≤ 42,

4X₁ +X₂ ≥ 4, 4X₁ −X₂ ≥ 0,

X₁ ≥ 0, 0 ≤ X₁ ≤ 6,

0 ≤ X₂≤ 8. X₂ ≥ 0.

_{͟ ͟}

L(X) = X₁ + 1,5X₂ →extr L(X) = -12X₁+ 3X₂ →extr

165. − X₁+X₂ ≥ − 3, 166. 3X₁ +X₂ ≥ 5,

7X₁ −X₂≥ 0, 3X₁−X₂ ≥ 0,

3X₁ +2X₂≥ 6, X₁ −4 X₂ ≥ 0,

5X₁ + X₂ ≤ 15, 0 ≤ X₁ ≤ 3,

X_1, X₂ ≥ 0. X₂ ≥ 0.

_{͟ ͟}

L(X) = − 14X₁ + 2X₂ →extr L(X) = -2X₁+8X₂ →extr

167. 2X₁+5X₂ ≥ 12, 168. 4X₁ +5X₂ ≤ 50,

4X₁ −3X₂≥ −12, 3X₁+X₂ ≥ 0,

3X₁ +4X₂ ≤ 24, X₁ −4 X₂ ≤ 0,

0 ≤ X₁ ≤ 7, X₁ ≥ 0,

X₂ ≥ 0. 0 ≤ X₂≤ 5.

_{͟ ͟}

L(X) = − 3X₁ − 4X₂ →extr L(X) = -3X₁+12X₂ →extr

169. 3X₁ − X₂ ≥ 0, 170. X₁ +X₂ ≤ 5,

X₁ +3X₂≥ 3, 3X₁−2X₂ ≥ − 6,

− X₁ +5X₂≥ − 5 , X₁ −3X₂ ≤ 0 ,

3X₁ + 7X₂ ≤ 21, X₁ ≥ 0 ,

X_1, X₂ ≥ 0. 0 ≤ X₂ ≤ 4.

_{͟ ͟}

L(X) = − 3X₁ + X₂ →extr L(X) = -1,5X₁+X₂ →extr

171. X₁− X₂ ≤ 2, 172. 4X₁ +X₂ ≥ 5,

− X₁ +2X₂≤ 4, 4X₁−X₂ ≥ 0,

5X₁− X₂≥ 0, X₁ −3 X₂ ≤ 6,

0 ≤ X₁ ≤ 5, 3 X₁ + 4 X₂ ≤ 24,

X₂ ≥ 0. X_1,X₂ ≥ 0.

_{͟ ͟}

L(X) = 3X₁− 6X₂ →extr L(X) = -2X₁+6X₂ →extr

173. − X₁+X₂ ≥ − 3, 174. −X₁+2X₂ ≤ 4,

X₁ −7X₂ ≤ 0, X₁+3X₂ ≥ 3,

X₁ +X₂≤ 6, 5X₁ +8 X₂ ≤ 4 0,

− 5X₁ + 2X₂ ≤ 5, X₁ ≥ 0 ,

X_1, X₂ ≥ 0. 0≤ X₂≤5.

_{͟ ͟}

L(X) = 4X₁− 4X₂ →extr L(X) = -10X₁−16X₂ →extr

175. 2X₁−X₂ ≥ − 4, 176. 2X₁− X₂ ≥ 0,

3X₁ +X₂≥ 3, 6X₁+X₂ ≥ 6,

X₁− 2X₂≤ 5, X₁ −2 X₂ ≤ 2,

4X₁ + 5X₂ ≤ 32, 0 ≤ X₁ ≤ 6,

X_1, X₂ ≥ 0. X₂ ≥ 0.

_{͟ ͟}

L(X) = 3X₁−1,5 X₂ →extr L(X) = -4X₁+2X₂ →extr

177. 5X₁−X₂ ≥ − 10, 178. − 3X₁ +2X₂≤ 6,

X₁ +X₂≤ 7, X₁−8X₂ ≤0,

X₁ −2X₂ ≤0, 3X₁ +2 X₂ ≤18,

X₁ ≥ 0, − X₁ + X₂ ≥ 5,

0 ≤ X₂ ≤ 6. X₁ ,X₂ ≥ 0.

_{͟ ͟}

L(X) = 2,5X₁ −X₂ →extr L(X) = -5X₁+5X₂ →extr

179. X₁−X₂ ≥ − 5, 180. 4X₁ +3X₂ ≤24,

3X₁ +2X₂≥ 6, X₁−2X₂ ≤3,

2X₁− X₂≤ 0, 4 X₁ −3 X₂ ≥ 0,

X₁ ≥0, 5 X₁+ X₂ ≥5,

0 ≤ X₂ ≤ 6. X₁ ,X₂ ≥ 0.

_{͟ ͟}

L(X) = 3X₁−3 X₂ →extr L(X) = -3X₁+6X₂ →extr

181. 2X₁+7X₂ ≥ 14, 182. X₁− 5X₂≤ 0,

X₁ −X₂ ≥ −4 , 3X₁−4X₂ ≥ − 12,

X₁ − 7X₂≤ 0, 3X₁ +4 X₂ ≤ 30,

0 ≤ X₁ ≤ 6, 2X₁+ X₂ ≥2,

X₂ ≥ 0. X_1,X₂ ≥ 0.

_{͟ ͟}

L(X) = − 2X₁ + 14X₂ →extr L(X) = -6X₁−3X₂ →extr

183. −3X₁+8X₂ ≥ − 8, 184. 3X₁ +X₂ ≥ 6,

8X₁ −X₂≥ 0, 3X₁−7X₂ ≤ 0,

9X₁ +5X₂≤ 45, X₁ +X₂ ≤ 8,

X₁ ≥ 0, 0 ≤ X₁ ≤ 4,

0 ≤ X₂ ≤ 0. X₂ ≥ 0.

_{͟ ͟}

L(X) = 1,5X₁ -4X₂ →extr L(X) = -6X₁+14X₂ →extr

185. X₁+2X₂ ≥ 4, 186. 3X₁ −4 X₂ ≥ −12,

7X₁ +X₂≥7, 5X₁−4X₂ ≤ 25,

X₁ +5X₂≥ 10, 3X₁ +X₂ ≥ 3,

3 X₁ + X₂ ≤ 15, X_1, X₂ ≤ 0,

X_1, X₂ ≥ 0. X₁ + X₂ ≥ 0.

_{͟ ͟}

L(X) = 4X₁ + 4X₂ →extr L(X) = -15X₁+20 X₂ →extr

187. X₁+2X₂ ≥6, 188 . X₁ +8X₂ ≥ 8 _,

7X₁ +9X ₂≤ 63, X₁+ X₂ ≤ 9 ,

3X₁−X₂ ≥0, -2X₁ + 3X₂ ≤ 7,

0 ≤ X₁ ≤ 7, X₁ ≥ 0,

X₂ ≥ 0. 0 ≤ X₂ ≤ 4.

_{͟ ͟}

L(X) = 3X₁ + 6X₂ →extr L(X) = -2X₁ -2X₂ →extr

189. 5X₁+X₂ ≤ 20, 190 . 6 X₁ +9X₂ ≥ 8 _,

3X₁− X ₂≥ −4, 3X₁−2X₂ ≥ −10,

3X₁+ 8X₂ ≥ 9, X₁ + X₂ ≤ 8,

X₁ ≥ 0, X₁ −6 X₂ ≤ 0,

X₂ ≥ 0. X_1, X₂ ≥0.

_{͟ ͟}

L(X) = 9X₁−3 X₂ →extr L(X) = -2X₁ +12X₂ →extr

191. 5X₁−X₂ ≥0, 192. X₁ − X₂ ≤ 0_,

X₁ −3X₂≤ 0, 3X₁+ 2X₂ ≤ 20 ,

6X₁ +11X₂≤ 60, 3X₁ + X₂ ≥3,

X₁ ≥ 0, 0 ≤ X₁ ≤ 3,

0 ≤ X₂≤ 5. X₂ ≥ 0.

_{͟ ͟}

L(X) = 3X₁ + 5,5X₂ →extr L(X) = -2X₁ +2X₂ →extr

193. -X₁+X₂ ≤ 3, 194 . X₁-4X₂ ≤ 0 _,

X₁+4 X ₂ ≥ 7, X₁+X₂ ≤7,

2X₁+ 3X₂≤ 20, 4 X₁− X₂ ≥ −12 ,

0 ≤ X₁ ≤ 8, X₁ ≥0,

X₂ ≥ 0. 0 ≤X₂ ≤5.

_{͟ ͟}

L(X) = 3X₁+ 4,5 X₂ →extr L(X) = -2X₁ +1,5X₂ →extr

195. 2X₁−3X₂ ≤ 6, 196 . −7 X₁+2X₂ ≤ 14 _,

X₁+3 X ₂ ≥ 3, 2X₁+X₂ ≤10,

2X₁−X₂≤ 0, 3X₁+5 X₂ ≥ 15 ,

0 ≤ X₁ ≤ 4, X₁ ≥0,

X₂ ≥ 0. 0 ≤X₂ ≤8.

_{͟ ͟}

L(X) = −X₁+ 0,5 X₂ →extr L(X) = 10X₁ +5X₂ →extr

197. − X₁+X₂ ≥ − 3, 198. 3X₁ +X₂ ≥ 5,

7X₁ −X₂≥ 0, 3X₁−X₂ ≥ 0,

3X₁ +2X₂≥ 6, X₁ −4 X₂ ≥ 0,

5X₁ + X₂ ≤ 15, 0 ≤ X₁ ≤ 3,

X_1, X₂ ≥ 0. X₂ ≥ 0.

_{͟ ͟}

L(X) = − 14X₁ + 2X₂ →extr L(X) = -2X₁+8X₂ →extr

199. X₁− X₂ ≤ 2, 200. 4X₁ +X₂ ≥ 5,

− X₁ +2X₂≤ 4, 4X₁−X₂ ≥ 0,

5X₁− X₂≥ 0, X₁ −3 X₂ ≤ 6,

0 ≤ X₁ ≤ 5, 3 X₁ + 4 X₂ ≤ 24,

X₂ ≥ 0. X_1,X₂ ≥ 0.

_{͟ ͟}

L(X) = 3X₁− 6X₂ →extr L(X) = -2X₁+6X₂ →extr

201. − X₁+X₂ ≥ − 3, 202. −X₁+2X₂ ≤ 4,

X₁ −7X₂ ≤ 0, X₁+3X₂ ≥ 3,

X₁ +X₂≤ 6, 5X₁ +8 X₂ ≤ 4 0,

− 5X₁ + 2X₂ ≤ 5, X₁ ≥ 0 ,

X_1, X₂ ≥ 0. 0≤ X₂≤5.

_{͟ ͟}

L(X) = 4X₁− 4X₂ →extr L(X) = -10X₁−16X₂ →extr

203. 2X₁−X₂ ≥ − 4, 204. 2X₁− X₂ ≥ 0,

3X₁ +X₂≥ 3, 6X₁+X₂ ≥ 6,

X₁− 2X₂≤ 5, X₁ −2 X₂ ≤ 2,

4X₁ + 5X₂ ≤ 32, 0 ≤ X₁ ≤ 6,

X_1, X₂ ≥ 0. X₂ ≥ 0.

_{͟ ͟}

L(X) = 3X₁−1,5 X₂ →extr L(X) = -4X₁+2X₂ →extr

205. 5X₁−X₂ ≥ − 10, 206. − 3X₁ +2X₂≤ 6,

X₁ +X₂≤ 7, X₁−8X₂ ≤0,

X₁ −2X₂ ≤0, 3X₁ +2 X₂ ≤18,

X₁ ≥ 0, − X₁ + X₂ ≥ 5,

0 ≤ X₂ ≤ 6. X₁ ,X₂ ≥ 0.

_{͟ ͟}

L(X) = 2,5X₁ −X₂ →extr L(X) = -5X₁+5X₂ →extr

207. X₁−X₂ ≥ − 5,

3X₁ +2X₂≥ 6,

2X₁− X₂≤ 0,

X₁ ≥0,

0 ≤ X₂ ≤ 6.

_͟

L(X) = 3X₁−3 X₂ →extr

5.Транспортная задача.

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого днородного груза из m |пунктов отправления (поставщики) A_1,A₂,...,A_m в n пунктов потребления (потребителя) B₁,B_2,...,B_n так, чтобы:

-вывести все грузы от поствщиков;

-удовлетворить спрос каждого потребителя;

-обеспечить минимальные суммарные транспортные расхода на перевозку всех грузов

Рассмотрим транспотную задачу, в качестве критерии оптимальности которой используется минимальная стоимость перевозки всего груза.

Обозначи:

A_i – наличие груза в i пункте отправления ( i = 1,m);

B_j – величина потребности в этом грузе в j пункте назначения ( j = 1,n);

C_ij – стоимость перевохки единицы груза из i пункта отправления в j пункт потребления (тариф перевозки);

X_ij - количество груза, перевозимого из i пункта отправления в j пункт назначения, X_ij ≥ 0.

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

Запишем математическую модель транспортной задачи.

Требуется определить матрицу Х = (X_ij) ( i = 1,m ; j = 1,n),

Которая удовлетворяет слудующим условиям:

_n

∑ X_ij = a_i, i = 1,m ; (5.1)

^j=1

_m

∑ X_ij = b_j, j = 1,n ; (5.2)

ⁱ⁼¹

X_ij ≥ 0, i = 1,m ; j = 1,n , (5.3)

и доставляет минимальное значение целевой функции

_{m n}

L(X) = ∑ ∑ C_{ij ·} X_ij → min (5.4)

i=1 j=1

Поскольку переменные Хij удовлетворяют линейных уравнений (5.1), (5.2) и условию неотрицательности, то обеспечивается доставка необходимого количества грузов каждому потребителю, вывоз имеющегося груза от всех поставщиков, а также исключаются обратные перевозки.

224. 1 2 2 1 5 600 225. 9 22 20 18 290

6 5 2 7 900 27 15 7 5 410

4 8 4 9 360 9 7 15 3 360

3 1 7 2 850 6 3 9 13 230

200 100 600 310 600 230 290 310

226. 8 20 23 18 620 227. 15 23 18 360

9 25 5 2 600 20 15 28 400

7 19 6 4 250 11 25 18 190

18 12 11 8 150 10 8 5 290

440 100 250 480 300 440 340

228. 3 12 4 8 250 229. 3 7 4 10 70

18 6 3 15 650 7 4 2 9 110

7 9 10 12 550 10 15 4 8 305

4 5 2 13 180 12 20 7 4 65

400 450 850 550 140 95 85 80

230. 6 23 7 16 230 231. 15 26 12 17 200

3 16 25 9 260 5 14 9 20 150

6 12 19 6 135 9 6 16 18 130

8 13 24 28 100 11 5 21 10 180

120 150 120 265 100 110 170 120

232. 7 20 16 8 800 233. 13 16 7 12 410

12 29 11 9 120 8 14 9 17 190

15 25 7 5 900 11 5 10 9 300

21 17 6 3 110 18 4 6 20 200

100 800 150 220 380 280 360 180

40