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

Для решения транспортной задачи разработано несколько методов, каждый из которых отличается от другого методом заполнения матрицы перевозок. Существуют два

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

Информация

Компьютеры, программирование

Другие материалы по предмету

Компьютеры, программирование

Сдать работу со 100% гаранией

1. ЛИНЕЙНЫЕ МЕТОДЫ ОПТИМИЗАЦИИ, ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ, ЕЕ ПОСТАНОВКА И СВОЙСТВА

1.1 Постановка задачи линейного программирования

В экономике помимо соотношений затрат, выпуска, спроса, предложения и т.п., часто возникает необходимость выбора одного из возможных вариантов функционирования экономической системы. Экономически оправдано в таких условиях ставить вопрос о выборе наилучшего варианта. Что понимать под лучшим вариантом задается в виде критерия (цели). В количественном выражении критерий представляет собой функциональную зависимость от переменных показателей, в дальнейшем будем ее называть целевой (критериальной) функцией. Наилучший вариант в таком случае соответствует наибольшему (экстремальному, оптимальному) значению функции.

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

Экономические требования накладывают свои особенности: в практических задачах число переменных и ограничений достаточно велико, целевая функция не всегда дифференцируема. Поэтому методы классического анализа для отыскания экстремумов к задачам математического программирования часто неприменимы. Возникает необходимость разработки специальных методов решения задач математического программирования и, следовательно, как всегда в таких случаях, появляются новые направления, требующие упорядочения, классификации. Классификация задач происходит в зависимости от экономических условий, видов ограничений, переменных и параметров, методов решения.

Традиционно в математическом программировании выделяют следующие основные разделы.

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

Нелинейное программирование - нелинейны целевая функция и ограничения. Нелинейное программирование принято подразделять следующим образом:

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

- квадратичное программирование - когда целевая функция квадратичная, а ограничения - линейные равенства и неравенства.

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

Важным разделом математического программирования является целочисленное программирование - когда на переменные накладываются условия целочисленности.

Первой из "неклассических" задач оптимизации была подробно исследована задача отыскания экстремума линейной функции на множестве, заданном линейными неравенствами и равенствами. Раздел теории оптимизации, изучающий такие задачи, получил название "линейное программирование".

В данном разделе изучается задача линейного программирования, которая задается следующим образом.

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)

 

 

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 = ……..

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

{ E aij xj<= -bi (12)

 

 

 

 

Уравнение ( 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

 

=0%20%20%20%20u1,%e2%80%a6..um>=0%20%20(16)">x1,…..,xn>=0 u1,…..um>=0 (16)

Стандартная задача линейного программирования на минимум

(матричная запись) записывается в виде:

 

(p,x) max x (17)

 

при условиях:

ax>=b

x>=0 (18)

или в записи в виде неравенств:

 

 

 

EpjXj min x1..xn

 

при ограничениях:

 

 

E aij xj>=bi

 

…………..

E aij xj>=bm

 

X1….xn>=0

 

Таким образом, не важно, в какой форме получаются линейные ограничения: в форме равенств или в форме неравенств. Эквивалентными преобразованиями возможно привести неравенства к равенствам и наоборот. Необходимость преобразований обычно связана с тем, какой применяется метод решения.

 

 

<

Похожие работы

1 2 3 > >>