Формы записи задач линейного программирования
Симметричной (стандартной) формой записи ЗЛП называется задача максимизации целевой функции (2.1) при ограничениях вида (2.2) и (2.5) или задача минимизации целевой функции (2.1) при ограничениях вида (2.4) и (2.5), то есть
;
,
,
или 
;
,
,
где 
- заданные действительные числа.
Канонической формой записи ЗЛП называется задача минимизации или максимизации целевой функции (2.1) при ограничениях вида (2.3) и (2.5), то есть
Рассмотрим приемы, позволяющие переходить от одной формы записи условий задач к другой
1 Переход от задачи на минимум к задаче на максимум осуществляется умножением целевой функции на (-1). Действительно, если функция 
достигает минимума при значениях 
, то функция 
достигает при тех же значениях переменных максимума.
2 Переход от неравенства вида « £ » к неравенствам вида « ³ » (и наоборот) также осуществляется умножением исходного неравенства на (-1).
3 Переход от неравенства к равенству осуществляется введением дополнительной неотрицательной переменной 
. Так если, к примеру, дано 
, то, вводя 
, получим:
.
4 При переходе от равенств к неравенствам можно руководствоваться следующим: если дано А=B, то это можно формально записать в виде двух неравенств: А £ В, А ³ В;
5 Введение условий неотрицательности переменных. Пусть на переменную 
это условие не было наложено. Тогда вместо этой переменной можно ввести две неотрицательные переменные 
и 
, и представить 
, где 
. Это всегда возможно.
|
|
|
Изложенными приемами общая ЗЛП может быть сведена к симметричной и канонической формам записи ЗЛП и наоборот. Однако, поскольку в процессе таких преобразований мы вводили дополнительные переменные, то после того, как задача решена, нужно произвести обратный переход к исходным переменным, определяющим непосредственный экономический смысл задачи.
Пример 4
Пусть математическая модель задачи имеетследующий вид:
;
Чтобы получить общую задачу линейного программирования, необходимо, чтобы на все переменные было наложено условие неотрицательности. Для наложения этого ограничения на переменную 
воспользуемся правилом 5. Введем новые неотрицательные переменные 
и 
и представим 
, где 
и 
.
Тогда ОЗЛП будет иметь вид:
;
или (раскрыв скобки):
;
В симметричной (стандартной) форме записи задача будет иметь вид:
;
Здесь ограничение (2.6) умножено на (-1), а ограничение (2.7) заменено двумя ограничениями:
откуда, умножив второе ограничение на (-1), получим ограничение (2.9) вида « ³ ».
Таким образом, из ограничения (2.7) получены ограничения (2.8) и (2.9).
|
|
|
В канонической форме записи ЗЛП будет иметь вид:
;
Пример 5
Экономико-математическую модель задачи, составленную в примере 2, представим в канонической форме записи:
;
Введенные дополнительные переменные и 
имеют экономический смысл, связанный с содержанием задачи. Здесь , - время простоя оборудования А1 и А2 соответственно.
Дата добавления: 2018-09-20; просмотров: 440; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!