11. Постановка и методы решения
задачи линейного программирования. Ее геометрическая и экономическая
интерпретации.
Линейное программирование -
это наука о методах исследования и отыскания наибольших и наименьших значений
линейной функции, на неизвестные которой наложены линейные ограничения.
1.
Формулировка
задачи.
Даны линейная функция
(1.1) Z = С 1 х 1 +С 2 х 2 +... +С N x N
и система линейных ограничений
a 11 x 1 + a 22 x 2 + ... + a 1N Х N = b 1
a 21 x 1 + a 22 x 2 + ... + a 2N Х N = b 2
. . . . . . . . . . . . . . .
a i1 x 1 + a i2 x 2 + ... + a iN Х N = b i (1.2)
. . . . . . . . . . . .
. . .
a M1 x 1 + a M2 x 2 + ... + a MN Х N = b M
(1.3) x j 0 (j
= 1, 2, ... ,n)
где а ij ,
Ь j и С j - заданные постоянные
величины.
Найти такие неотрицательные значения х 1 , х 2 , ..., х n , которые удовлетворяют
системе ограничений (1.2) и доставляют линейной функции (1.1)минимальное
значение.
2. Методы решения задач ЛП делятся на два типа: точные и приближенные. Точные -
симплексные методы. Приближенные методы - различные варианты градиентных схем
оптимизации, методы случайного поиска. Наибольшее
распространение у симплексных (последовательный перебор угловых точек, при
котором значение целевой функции улучшается от итерации к итерации (от одной
угловой точки к другой).
3. Геометрическая интерпретация задачи линейного
программирования.
Рассмотрим задачу линейного программирования, система
ограничений которой задана в виде неравенств.
Найти минимальное значение линейной функции
(1.5) Z = С 1 х 1 +С 2 х 2 +... +С N x N
при ограничениях
a 11 x 1 + a 22 x 2 + ... + a 1N Х N b 1
a 21 x 1 + a 22 x 2 + ... + a 2N Х N b 2
(1.6) . . . . . . . . .
. . . . . .
a M1 x 1 + a M2 x 2 + ... + a MN Х N b M
(1.7) x j 0 (j = 1, 2, ...
,n)
Совокупность чисел х 1 , х 2 , ..., х N , удовлетворяющих ограничениям
(1.6) и (1.7), называется решением. Если система неравенств (1.6) при условии (1.7)
имеет хотя бы одно решение, она называется совместной, в противном случае -
несовместной.
Рассмотрим на плоскости х 1 Ох 2 совместную систему линейных
неравенств
a 11 x 1 + a 22 x 2 b 1
a 21 x 1 + a 22 x 2 b 2
. . . . . . . .
a M1 x 1 + a M2 x 2 b M
x 1 0, x 2 0
Это все равно, что в системе (1.6) - (1.7) положить N=2.
Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой