[Список тем] [Вступление к этой теме] страницы темы: [1] [2] [3] [4] [5]

Алгоритм приведения задач линейного программирования к стандартной и канонической форме.

Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме. Для этого в общем случае нужно уметь сводить задачу максимизации к задаче минимизации; переходить от ограничений неравенств к ограничениям равенствами и заменять переменные, которые не подчиняются условию неотрицательности.

Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:

1. если в исходной задаче требуется определить минимум линейной функции Z(X), то следует изменить знак и искать максимум oт -Z (x): max(-Z(X)) = max f(X)
   
2. если в ограничениях правая часть отрицательна, то следует умножить это ограничение на (-1);
   
3. если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;
   
4. если некоторая переменная х_k не имеет ограничений по знаку, то она заменяется ( в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными х_k = х'_k - x_l, где l - свободный индекс, х'_k >= 0, x_l >= 0.
   

Задача

Привести к канонической форме задачу линейного программирования ; Z = 2x1 + х2 - x3 --> min 2х2 - х3 <= 5 x1 + х2 - x3 >= -1 2x1 - х2 <= -3 x1 <= 0, х2 >= 0, x3 >= 0 Решение : введем в каждое уравнение системы ограничений выравнивающие переменные x4 , х5, x6. Система запишется в виде равенств, причем в первое и третье уравнения системы ограничений переменные x4, х6 вводятся в левую часть со знаком "+", а во второе уравнение вводится x5 со знаком "-" Итак: 2х2 - х3 + х4 = 5 х1 + х2 - х3 - х5 = -1 2х1 - х2 + х6 = -3 х4 >= 0, х5 >= 0, х6 >= 0 Свободные члены в канонической форме должны быть положительными, для этою два последних уравнения умножим на -1: 2х2 - х3 + х4 = 5 -х1 - х2 + х3 + х5 = 1 -2х1 + х2 - х6 = 3 В канонической форме записи задач линейного программирования все переменные, входящие в систему ограничении, должны быть неотрицательными, для этого допустим, что х1 = х'1 - x7, где х'1 >= 0, x7 >= 0. Подставляя данное выражение в систему ограничений и целевую функцию и записывая переменные в порядке возрастания индекса, получим задачу линейного программирования, представленную в канонической форме: 2х2 - х3 + х4 = 5 -х'1 - х2 + х3 + х5 + х7 = 1 -2х1 + х2 - х6 = 3 L min = 2х1' + х2 - х3 - 2х7; х'1 >= 0; хi >= 0, i = 2,3,4,5,6,7.

Если исходная задача представлена в канонической форме, а для графического решения надо получить соответствующую задачу в стандартной форме, то применяется уже знакомый алгоритм:

1. Выбрать оcновные переменные.
2. Выразить основные переменные через неосновные.
3. Записать условие неотрицательности основных переменных, выраженных через неосновные.
4. Построить ограничения на плоскости.
5. Построить целевую функцию для двух значений и определить направление ее возрастания.
6. Сдвигая целевую функцию параллельно самой себе в направлении возрастания до границы области допустимых значений, получить оптимальное решение.
7. Выразить основные переменные через неосновные для оптимального решения.

[Список тем] [Вступление к этой теме] страницы темы: [1] [2] [3] [4] [5] [В начало страницы]