06. Приемы, позволяющие переходить от одной формы записи условий задач к другой

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 соответственно.

< Предыдущая		Следующая >