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

БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Нахождение опорного плана транспортной задачи

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

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

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.3 Транспортная задача

Пусть некоторый, однородный товар (продукт) хранится на M складах и

потребляется в N пунктах (например, магазинах). Известны следующие

параметры:

ai - запас продукта на -ом складе, ai>0, i=1,….,m

bj- потребность в продукте в -ом пункте, bj>0,j=1,….,n

Cij - стоимость перевозки единичного количества товара с -го склада в

-й пункт, . Планируется полностью перевезти товар со складов и

полностью удовлетворить потребности в пунктах назначения. При этом

предполагается, что суммарные запасы равны суммарным потребностям:

m n

E ai = E bj (19)

i=1 j=1

Транспортная задача ставится как каноническая задача ЛП следующего

специального вида:

m n

E E CijXij ( min (20)

i=1 j=1

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

n

E xij=ai,i=1,…,m (21)

J=1

n

E xij=bj,j=1,….,n (22)

I=1

Xij>=0, i=1,…..m j=1,….n (23)

где - количество товара, перевозимого с I-го склада в J-ый пункт.

Иными словами, требуется так организовать перевозки продукта со складов в

пункты потребления, чтобы при полном удовлетворении потребностей

минимизировать суммарные транспортные расходы. Заметим, что условие ( )

является необходимым и достаточным для существования решения транспортной

задачи.

4. Анализ задачи или модели.

4.1 Определение опорного плана транспортной задачи

Для решения транспортной задачи разработано несколько методов, каждый

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

Существуют два типа транспортной задачи: открытая и закрытая. Транспортная

задача называется открытой если сумма запасов товара на складах отличается

от суммы потребностей товаров у магазинов. Транспортная задача называется

закрытой , если сумма запасов товара на складах равняется сумме

потребностей магазинов. Решение существует только для закрытой транспортной

задачи, поэтому если транспортная задача открытая , то ее надо привести к

закрытому типу. Для этого в случае , если запас товара на складах

превышает потребность магазинов, то вводят фиктивного потребителя, который

выбирает весь избыток товара. В случае же, если существует дефицит товара,

т.е. потребность магазинов больше, чем запас товаров на складах, то вводят

фиктивного поставщика, с фиктивным запасом товара на складе. В обоих

случаях в матрице тарифов перевозок |C| данному складу или магазину

проставляется нулевая цена перевозки.

Метод минимального элемента

Алгоритм метода минимального элемента состоит в следующем.

Просматривается вся матрица тарифов перевозок, и из нее выбирается

позиция с наименьшим значением тарифа C, затем просматриваются значения

наличия запасов на складе A и потребности у потребителя B, затем в данную

клетку записывается величина D=MIN(A,B). Из запасов соответствующего склада

и потребностей магазина вычитается величина D . Если запас товара на

складе исчерпан, то эта строка исключается из дальнейшего рассмотрения.

Если потребность магазина в товаре удовлетворена полностью, то этот

столбец исключается из дальнейшего рассмотрения. Может быть случай , когда

одновременно исключаются и строка и столбец, этот случай называется

вырожденным. В дальнейшем весь процесс повторяется до тех пор , пока не

будет исчерпан весь запас товаров на складах и не будет удовлетворена

потребность всех магазинов. По полученной матрице перевозок вычисляется

целевая функция задачи Z.

Метод Фогеля

Метод состоит в следующем. Просматриваются все строки и столбцы

матрицы тарифов, вычисляется разность между двумя наименьшими элементами в

строке или в столбце. Затем из всех этих разностей выбирается строка или

столбец с максимальной разность. В выбранной строке или столбце , как и в

методе минимального элемента, заполняется клетка с наименьшим значением

тарифа. Затем обнулявшаяся строка или столбец исключаются из рассмотрения и

весь процесс повторяется до полного исчерпания запаса товаров на складах.

По полученной матрице перевозок вычисляется целевая функция Z.

Метод двойного предпочтения

В начальной своей стадии этот метод похож на метод минимального

элемента , но для столбцов. Просматривается первый столбец матрицы тарифов,

в нем находится наименьший элемент. Затем проверяется , минимален ли этот

элемент в своей строке. Если элемент минимален в своей строке, то по методу

минимального элемента в эту клетку заносится значение D=MIN(A,B),

соответствующие запас и потребность уменьшаются на эту величину.

Обнулившаяся строка или столбец исключаются из рассмотрения и процесс

повторяется, начиная с первого неисключенного столбца. Если найденный

минимальный элемент не минимален в своей строке, то происходит переход к

следующему столбцу и так до тех пор, пока не будет найден такой элемент. По

полученной матрице перевозок вычисляется целевая функция Z. Этот метод

требует интенсивных операции обмена с памятью , поэтому более громоздок по

сравнению с остальными и требует больших вычислительных ресурсов.

Как и любая задача линейного программирования, необходимо построить

первоначальный опорный план для решения задачи. Одним из методов построения

исходного опорного плана является так называемый метод «северо-западного»

угла.

Метод северо-западного угла

Метод состоит в следующем. Просматривается матрица тарифов перевозок C ,

начиная с левого верхнего угла (клетки). В эту клетку записывается величина

D=MIN(A,B). Она вычитается из запасов и потребностей соответствующего

склада и магазина. Обнулившаяся строка или столбец исключаются из

рассмотрения, затем процесс опять повторяется для левой верхней клетки

оставшейся матрицы и так до тех пор пока весь запас товаров не будет

исчерпан. Полученный опорный план не оптимален, поэтому его дальнейшее

решение продолжают одним из вышерассмотренных методов.

2. Предмодельный анализ.

2.1 Анализ существующих аналогов и подсистем

Программное обеспечение для решения задач линейного программирования и в

частности, транспортной задачи разработано уже в конце 60-ых – начале 70-ых

годов и было реализовано как пакет программ – библиотек. Данный пакет задач

был реализован на таких алгоритмических языках как Алгол, Фортран. В

западных разработках в основном применялся алгоритмический язык Кобол. С

появлением персональных компьютеров данный пакет был перемещен на ПК, с

учетом особенностей реализации трансляторов вышеперечисленных языков на ПК.

Также дополнительно были реализованы пакеты программ, в основном усилиями

вузов на языках Паскаль, Си. Перенос программного обеспечения на ПК открыл

новые возможности в решении задач линейного программирования и наглядного

отображения результатов вычислении, что отсутствовало на больших

вычислительных системах – мэйнфреймах.

Ход вычислении и его результаты, особенно для многомерных задач с большим

числом переменных можно было наглядно отобразить на мониторе. Кроме того

появление интерактивных программ, программ , в ход которых человек-

оператор мог активно вмешаться, корректировать промежуточные результаты ,

изменить методику расчетов, значительно облегчал и ускорял разработку

нового программного обеспечения.

С развитием аппаратного обеспечения совершенствовалось и программное

обеспечение. Алгоритмические языки тоже совершенствовались согласно

потребностям экономики, науки и т.д.

Особо бурное развитие программного обеспечения началось с появлением

операционной системы Windows. Почти все существующее программное

обеспечение и алгоритмические языки были перенесены на эту операционную

платформу. Возможности Windows усилили интерактивную сторону этих

алгоритмических языков, перейдя на объектно-ориентированный принцип

построения алгоритмов, что позволяло использовать уже наработанное

программное обеспечение без больших изменений.

Одним из бурно развивающихся алгоритмических языков является Pascal и его

диалекты. Первоначально этот язык был создан для обучения студентов основам

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

создан Никлаусом Виртом, и послужил основой для целого семейства паскале-

подобных языков – Modula, Classcal, Object Pascal.

Наиболее развитую систему программирования на языке Pascal построила фирма

Borland – Turbo Pascal. Первоначально она была реализована для DOS, с

появлением Windows , она была перенесена в нее. И наконец, была выпущена

новая версия для Windows – Delphi.

5.2 Среда разработки Delphi

Без баз данных сегодня невозможно представить работу большинства

финансовых, промышленных, торговых и прочих организаций. Потоки информации,

циркулирующие в мире, который нас окружает, огромны. Во времени они имеют

тенденцию к увеличению. Не будь баз данных, мы давно захлебнулись бы в

информационной лавине. Базы данных позволяют информацию структурировать,

хранить и извлекать оптимальным для пользователя образом.

Поскольку использование баз данных является одним из краеугольных камней,

на которых построено существование различных организаций, пристальное

внимание разработчиков приложений баз данных вызывают инструменты, при

помощи которых такие приложения можно было бы создавать. Выдвигаемые к ним

требования в общем виде можно сформулировать как:

"быстрота, простота, эффективность, надежность".

Среди большого разнообразия продуктов для разработки приложений Delphi

занимает одно из ведущих мест. Delphi и отдают предпочтение разработчики с

разным стажем, привычками, профессиональными интересами. С помощью Delphi

написано колоссальное количество приложений, десятки фирм и тысячи

программистов-одиночек разрабатывают для Delphi дополнительные компоненты.

В основе такой общепризнанной популярности лежит тот факт, что Delphi, как

никакая другая система программирования, удовлетворяет изложенным выше

требованиям. Действительно, приложения с помощью Delphi разрабатываются

быстро, причем взаимодействие разработчика с интерактивной средой Delphi не

вызывает внутреннего отторжения, а наоборот, оставляет ощущение комфорта.

Delphi -приложения эффективны, если разработчик соблюдает определенные

правила (и часто - если не соблюдает). Эти приложения надежны и при

эксплуатации обладают предсказуемым поведением.

Но вот проста ли Delphi? И да, и нет. Она лишь кажется простой, поскольку

многие "подводные камни" скрыты от разработчика. Однако чем больше изучаешь

ее, тем больше становится ясной ее глубина, которая одновременно и вызывает

уважение, и пугает. Лишь со временем приходит понимание того, что для

написания действительно мощных и функциональных приложений требуется

постоянное изучение Delphi.

-----------------------

лист

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

Лист

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

Лист

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

Лист

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

Лист

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

Лист

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

Лист

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

Лист

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

Лист

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

Лист

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

Лист

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

Лист

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