4. Связь между различными типами задачи лп.

Покажем, что общая задача ЛП может быть сведена как к однородной задаче ЛП, так и к канонической.

1. Вначале сведём общую задачу к однородной. В соответствии с определением 1 п.1.3 для этого достаточно каждое ограничение вида равенства:

,

заменить на равносильную систему неравенств:

Все ограничения задачи будут иметь вид неравенства и задача станет однородной. При этом число ограничений, конечно же, увеличится.

2. Теперь сведем общую задачу ЛП к канонической. Для этого следует, во-первых, представить каждое неравенство в виде равенства и, во-вторых, добиться того, чтобы все переменные задачи были неотрицательны. Для каждого неравенства системы ограничений вида «меньше»

,

добавим новую (балансовую) переменную , определяемую равенством:

.

Для каждого неравенства системы ограничений вида «больше»

введем переменную , определяемую равенством:

Ясно, что так определенные балансовые переменные неотрицательны. Таким способом все неравенства могут быть заменены на равенства.

Для каждой переменной , на которую не наложено тривиальное ограничение, положим: где и

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

Пример 1. Пусть дана задача ЛП

(1)

Требуется преобразовать исходную общую задачу ЛП к другим формам задачи ЛП.

1. Сведем эту задачу к однородной форме.

Заменяя равенство из (1) на систему неравенств получим соответствующую однородную задачу:

(2)

2. Сведем задачу к каноничной форме. Добавим неотрицательные балансовые переменные и , превращая первое и третье ограничения в равенства:

Заменим переменную :

Тогда получим каноническую задачу:

(3)

фактически равносильную исходной.

Таким образом, показано, что общая, однородная и канонические формы задачи ЛП могут быть сведены друг к другу.

Сведение произвольной канонической задачи ЛП к симплексной форме будет рассмотрено в следующих параграфах.

Укажем на один частный случай сведения однородной задачи ЛП к симплексной форме. Пусть дана задача о ресурсах, то есть однородная задача ЛП вида:

(4)

причем все

Сведем эту задачу к канонической с помощью введения балансовых переменных

(5)

Полученная каноническая задача ЛП на самом деле является симплексной, поскольку, во-первых, столбец свободных членов состоит только из неотрицательных элементов, во-вторых, система уравнений имеет разрешенный вид (столбцы переменных , …, и сами переменные являются базисными), в-третьих, целевая функция F зависит только от свободных переменных .

1.5. Графический метод решения задачи лп.

Рассмотрим графический метод решения однородной двумерной задачи ЛП на конкретном примере.

Пример №1.

Решение. Найдем вначале область допустимых решений (ОДР). Решим графически первое неравенство:

(1)

Для этого построим вначале прямую линию, соответствующую уравнению:

. (1¹)

Поскольку, если то то прямая (1¹) проходит через точку М₁(0;8). Аналогично, если то и прямая (1¹) проходит также через точку М₂ (8;0). Проведем через эти две точки прямую линию и отметим ее с помощью 1 (см. рис. 1). Эта линия делит плоскость на две полуплоскости, которые мы условно назовем верхней и нижней полуплоскостями. Так как координаты точки (0;0) удовлетворяют неравенству (1), то этому неравенству соответствует нижняя полуплоскость, которая содержит эту точку. Этот факт мы изобразим на рис. 1 штрихами, направленными вниз от линии 1 .

Теперь решим графически второе неравенство:

(2)

Ему соответствует прямая, заданная уравнением:

(2¹)

Ее мы построим несколько иначе. Перепишем уравнение (2¹) в виде:

Тогда при оказывается , что дает точку М₃ (0;3) искомой прямой. Угловой коэффициент этой прямой Но угловой коэффициент любой прямой равен где - угол наклона прямой к оси 0х: . Если теперь мы отложим три единицы вправо от точки М₃ (0;3) и затем две единицы вверх, то получим другую точку М₄ (3;5) которая также лежит на прямой (2¹). Через точки М₃ и М₄ мы проводим прямую 2 (рис.1). Начало координат (0;0) удовлетворяет (2) и лежит ниже графика линии 2 , поэтому соответствующая полуплоскость является «нижней», что мы и отмечаем штрихами, направленными вниз от прямой 2 (рис.1). Аналогично строим прямую 3.

Уравнение

(3)

заменяем на уравнение

,

Ясно, что прямая проходит через т. М₅ (5;0), и имеет угловой коэффициент к = 2. При этом самому неравенству

соответствует верхняя полуплоскость, отмеченная штрихами вверх от прямой (3).

Тривиальному неравенству соответствует правая полуплоскость координатной плоскости, то есть полуплоскость, лежащая справа от вертикальной оси Ее отмечаем штрихами, направленными вправо от оси 0 Наконец неравенству соответствует верхняя полуплоскость координатной плоскости, отмеченная штрихами, направленными вверх от оси 0 . Пересечение всех указанных полуплоскостей определяет ОДР данной задачи. На рисунке 1 это область, ограниченная выпуклым пятиугольником ОАВСD.

Изобразим на рисунке 1 вектор роста целевой функции . Это вектор началом в т. (0;0) и концом в точке М (4;3), поскольку .

Построим теперь линию уровня . Она определяется уравнением:

(3)

Мы взяли здесь константу С =11, для того чтобы точки пересечения прямой (3) с осями имели целые координаты. Действительно, если то и, если то что дает две точки М₁ (0;4) и М₂ (3;0) линии уровня (3). Через них проводим пунктиром соответствующую линию уровня (рис. 1). Она оказывается перпендикулярна вектору роста . Отрезок пересекается с ОДР и в каждой его точке х значение целевой функции равно 11:

.

Мы знаем, что значение функции F увеличивается в направлении вектора роста . Чтобы найти максимальное значение на ОДР будем параллельно перемещать линию уровня в направлении вектора роста до тех пор, пока, она будет иметь хотя бы одну точку пересечения с ОДР задачи. Из рисунка 1 ясно, что последнее пересечение смещенной линии уровня (3) будет точка

Рисунок 1. Графическое решение задачи ЛП.

На этой линии очевидно и будет достигаться максимальное значение целевой функции F в ОДР, поскольку при дальнейшем движении линии уровня в направлении вектора роста, она перестает пересекаться с ОДР. Итак, максимальное значение функция F(х) имеет в точке . Так как точка является пересечением прямых 1 и 3, то ее координаты находятся из системы:

(4)

Чтобы решить эту систему, сложим оба уровня. Тогда получим, что или .

Из первого уравнения находим, что

Итак, координаты точки С найдены – С (6;2). Найдем максимальное значение функции:

Задача решена

Ответ: максимальное значение целевой функции F достигается в точке С (6;2) и равно 29:

.