Программирования

Общая и основная задачи линейного

Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции

(2.8)

при условиях

(2.9)

(2.10)

. (2.11)

где - заданные постоянные величины и .

Функция (2.8) называется целевой функцией (линейной формой) задачи (2.8)-(2.11), а условия (2.9)-(2.11) – ограничениями данной задачи.

Стандартной (симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (2.8) при условиях (2.9) и (2.11), где k=m и l=n.

Канонической (основной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (2.8) при условиях (2.10) и (2.11), где k= 0 и l=n.

Совокупность чисел , удовлетворяющих ограничениям (2.9)-(2.11), называется допустимым решением (планом).

План , при котором целевая функция (2.8) принимает свое максимальное (минимальное) значение, называется оптимальным.

- оптимальный план задачи, если (в задаче на максимум) и (в задаче на минимум).

Замечание. Все 3 формы задачи линейного программирования эквивалентны:

1) Если требуется найти минимум функции

,

можно перейти к нахождению максимума функции

,

т.к. min z=-max(-z).

2) От знака «» в ограничениях можно перейти к «=» добавлением к левой части ограничения дополнительной переменной, а от знака «» - вычитанием дополнительной неотрицательной переменной.

3) Число вводимых дополнительных переменных равно числу преобразуемых неравенств.

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

(2.12)

при условиях

(2.13)

Решение. Чтобы записать в форме основной задачи нужно перейти к ограничениям-равенствам:

(2.14)

Данная задача может быть записана в форме основной таким образом: максимизировать функцию (2.12) при условиях (2.14).

Пример 2.2. Записать задачу, состоящую в минимизации функции

(2.15)

при условиях

(2.16)

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

Решение. Вместо нахождения минимума функции z нужно найти максимум функции при ограничениях, получающихся из исходных добавлением к левым частям неравенств «», и вычитанием из левых частей неравенств со знаком «» дополнительных переменных. Тогда исходная задача может быть записана в форме основной задачи линейного программирования так:

при условиях

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

(2.17)

при условиях

(2.18)

Решение. Выпишем расширенную матрицу системы и с помощью метода исключения неизвестных Жордана-Гаусса приведем ее к ступенчатой форме:

~ ~ ~ ~ .

Таким образом, исходную систему мы свели к следующей:

Выразим и через и и подставим в z

Тогда задача будет состоять в нахождении максимального значения функции

при условиях

Замечание. Вводимые дополнительные переменные имеют вполне экономический смысл. Так, если в ограничениях исходной задачи отражается расход и наличие производственных ресурсов, то числовое значение дополнительной переменной в плане задачи, записанной в форме основной, равно объему неиспользуемого соответствующего ресурса.

Дата добавления: 2015-05-26