Динамическое и линейное программирование



РУБРИКИ	Динамическое и линейное программирование	РЕКЛАМА

Главная

Логика

Логистика

Международное публичное право

Международное частное право

Международные отношения

Авиация и космонавтика

Административное право

Экономико-мат. моделирование

Экономическая география

ПОИСК

Динамическое и линейное программирование

Государственный университет управления

Институт заочного обучения

Специальность – менеджмент

Кафедра прикладной математики

КУРСОВОЙ ПРОЕКТ

по дисциплине: «Прикладная математика»

Выполнил студент 1-го курса

Группа № УП4-1-98/2

Студенческий билет №

Москва, 1999 г.

Содержание

1. Линейная производственная задача 3

2. Двойственная задача 7

3. Задача о «Расшивке узких мест производства» 9

4. Транспортная задача 12

5. Распределение капитальных вложений 17

6. Динамическая задача управления запасами 21

7. Анализ доходности и риска финансовых операций 26

8. Оптимальный портфель ценных бумаг 28

1. Линейная производственная задача

Линейная производственная задача – это задача о рациональном

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

линейного программирования. В общем виде задача может быть сформулирована

следующим образом:

Предположим, предприятие или цех может выпускать [pic] видов продукции,

используя [pic] видов ресурсов. При этом известно количество каждого вида

ресурса, расход каждого вида ресурса на выпуск каждого вида продукции,

прибыль, получаемая с единицы выпущенной продукции. Требуется составить

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

предприятием, была бы наибольшей.

Примем следующие обозначения:

|[pic]|Номер ресурса (i=1,2,…,m) |

|[pic]|Номер продукции (j=1,2,…,n) |

|[pic]|Расход i-го ресурса на единицу j-ой продукции |

|[pic]|Имеющееся количество i-го ресурса |

|[pic]|Прибыль на единицу j-ой продукции |

|[pic]|Планируемое количество единиц j-ой продукции |

|[pic] |Искомый план производства |

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

производственную программу [pic] максимизирующую прибыль:

[pic]

При этом, какова бы ни была производственная программа [pic], ее

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

данного вида ресурса, при производстве всех видов продукции не должно

превышать имеющееся количество данного вида ресурса, т.е.

[pic], где [pic]

А так как компоненты программы – количество изделий, то они не могут

быть выражены отрицательными числами, следовательно добавляется еще одно

условие:

[pic], где [pic]

Предположим, что предприятие может выпускать четыре вида продукции

([pic]), используя для этого три вида ресурсов ([pic]). Известна

технологическая матрица [pic] затрат любого ресурса на единицу каждой

продукции, вектор [pic] объемов ресурсов и вектор [pic] удельной прибыли:

[pic] [pic] [pic]

Тогда математическая модель задачи будет иметь вид:

Найти производственную программу [pic] максимизирующую прибыль:

|[pic] |(1.1) |

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

|[pic] |(1.2) |

где по смыслу задачи: [pic], [pic], [pic], [pic]

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

решения введем дополнительные неотрицательные неизвестные:

|[pic], |остаток ресурса определенного вида |

|[pic], |(неиспользуемое количество каждого |

|[pic] |ресурса) |

Тогда вместо системы неравенств (1.2), получим систему линейных

алгебраических уравнений:

|[pic] |(1.3) |

где среди всех решений, удовлетворяющих условию неотрицательности:

[pic], [pic], [pic], [pic], [pic], [pic], [pic]

надо найти решение, при котором функция (1.1) примет наибольшее значение.

Эту задачу будем решать методом последовательного улучшения плана –

симплексным методом.

Воспользуемся тем, что правые части всех уравнений системы (1.3)

неотрицательны, а сама система имеет предпочитаемый вид – дополнительные

переменные являются базисными. Приравняв к нулю свободные переменные x1,

x2, x3, x4, получаем базисное неотрицательное решение:

[pic], [pic], [pic], [pic], [pic], [pic], [pic]

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

[pic], по которой пока ничего не производится.

Из выражения (1.1) видно, что наиболее выгодно начинать производить

продукцию третьего вида, т.к. прибыль на единицу выпущенной продукции здесь

наибольшая, поэтому в системе (1.3) принимаем переменную x3 за разрешающую

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

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

положительным коэффициентам при выбранной неизвестной и находим наибольшее

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

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

т.е.

[pic]

Оно соответствует первому уравнению в системе (1.3), и показывает какое

количество изделий третьего вида предприятие может изготовить с учетом

объемов сырья первого вида. Следовательно, в базис вводим неизвестную x3, а

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

системе (1.3) за разрешающее, а разрешающим элементом будет a13=6.

Применив формулы исключения, переходим к новому предпочитаемому виду

системы с соответствующим базисным допустимым решением.

Полный процесс решения приведен в таблице 1, где в последней строке

третьей таблицы нет ни одного отрицательного относительного оценочного

коэффициента

[pic], где [pic], где [pic],

т.е. выполняется критерий оптимальности для максимизируемой функции (1.1).

|Таблица 1 |

|C |Бази|H |30 |11 |45 |6 |0 |0 |0 |Пояснения |

| |с | | | | | | | | | |

| | | |[pic| |[pic|[pic|[pic|[pic|[pic| |

| | | |] | |] |] |] |] |] | |

|0 |[pic|15|3 |2 |6 |0 |1 |0 |0 |[pic] |

| |] |0 | | | | | | | |x3 – разрешающая|

| | | | | | | | | | |[pic] |

|0 |[pic|13|4 |2 |3 |5 |0 |1 |0 | |

| |] |0 | | | | | | | | |

|0 |[pic|12|4 |3 |2 |4 |0 |0 |1 | |

| |] |4 | | | | | | | | |

| |0 | |-30 |-11 |-45 |-6 |0 |0 |0 | |

|45|[pic|25|[pic|[pic|1 |0 |[pic|0 |0 |[pic] |

| |] | |] |] | | |] | | |x1 – разрешающая|

| | | | | | | | | | |[pic] |

|0 |[pic|55|[pic|1 |0 |5 |[pic|1 |0 | |

| |] | |] | | | |] | | | |

|0 |[pic|74|3 |[pic|0 |4 |[pic|0 |1 | |

| |] | | |] | | |] | | | |

| |1125| |[pic|4 |0 |-6 |[pic|0 |0 | |

| | | |] | | | |] | | | |

|45|[pic|14|0 |[pic|1 |-1 |[pic|[pic|0 |Все [pic] |

| |] | | |] | | |] |] | | |

|30|[pic|22|1 |[pic|0 |2 |[pic|[pic|0 | |

| |] | | |] | | |] |] | | |

|0 |[pic|8 |0 |[pic|0 |-2 |[pic|[pic|1 | |

| |] | | |] | | |] |] | | |

| |1290| |0 |7 |0 |9 |6 |3 |0 | |

При этом каждый элемент симплексной таблицы имеет определенный

экономический смысл. Например, во второй симплексной таблице:

|В столбце [pic]: |

|[pic] |Показывает, на сколько следует уменьшить |

| |изготовление изделия третьего вида, если |

| |запланирован выпуск одного изделия первого |

| |вида. |

|[pic]; 3 |Показывают, сколько потребуется сырья второго и|

| |третьего вида, при включении в план одного |

| |изделия первого вида. |

|Т.е. при включении в план одного изделия первого вида, потребуется |

|уменьшение выпуска продукции третьего вида на 0.5 единиц, а также |

|потребуются дополнительные затраты 2.5 единиц сырья второго вида и 3|

|единицы сырья третьего вида, что приведет к увеличению прибыли |

|предприятия на 7.5 денежных единиц. |

|В столбце [pic]: |

|[pic];[pic];[pic] |Показывают, что увеличение объема сырья первого |

| |вида на единицу позволило бы увеличить выпуск |

| |продукции третьего вида на[pic]. |

| |[pic] |

