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

Текст из файла

12

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

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

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)

Лист

Кп-км-п-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 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

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

Лист

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

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-ый пункт. Иными словами, требуется так организовать перевозки продукта со складов в пункты потребления, чтобы при полном удовлетворении потребностей минимизи­ровать суммарные транспортные расходы. Заметим, что условие ( ) является необходимым и достаточным для существования решения транспортной задачи.

Лист

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

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

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

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

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

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

Просматривается вся матрица тарифов перевозок, и из нее выбирается позиция с наименьшим значением тарифа C, затем просматриваются значения наличия запасов на складе A и потребности у потребителя B, затем в данную клетку записывается величина D=MIN(A,B). Из запасов соответствующего склада и потребностей магазина вычитается величина D . Если запас товара на складе исчерпан, то эта строка исключается из дальнейшего рассмотрения. Если потребность магазина в товаре удовлетворена полностью, то этот столбец исключается из дальнейшего рассмотрения. Может быть случай , когда одновременно исключаются и строка и столбец, этот случай называется вырожденным. В дальнейшем весь процесс повторяется до тех пор , пока не будет исчерпан весь запас товаров на складах и не будет удовлетворена потребность всех магазинов. По полученной матрице перевозок вычисляется целевая функция задачи Z.

Лист

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

Метод Фогеля

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

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

В начальной своей стадии этот метод похож на метод минимального элемента , но для столбцов. Просматривается первый столбец матрицы тарифов, в нем находится наименьший элемент. Затем проверяется , минимален ли этот элемент в своей строке. Если элемент минимален в своей строке, то по методу минимального элемента в эту клетку заносится значение D=MIN(A,B),

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

Как и любая задача линейного программирования, необходимо построить первоначальный опорный план для решения задачи. Одним из методов построения исходного опорного плана является так называемый метод «северо-западного» угла.

Лист

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов реферата