Задача линейного программирования (злп): содержательная постановка, примеры задач лп; этапы решения задачи; формальная постановка.
Линейное программирование -- область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между переменными.
Модель задачи линейного программирования включает: 1) совокупность неизвестных величин, действуя на которые, систему можно совершенствовать. Их называют планом задачи (вектором управления, решением, управлением, стратегией, поведением и др.); 2) целевую функцию (функцию цели, показатель эффективности, критерий оптимальности, функционал задачи и др.). Целевая функция позволяет выбирать наилучший вариант - из множества возможных. Наилучший вариант доставляет целевой функции экстремальное значение. Это может быть прибыль, объем выпуска или реализации, затраты производства, издержки обращения, уровень обслуживания или дефицитности, число комплектов, отходы и т. д.;
Постановка практической задачи ЛП включает следующие основные этапы:
· определение переменных задачи,
· задание линейной целевой функции L(x), подлежащей минимизации или максимизации,
· задание ограничений.
Строится система линейных уравнений с n неизвестными исходя из ограничений по условию задачи и ограничений на неотрицательность переменных:
a11 x1 + a11 x2 + …… + a11 xn >(<,=) b1 ,
a21 x1 + a22 x2 + …… + a2n xn >(<,=) b2 ,
am1 x1 + am2 x2 + …… + amn xn >(<,=) bm ,
и линейная функция
L = c1 x1 + c2 x2 +………+ cn xn
Требуется найти такое неотрицательное решение системы при котором функция L принимает наименьшее(наибольшее) значение.
Уравнения называют системой ограничений данной задачи; функцию L -- целевой функцией.
Формы записи злп: общая, симметричная, каноническая, матричная, векторная. Переход к канонической форме.
Стандартная постановка:
|
(1.7) |
Введем вектора
; 
; 
,
a также вектора
, 
и матрицу
.
Заметим,
что комбинация 
есть
не что иное, как скалярное
произведение векторов 
и 
.
Поэтому в векторной
форме задача (1.7)примет
вид
|
Можно
использовать и матричные
обозначения. Тогда
комбинация
есть произведение
и задача (1.7) примет вид
|
Каноническая, стандартная и общая формы:
Каноническая (основная) форма |
Стандартная (симметричная) форма |
Общая форма |
1) ограничения |
||
Уравнения
|
Неравенства
|
Уравнения и неравенств
|
2) условия неотрицательности |
||
Все переменные
|
Все переменные , |
Часть переменных
, |
3) цель задачи
|
||
max F(x) или minF(x) |
max F(x) [min F(x)] |
max F(x) или min F(x) |
.
.
.
, 
, 
.
Способы преобразования. Переход к канонической форме. Указанные выше три формы ЗЛП эквивалентны в том смысле, что каждая из них с помощью несложных преобразований может быть записана в форме другой задачи. Это означает, что если имеется способ нахождения решения одной из указанных задач, то тем самым может быть определен оптимальный план любой из трех задач.
Чтобы перейти от одной формы записи ЗЛП к другой, нужно в общем случае уметь:
1. сводить задачу минимизации функции к задаче максимизации;
2. переходить от ограничений-неравенств к ограничениям-равенствам и наоборот;
3. заменять переменные, которые не подчинены условию неотрицательности.
В том случае, когда требуется найти минимум функции , можно перейти к нахождению максимума функции , поскольку max F(x) = – min[– F(x)], min F(x) = – max[– F(x)].
Ограничение-неравенство исходной ЗЛН, имеющее вид «меньше или равно», можно преобразовать в ограничение-равенство добавлением к его левой части дополнительной переменной, а ограничение-неравенство вида «больше или равно» - в ограничение-равенство вычитанием из его левой части дополнительной неотрицательной переменной. Таким образом, ограничение-неравенство преобразуется в ограничение-равенство, а ограничение-неравенство преобразуется в ограничение-равенство.