| |что одновременно потребовало бы [pic] единицы |

| |сырья второго вида и [pic] единицы сырья |

| |третьего вида. |

Т.к. в последней строке третьей таблицы 1 нет ни одного отрицательного

относительного оценочного коэффициента, то производственная программа, при

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

т.к., например, коэффициент [pic] при переменной [pic] показывает, что если

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

7 денежных единиц.

Таким образом, получили производственную программу:

[pic], [pic], [pic], [pic]

которая является оптимальной и обеспечивает предприятию наибольшую

возможную прибыль:

[pic]

При этом первый и второй ресурсы будут использованы полностью, т.е.

первый и второй ресурсы образуют «узкие места производства»:

[pic], [pic]

а третий ресурс будет иметь остаток:

[pic]

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

отвечающий оптимальной производственной программе:

[pic]

тогда можно проверить выполнение соотношения [pic]:

[pic]

а т.к. из третьей симплексной таблицы:

[pic], следовательно, соотношение [pic] выполняется.

2. Двойственная задача

Задача, двойственная линейной производственной задаче, например, может

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

на сторону.

Например, в предыдущем п.1. рассмотрена линейная производственная задача

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

заданным технологиям. Предположим, некий предприниматель, занимающийся

производством других видов продукции с использованием трех таких же видов

ресурсов, предлагает «уступить» ему все имеющиеся ресурсы и обещает платить

y1 денежных единиц за каждую единицу первого ресурса, y2 денежных единиц за

каждую единицу второго ресурса и y3 денежных единиц за каждую единицу

третьего ресурса. Возникает вопрос: при каких значениях y1, y2, y3 можно

согласиться с предложением этого предпринимателя.

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

ресурса на единицу каждой продукции, вектор [pic] объемов ресурсов и вектор

[pic] удельной прибыли имели вид:

[pic] [pic] [pic]

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

должно затратить 3 единицы ресурса первого вида, 4 единицы ресурса второго

вида и 4 единицы ресурса третьего вида, за что оно получит прибыль

30 денежных единиц. Следовательно, согласиться с предложением

предпринимателя можно, если он заплатит не меньше, т.е. в ценах y1, y2, y3

это условие будет иметь вид:

[pic]

Аналогично и с продукцией второго, третьего и четвертого вида, при этом,

за все имеющиеся ресурсы, предприниматель должен заплатить не меньше:

[pic] денежных единиц.

Следовательно, предприниматель будет искать такие значения y1, y2, y3,

при которых эта сумма была бы как можно меньше. При этом речь идет о ценах,

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

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

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

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

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

[pic]

минимизирующий общую оценку всех ресурсов

[pic]

при условии, что по каждому виду продукции суммарная оценка всех ресурсов,

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

получаемой от реализации единицы этой продукции, т.е.:

[pic]

причем оценки ресурсов не могут быть отрицательными, т.е.: [pic], [pic],

[pic]

Решение полученной задачи можно найти с помощью второй теоремы

двойственности: дефицитный (избыточный) ресурс, полностью (неполностью)

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

(нулевую) оценку, и технология, применяемая с ненулевой (нулевой)

интенсивностью, имеет нулевую (положительную) оценку.

Т.е. для оптимальных решений [pic] и [pic] пары двойственных задач

необходимо и достаточно выполнение условий:

[pic] [pic]

Ранее в п.1. было найдено, что [pic], [pic], а [pic] и [pic], тогда:

[pic]

Но т.к. третий ресурс был избыточным (см. п.1.), то по второй теореме

двойственности, его двойственная оценка равна нулю, т.е. [pic]. Тогда

переходим к новой системе уравнений:

[pic]

от куда получаем: [pic], [pic]

Таким образом, получили двойственные оценки ресурсов:

[pic], [pic], [pic]

тогда общая оценка всех ресурсов равна:

[pic]

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

строке симплексной таблицы 1 и имеет определенный экономический смысл:

|[pic] |Показывает, что добавление одной единицы первого ресурса |