 |
 |
 |
 |
|
 |
 |
10
Поскольку любая оптимизационная задача однозначно определяется целевой функцией f и областью
D, на которой отыскивается оптимум (максимум), будем обозначать эту задачу парой (D, f).
Условимся относительно терминологии, которая используется в дальнейшем и является
общепринятой в теории линейного программирования.
Планом ЗЛП называется всякий вектор х из пространства R
n
.
Допустимым планом называется такой план ЗЛП, который удовлетворяет ограничениям (1.2)-(1.3),
т. е. содержится в области D. Сама область D называется при этом областью допустимых планов.
Оптимальным планом х* называется такой допустимый план, при котором целевая функция достигает
оптимального (в нашем случае — максимального) значения, т. е. план, удовлетворяющий условию
max f(x) = f(x*).
Величина f* =f(х*) называется оптимальным значением целевой функции.
Решением задачи называется пара (х*, f*), состоящая из oптимального плана и оптимального
значения целевой функции, а процесс решения заключается в отыскании множества всех решений ЗЛП.
1.1.2. Переход к канонической форме. Подавляющее большинство известных методов решения
задач линейного программирования предназначены для канонических задач. Поэтому начальный этап
решения всякой общей задачи линейного программирования обычно связан с приведением ее к
некоторой эквивалентной канонической задаче.
Общая идея перехода от ОЗЛП к КЗЛП достаточно проста:
ограничения в виде неравенств преобразуются в уравнения за счет добавления фиктивных
неотрицательных переменных х
i
, (i ? 1:m), которые одновременно входят в целевую функцию с
коэффициентом 0, т. е. не оказывают влияния на ее значение;
переменные, на которые не наложено условие неотрицательности, представляются в виде
разности двух новых неотрицательных переменных:
- = - =
х
j
= х
j
– х
j
, (x
j
?
0, х
j
?
0).
Проиллюстрируем применение описанных выше рекомендаций на примере. Пусть задана задача
линейного программирования (D, f) в общей форме с целевой функцией
f(x) = 5х1 + 3x2 + x3 + 2х
4
-2х
5
>
max
и множеством допустимых планов D, определенным системой уравнений и неравенств,
2х1
+ 4х2
+ 5x3
=7,
- 3x2
+ 4x3
– 5x
4
– 4x
5
? 2,
3х1
- 5x3
+ 6x
4
– 2x
5
? 4,
х1? 0,
x3
? 0.
Тогда в соответствии со сформулированными правилами эквивалентная каноническая задача будет
иметь вид (D',f'), где:
а множество D' определено как: