Нахождение опорного плана транспортной задачи
.
ЛИНЕЙНЫЕ МЕТОДЫ
ОПТИМИЗАЦИИ,
ЗАДАЧА ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ,
ЕЕ ПОСТАНОВКА
И СВОЙСТВА
1.1 Постановка задачи линейного программирования
В экономике помимо соотношений затрат, выпуска, спроса, предложения и т.п., часто возникает необходимость выбора одного из возможных вариантов функционирования экономической системы. Экономически оправдано в таких условиях ставить вопрос о выборе наилучшего варианта. Что понимать под лучшим вариантом задается в виде критерия (цели). В количественном выражении критерий представляет собой функциональную зависимость от переменных показателей, в дальнейшем будем ее называть целевой (критериальной) функцией. Наилучший вариант в таком случае соответствует наибольшему (экстремальному, оптимальному) значению функции.
В экономических задачах, как правило, область изменения переменных параметров ограничена и оптимальное значение целевой функции требуется найти на ограниченном множестве. Область исследования, заключающаяся в нахождении алгоритмов решения подобных задач, образует направление, которое называется математическим программированием.
Экономические требования накладывают свои особенности: в практических задачах число переменных и ограничений достаточно велико, целевая функция не всегда дифференцируема. Поэтому методы классического анализа для отыскания экстремумов к задачам математического программирования часто неприменимы. Возникает необходимость разработки специальных методов решения задач математического программирования и, следовательно, как всегда в таких случаях, появляются новые направления, требующие упорядочения, классификации. Классификация задач происходит в зависимости от экономических условий, видов ограничений, переменных и параметров, методов решения.
Традиционно в математическом программировании выделяют следующие основные разделы.
Линейное программирование - целевая функция линейна, множество, на котором ищется экстремум целевой функции, задается системой линейных равенств и неравенств. В свою очередь в линейном программировании существуют классы задач, структура которых позволяет создать специальные методы их решения, выгодно отличающиеся от методов решения задач общего характера. Так, в линейном программировании появился раздел транспортных задач, блочного программирования и др.
Н
лист
Кп-км-п-44-2203-99
-
выпуклое
программирование
- когда выпукла
целевая функция,
если рассматривается
задача ее минимизации
(либо выпуска,
если ищется
максимум), и
выпукло множество,
на котором
решается
экстремальная
задача;
- квадратичное программирование - когда целевая функция квадратичная, а ограничения - линейные равенства и неравенства.
Многоэкстремальные задачи - здесь обычно выделяют специализированные классы задач, часто встречающихся в приложениях, например, задачи о минимизации на выпуклом множестве вогнутых функций.
Важным разделом математического программирования является целочисленное программирование - когда на переменные накладываются условия целочисленности.
Первой из "неклассических" задач оптимизации была подробно исследована задача отыскания экстремума линейной функции на множестве, заданном линейными неравенствами и равенствами. Раздел теории оптимизации, изучающий такие задачи, получил название "линейное программирование".
В данном разделе изучается задача линейного программирования, которая задается следующим образом.
1. Задача решается относительно переменных .
В дальнейшем они будут записываться в виде либо вектора-столбца
( X1)
X = ( .. )
( Xn)
либо вектора-строки х = (х1, ..., хn).
Предполагается, что вектор х должен удовлетворять системе n линейных неравенств
a11x1+ …. +a1nxn <= b1
am1x1+….+amnxn<=bm (1)
3. В экономических задачах присутствует дополнительное необходимое условие: координаты вектора х должны быть неотрицательными:
X >= 0 (2)
где 0 - нулевой вектор-столбец размерности n.
4. Целевая функция представляет собой линейную функцию переменных X1,…..,Xn
P1X1+…..PmXn=f(x1,….,xn) (3)
Лист
Кп-км-п-44-2203-99
5
.
Общая задача
линейного
программирования
(ЛП) состоит в
выборе вектора
х, удовлетворяющего
системе неравенств
(1),
(2)
и максимизирующего
целевую функцию
( 3 ).
Математически
задача ЛП
записывается
следующим
образом:
P1X1+…..+PnXn max (x1<….xn) (4)
при условиях
{a11x1+…….+a1nxn<=b1}
{…………………………… } (5)
{am1x1+…….+amnxn<=bm}
x1>=0, x2>=0,……,xn>=0 (6)
или
n
E pixi max
J=1 x1,..,xn
при условиях
n
{ E a1jxj<=bi
j=1
{…………
n
{ E a1jxj<=bj
j=1
{…………
n
{ E mjxj<=bm
x1,….,xn >=0
Задача Линейного Программирования в матричной форме записывается следующим образом. Обозначим через b вектор-столбец правой части СЛН
(b1)
B = (….)
(bm)
через А - матрицу коэффициентов СЛН:
![]()
![]()
![]()
![]()
a11…..a1n
……..
A = ……..
Лист
Кп-км-п-44-2203-99
ч![]()
![]()
ерез
р - вектор-строку
коэффициентов
целевой функции.
Напомним, выражение
(р, х) означает
скалярное
произведение
векторов р и
х. Тогда в матричном
виде задача
ЛП записывается:
(P,X)max(x)
при условии:
Ax<=b
x>=0
Таким образом, в задаче Линейного Программирования константами (параметрами) являются коэффициенты матрицы А, вектор правой части В и коэффициенты целевой функции - вектор P. Подлежит определению вектор х*=х1,..,,хn,), который удовлетворяет ограничениям ( 8 ), ( 9):
Ах* < В
х*>0,
и доставляет максимум целевой функции ( 7):
max(p,x)= (р, х*).
Это матричная запись задачи ЛП на максимум в стандартной форме.
Запись задачи линейного программирования ( 4) - (6) или (7) - (9) называют записью ЗЛП в стандартной форме.
Иногда, исходя из практических требований, отдельные ограничения на переменные х,, ..., х„ могут иметь вид точного равенства
n
E aijxj=bi
I=1 (10)
Это значит, что решение требуется искать среди векторов х, координаты которых удовлетворяют i-му ограничению как точному равенству. Чтобы привести в этом случае задачу к стандартному виду, уравнение (10) достаточно заменить на систему из двух ^неравенств:
{ E ai jxj<=bi
{ E aij xj>=bi (11)
или
{ E aij xj<=bi
{ E aij xj<= -bi (12)
Лист
Кп-км-п-44-2203-99
У
равнение
( 11)
и система (
12 ) или эквивалентны.
Задача линейного
программирования
вида:
mах (р, х)
Ах=B ( 13 )
х>0
называется задачей линейного программирования в канонической форме.
Чтобы привести задачу линейного программирования в стандартной фюрме к форме канонической, следует ввести дополнительные переменные ui,ui>=0,i=1,2,….,m , такие, что
E aij xj+ui=bi, i=1,….,m
Причем целевая функция при этом должна оставаться неизменной. Для этого запишем целевую функцию в виде:
EpjXj+0*u1+0*u2+…..0*um
Здесь коэффициенты при переменных u1,….,um полагаются равными нулю. Тогда задача (7) - (9) в каноническом виде принимает вид:
( n )
( E PjXj ) max x
( j=1 )
(14)
при условиях:
n
E aijxj+ui=bi, i=1,…..,m (15)
j=1
x1,…..,xn>=0 u1,…..um>=0 (16)
Стандартная задача линейного программирования на минимум
(матричная запись) записывается в виде:
(p,x) max x (17)
при условиях:
ax>=b
x>=0 (18)
или в записи в виде неравенств:
Лист
Кп-км-п-44-2203-99
E
pjXj
min x1..xn
при ограничениях:
E aij