Основы автоматизированного проектирования химических производств. Миронов В.М - 116 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

116
7.7.2. Задача ЛП в стандартной форме.
Эту задачу в стандартной форме можно записать в компактных матема-
тических обозначениях следующим образом:
Оптимизировать функцию Z=cx при ограничениях Ах=b; х
≥
0; b
≥
0,
где А – матрица размерности mxn (матрица коэффициентов);
х – вектор-столбец размерностью nx1 (вектор переменных);
b – вектор-столбец размерностью mx1 (вектор ресурсов);
с – вектор-строка размерностью 1xn (вектор оценок задачи ЛП).
Основной метод решения задач линейного программирования – сим-
плекс-метод. При решении задач ЛП симплекс-методом требуется, чтобы за
-
дача была представлена в стандартной форме. Однако, не все задачи ЛП
имеют стандартную форму. Часто ограничения имеют вид неравенств, в не-
которых задачах не все переменные неотрицательны. Таким образом, первый
этап решения задачи ЛП состоит в приведении ее к стандартной форме.
Ограничения в виде неравенств можно преобразовать в равенства при
введении так называемых остаточных, или избыточных переменных.
Например: 2х
1
+х
2
-3х
3
≥12⇒2х
1
+х
2
-3х
3
-S
1
=12; S
1
=2х
1
+х
2
-3х
3
-12;
x
1
+2x
2
+3x
3
≤25⇒ x
1
+2x
2
+3x
3
+S
2
=25.
Поскольку переменные линейного программирования в стандартной
форме предполагаются неотрицательными, неограниченные переменные сле-
дует заменить разностью двух неотрицательных:
.0;0;
11111
≥≥−=
−+−+
SSSSS
ПРИМЕР 7.16. Максимизировать функцию Z=x
1
-2x
2
+3x
3
при ограни-
чениях:
х
1
+х
2
+х
3
≤7; (А)
х
1
-х
2
+х
3
≥2; (Б)
3х
1
-х
2
-2х
3
=-5; (В)
х
1
≥0; х
2
≥0; (Г)
Переменная х
3
– неограниченная по знаку.
Преобразуем задачу к стандартной форме:
- заменим х
3
=х
4
-х
5
, где х
4
≥0 и х
5
≥0;
- умножим обе части уравнения (В) на –1;
- введем дополнительные переменные х
6
и х
7
в уравнения (А) и (Б)
соответственно;
- припишем нулевой коэффициент переменным х
6
и х
7
, целевая функ-
ция при этом не изменится.
Тогда задача сведется к следующей:
Максимизировать функцию Z=x
1
-2x
2
+3x
4
-3х
5
при ограничениях:
х
1
+х
2
+х
4
+х
5
+х
6
+х
7
=7;
х
1
-х
2
+х
4
-х
5
-х
7
=2;

Страницы