Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
3-курс ВО-МатПрог.doc
Скачиваний:
11
Добавлен:
12.11.2019
Размер:
2.51 Mб
Скачать

Формы записи задач линейного программирования

Симметричной (стандартной) формой записи ЗЛП называется задача максимизации целевой функции (2.1) при ограничениях вида (2.2) и (2.5) или задача минимизации целевой функции (2.1) при ограничениях вида (2.4) и (2.5), т.е.

;

,

или ;

,

,

где – заданные действительные числа.

Канонической формой записи ЗЛП называется задача минимизации или максимизации целевой функции (2.1) при ограничениях вида (2.3) и (2.5), т.е.

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

  1. Переход от задачи на минимум к задаче на максимум осуществляется умножением целевой функции на «–1». Действительно, если функция достигает минимума при значениях , то функция достигает при тех же значениях переменных максимума.

  1. Переход от неравенства вида  к неравенствам вида  (и наоборот) также осуществляется умножением исходного неравенства на –1.

  1. Переход от неравенства к равенству осуществляется введением дополнительной неотрицательной переменной . К примеру, если первое ограничение имеет вид , то, вводя неотрицательную переменную , получим , если второе ограничение имеет вид , то, вводя неотрицательную переменную , получим

  2. При переходе от равенств к неравенствам можно руководствоваться следующим: если дано А=B, то это можно формально записать в виде двух неравенств А  В, А  В;

  3. Введение условий неотрицательности переменных. Пусть на переменную это условие не было наложено, тогда вместо этой переменной можно ввести две неотрицательные переменные и и представить , где . Это всегда возможно.

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

Пример 4

Пусть математическая модель задачи имеет следующий вид

;

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

Тогда ОЗЛП будет иметь вид

;

или (раскрыв скобки):

;

В симметричной (стандартной) форме записи задача будет иметь вид

;

Здесь ограничение (2.6) умножено на –1, а ограничение (2.7) заменено двумя ограничениями:

откуда, домножив второе ограничение на –1, получим ограничение (2.9) вида .

Таким образом, из ограничения (2.7) получены ограничения (2.8) и (2.9).

В канонической форме записи ЗЛП будет иметь вид

;

Пример 5

Экономико-математическую модель задачи, составленную в примере 2, представим в канонической форме записи:

;

Введенные дополнительные переменные и имеют экономический смысл, связанный с содержанием задачи. Здесь , – время простоя оборудования А1 и А2 соответственно.