Реферат: Нахождение опорного плана транспортной задачи

через А - матрицу коэффициентов СЛН:

a11…..a1n

……..

A = ……..

Лист

Кп-км-п-44-2203-99

am1?..amn

через р - вектор-строку коэффициентов целевой функции. Напомним, выражение (р, х) означает скалярное произведение векторов р и х. Тогда в матричном виде задача ЛП записывается:

(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