Составители:
Рубрика:
71
нет. Если же это решение не является неотрицательным, то задача не имеет решения, так
как оптимальный план должен быть неотрицательным, а имеющееся единственное
решение таковым не является.
Приведение задач линейного программирования к стандартной форме
Иногда задачу линейного программирования целесообразно бывает представить в
стандартной форме. При этом число переменных в эквивалентной стандартной задаче
уменьшается.
Общая задача линейного программирования (2.2.1) — (2.2.3) может быть
приведена к стандартной форме следующим образом. Система уравнений (2.2.2)
разрешается относительно некоторых неизвестных; полученные выражения
подставляются в линейную форму, в систему неравенств (2.2.3), а также в условия
неотрицательности неизвестных х
j
≥
0 при всех j. В результате задача принимает
стандартную форму (2.2.7) — (2.2.8). Аналогичным образом приводится каноническая
задача линейного программирования к эквивалентной стандартной задаче.
Приведем численные примеры, иллюстрирующие порядок действий при
преобразовании общей и канонических задач линейного программирования к
эквивалентным стандартным задачам.
Пример 1. Рассмотрим задачу линейного программирования, заключающуюся в
максимизации целевой функции
z=x
1
+x
2
+3x
3
+3x
4
(2.2.18)
при условиях:
=+++
=+++
;7233
;624
4321
4321
xxxx
xxxx
(2.2.19)
;62
4321
≤+++
xxxx (2.2.20)
.0,0,0,0
4321
≥≥≥≥
xxxx (2.2.21)
Последние условия (2.2.21) выражают неотрицательность переменных x
1
, x
2
, x
3
, x
4
.
Приведем систему (2.2.19) к системе с единичным базисом, соответствующим,
например, базисным неизвестным x
3
и х
4
. Как это делается, нам известно (см. часть 1;
2.1.9).
Оформляем расширенную матрицу системы (2.2.19) в виде таблицы столбцов ее по
отношению к единичному базису:
A
1
A
2
A
3
A
4
B
e
1
4
1 2 6
e
2
3 3
1 2 7
Переходим к таблице векторов по отношению к базису А
3
А
4
.
1
Страницы
- « первая
- ‹ предыдущая
- …
- 69
- 70
- 71
- 72
- 73
- …
- следующая ›
- последняя »
