Формы ОЗЛП.ppt

Слайд 2

Стандартная форма Первая стандартная форма задачи линейного программирования имеет вид

Стандартная форма

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

Слайд 3

Стандартная форма Вторая стандартная форма задачи линейного программирования имеет вид

Стандартная форма

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

Слайд 4

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

Каноническая форма

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

Слайд 5

Правила приведения Рассмотрим теперь те приёмы, которые позволяют произвольные формы задач

Правила приведения

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

программирования приводить к указанным выше стандартным формам.
1. Превращение max в min и наоборот.
Если целевая функция в задаче линейного программирования задана в виде
то, умножая её на (- 1), приведем её к виду
так как смена знака приводит к смене min на max.
Аналогично можно заменить max на min.

,

Слайд 6

Правила приведения 2. Смена знака неравенства. Если ограничение задано в виде

Правила приведения

2. Смена знака неравенства.
Если ограничение задано в виде
то, умножая на

(-1), получим:
Аналогично, неравенство вида больше либо равно можно превратить в неравенство вида меньше либо равно .
Слайд 7

Правила приведения 3. Превращение равенства в систему неравенств. Если ограничение задано

Правила приведения

3. Превращение равенства в систему неравенств.
Если ограничение задано в виде
то

его можно заменить эквивалентной системой двух неравенств
или такой же системой неравенств со знаками больше либо равно.
Указанные выше приемы позволяют приводить задачи линейного программирования к стандартной форме.
Слайд 8

Правила приведения 4. Превращение неравенств в равенства. Для приведения задачи к

Правила приведения

4. Превращение неравенств в равенства.
Для приведения задачи к канонической форме,

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