Главная Коллекция "Otherreferats" Экономико-математическое моделирование Моделирование экономических процессов

Моделирование экономических процессов

Определение расчетных оценок ресурсов. Математическая модель "расшивки узких мест производства". Решение транспортной задачи методом потенциалов. Моделирование распределения капитальных вложений. Матричная игра как модель сотрудничества и конкуренции.

Рубрика Экономико-математическое моделирование
Вид курсовая работа
Язык русский
Дата добавления 21.04.2011
Размер файла 175,3 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Страница:

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Федеральное агентство по образованию

Государственное образовательное учреждение

Высшего профессионального образования

«ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ УПРАВЛЕНИЯ»

Институт информационных систем управления

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

Курсовая работа

«Прикладная математика»

Москва - 2010

Введение

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

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

Цель курса - дать студентам знания и навыки применения математических методов и моделей при выработке управленческих решений.

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

1.1 Задание

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

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

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

Исходные данные

48 30 29 10

3 2 4 3 198

2 3 1 2 96

6 5 1 0 228

1.2 Формулировка линейной производственной задачи

Сформулируем линейную производственную задачу.

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

Известны:

· Технологическая матрица затрат любого из имеющихся ресурсов на единицу каждого вида продукции А, в которой каждый элемент aij означает необходимое количество i-го ресурса для выпуска j-го вида продукции:

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

· Вектор объемов имеющихся ресурсов В, каждый элемент которого bi означает предельное количество i-го ресурса для выпуска всего объема продукции:

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

· Вектор удельной прибыли C, элементы которого cj означают прибыль от реализации единицы продукции j-го вида (условимся, что реализация произведенной продукции происходит беспрепятственно):

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Требуется:

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

Математическая модель:

- Найти производственную программу:

X=(x1, x2, x3, x4)

- Найти максимизирующую прибыль:

P(x) = 48x1 + 30x2 + 29x3 + 10 x4

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

3х1 + 2x2 + 4х3 + 3х4 ? 198

2х1 + 3х2 + х3 + 2х4 ? 96

6х1 + 5х2 + 1х3 ? 228

Где по смыслу задачи х1 ? 0, х2 ? 0, х3 ? 0, х4 ? 0

1.3 Решение линейной производственной задачи

Получили задачу на условный экстремум. Для ее решения необходимо заменять систему неравенств системой линейных алгебраических уравнений при помощи дополнительных неотрицательных неизвестных x5 x6 x7 :

3х1 + 2x2 + 4х3 + 3х4 + х5 = 198

2х1 + 3х2 + х3 + 2х4 + х6 = 96

6х1 + 5х2 + 1х3 + х7 = 228

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

х1, х2, х3, х4, х5, х6, х7 ? 0

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

Поскольку правые части всех уравнений системы неотрицательны, а сама система линейных алгебраических уравнений имеет предпочитаемый вид (дополнительный переменные х5, х6, х7 являются базисными), приравняв к нулю переменные x1 x2 x3 x4 получаем базисное неотрицательное решение:

x1 =0, x2 =0, x3 =0, x4 =0, x5 = 198, x6 = 96, x7 = 228

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

x1 =0, x2 =0, x3 =0, x4 =0

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

Запишем общее решение системы:

х5 = 198 - 3х1 - 2x2 - 4х3 - 3х4

х6 = 96 - 2х1 - 3х2 - х3 - 2х4

х7 = 228 - 6х1 - 5х2 - х3

Сохраним значения x2 =0, x3 =0, x4 =0 и будем увеличивать только х1. При этом значения базисных переменных должны оставаться неотрицательными.

198 - 3х1 ? 0 х1 ? 66

96 - 2х1 ? 0 х1 ? 48 т.е. 0 ? х1 ? 38

228 - 6х1 ? 0 х1 ? 38

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

x1 = 38, x2 = 0, x3 = 0, x4 = 0, x5 = 84, x6 = 20, x7 = 0

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

Min ( bi / ai4 > 0 ) = min (198/3; 96/2; 228/6) = 196/4

Методом Гаусса-Жордана, применив формулы исключения, получаем для системы уравнений новый предпочитаемый вид:

- х2/2 + 7х3 /2 + 3х4 + х5 -1 х7 /2 = 84

4х2 /3+ х3 /2 + 2х4 + х6 - 1 х7 /3 = 20

х1 + 5х2 / 6 + х3 / 6+ х7 /6 = 38

Приравняв к нулю свободные переменные x2, x3, x4 , x7 получаем базисное неотрицательное решение. Первые четыре компоненты определяют новую производственную программу:

x1 = 38, x2 = 0, x3 = 0, x4 = 0

Исследуем, является ли эта программа наилучшей, то есть, обеспечивает ли она наибольшую прибыль. Для этого выразим функцию прибыли через новые свободные переменные. Из последнего уравнения системы выражаем базисную переменную x1 через свободные, и подставляем в целевую функцию:

P(x) = 48 * (38 - 5х2 / 6 - х3 /6 - х4 / 2 - х7 /6 ) + 30x2 + 29x3 + 10 x4

P(x) = 1824 - 10 x2 + 21 x3 + 10 x4 - 8 х7

Видно, что производственная программа x1 = 38, x2 = 0, x3 = 0, x4 = 0

Не является наилучшей, потому что прибыль будет расти, если мы начнем производить 3 или 4 продукцию. Но наиболее быстро функция растет при возрастании x3. Поэтому принимаем x3 за разрешающую.

Min (84/7/2; 20/1/2; 38/1/6) )= 84/7/2)

Поэтому за разрешающее уравнение принимаем 3 и исключаем x3 всех уравнений системы. Для этого представим целевую функцию в виде уравнения:

- 48x1 - 30x2 - 29x3 - 10 x4 = 0 - P

Припишем его к исходной системе и получим вспомогательную систему:

3х1 + 2x2 + 4х3 + 3х4 + х5 = 198

2х1 + 3х2 + х3 + 2х4 + х6 = 96

6х1 + 5х2 + 1х3 + х7 = 228

- 48x1 - 30x2 - 29x3 - 10 x4 = 0 - P

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

- х2/2 + 7х3 /2 + 3х4 + х5 -1 х7 /2 = 84

4х2 /3+ х3 /2 + 2х4 + х6 - 1 х7 /3 = 20

х1 + 5х2 / 6 + х3 / 6+ х7 /6 = 38

10 x2 - 21 x3 - 10 x4 + 8 х7 = 1824 - P

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

- х2/7 + х3 + 6х4/7 + 2 х5/7 -1 х7 /7 = 24

10х2 /7+ 10х4/7 + х6 - 5 х7 /21 = 4

х1 + 6х2 / 7 +- 1x4/7 - x5/21 +4 х7 /21 = 34

7 x2 + 8 x4 +6x5 + 5 x7 = 2328 - P

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

x1 = 34, x2 = 0, x3 = 24, x4 = 0, x5 = 0, x6 = 4, x7 = 0

то есть определяют производственную программу:

x1 = 34, x2 = 0, x3 = 24, x4 = 0

и остатки ресурсов:

первого вида x5 = 0,

второго вида x6 = 4,

третьего вида x7 = 0

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

P = 2328 - 7 x2 - 8 x4 - 6x5 - 5 x7

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

x2 = 0, x4 = 0, x5 = 0, x7 = 0

Это означает, что производственная программа x1 = 34, x2 = 0, x3 = 24, x4 = 0 является наилучшей и обеспечивает предприятию наибольшую прибыль.

X опт = (34, 0, 24, 0, (0, 4, 0)) и P max = 2328

1.4 Запись в виде симплексной таблицы

C

Базис

B

x1

x2

x3

x4

x5

x6

x7

0

x5

198

3

2

4

3

1

0

0

x6

96

2

3

1

2

0

1

0

x7

228

6

5

1

0

0

0

1

P(X0)

0

-48

-30

-29

-10

0

0

0

C

Базис

B

x1

x2

x3

x4

x5

x6

x7

2

x5

84

0

-1/2

31/2

3

1

0

-1/2

x6

20

0

11/3

2/3

2

0

1

-1/3

x1

38

1

5/6

1/6

0

0

0

1/6

P(X2)

1824

0

10

-21

-10

0

0

8

C

Базис

B

x1

x2

x3

x4

x5

x6

x7

3

x3

24

0

-1/7

1

6/7

2/7

0

-1/7

x6

4

0

13/7

0

13/7

-4/21

1

-5/21

x1

34

1

6/7

0

-1/7

-1/21

0

4/21

P(X3)

2328

0

7

0

8

6

0

5

Выводы.

Оптимальная производственная программа имеет вид:

х1* = 34, х2* = 0, х3* = 24, х4* = 0 или Х* = (34, 0, 24, 0).

Максимальная прибыль равна Z(max) = 2328 денежных единиц.

Использование ресурсов:

Первый и третий ресурсы используются полностью (х5* = 0, х7* = 0),

а второй ресурс имеет остаток х6* = 4 единицы.

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

1.5 Проверка полученного решения

Укажем обращенный базис Q-1, соответствующий оптимальному базисному решению, и проверим выполнение соотношения

Q-1 *В = H

Обращенный базис Q-1, соответствующий оптимальной производственной программе, содержится в последней симплексной таблице на месте единичной матрицы в первой симплексной таблице:

Обращенный базис Q-1

2/7 0 -1/7

Q-1= -4/21 1 -5/21

- 1/21 0 4/21

х5 х6 х7

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Проверим выполнение соотношения:

2/7*198 + 0*96 - 1/7*228 24

Q-1 *B= -4/21*198 + 1*96 - 5/21*228 = 4 = H

-1/21*198 + 0*96 + 4/21*228 34

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

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

Составим математическую модель задачи оптимизации производственной программы с двумя оставшимися переменными (х1 , х3) и решим ее графически.

Воспользуемся тем, что в оптимальной производственной программе х2* = 0, х4* = 0, т.е. продукция второго и четвертого вида не производится. Предположим, что второй и четвертый виды продукции мы не намеревались выпускать с самого начала.

Рассмотрим задачу с оставшимися двумя переменными, сохранив их нумерацию.

Исходные данные примут вид:

Вектор удельной прибыли

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

48

29

Вектор

объемов

ресурсов

3

4

198

2

1

96

6

1

228

Математическая модель задачи будет выглядеть следующим образом:

Найти производственную программу Х (х1, х3),

максимизирующую прибыль Z = 48x1 + 29x3 > max,

при условии ограниченности

имеющихся ресурсов 3х1 + 4х3 ? 198

2х1 + х3 ? 96

6х1 + 1х3 ? 228

где по смыслу задачи х1 ? 0, х3 ? 0

Полученную линейную производственную задачу с двумя переменными можно решить графически.

Построим систему координат, где на горизонтальной оси будем откладывать значения х1, а на вертикальной - значения х3, причем нас интересует только правая верхняя полуплоскость данной системы, поскольку по условию задачи х1 ? 0, х3 ? 0.

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

3х1 + 4х3 = 198 - ограничивающая прямая I

2х1 + х3 = 96 - ограничивающая прямая II

6х1 + х3 = 228 - ограничивающая прямая III

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

Построим вектор-градиент grad Z = (0, 0); (48, 29), указывающий направление наискорейшего возрастания функции P.

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

3х1 + 4х3 = 198 x1=34

6х1 + х3 = 228 x2=24

Z(max) = 48*34 + 29*24 = 2328

2. Двойственная задача линейного программирования

2.1 Задание

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

Применить найденные двойственные оценки ресурсов к решению следующей задачи.

2.2 Формулировка двойственной задачи

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

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

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

Представим, что другое предприятие, производящее другие виды продукции по другим технологиям, но с использованием трех таких же видов ресурсов, которые имеются у нас, предлагает нам «уступить» имеющиеся у нас ресурсы по «договорным» ценам. Возникает вопрос: при каких предложенных ценах мы можем согласиться с таким предложением.

Технологическая матрица А, вектор объемов ресурсов В и вектор удельной прибыли С известны:

3 2 4 3 198

A = 2 3 1 2 B = 96 C = (48 30 29 10)

6 5 1 0 228

а) Обозначим стоимость единицы каждого вида ресурса через вектор У (у1, у2, у3,) значение компонент которого прямо зависит от условий, в которых действует наше предприятие.

б) Для производства единицы продукции первого вида мы должны затратить, как видно из матрицы затрат А, 3, 2 и 4 единиц 1-го, 2-го и 3-го видов ресурсов соответственно (элементы первого столбца матрицы).

В ценах у1, у2, у3 наши затраты на производство одной единицы первого вида продукции составят: 3у1 + 2у2 + 6у3, т.е. столько нам готово заплатить другое предприятие за все ресурсы, идущие на производство первого вида продукции. На рынке за единицу первого вида продукции мы получили бы прибыль в размере 48 денежных единиц.

Следовательно, мы можем согласиться с предложением «уступить» ресурсы, идущие на производство первого вида продукции, только в том случае, если нам заплатят не меньше 48 денежных единиц. Математически это можно выразить неравенством:

3у1 + 2у2 + 6у3 ? 48

Аналогичное условие «уступки» ресурсов мы поставим и по другим видам продукции:

2y1 + 3у2 + 5у3 ? 30

4у1 + у2 + у3 ? 29

3у1 + 2 у2 ? 10

в) Выразим через введенные переменные у1, у2, у3 общую стоимость всех имеющихся ресурсов, которую нам должны заплатить:

F = 198у1 + 96у2 + 228у3 денежных ресурсов

При поставленных нами условиях покупающее ресурсы предприятие будет искать такие значения у1, у2, у3, чтобы общая стоимость всех ресурсов была как можно меньше.

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

Найти вектор двойственных оценок ресурсов: У (у1, у2, у3),

минимизирующий общую оценку всех ресурсов F = 198у1 + 96у2 + 228у3 > min

при условии, что по каждому виду продукции 3у1 + 2у2 + 6у3 ? 48

суммарная оценка всех ресурсов, затрачиваемых на 2y1 + 3у2 + 5у3 ? 30

производство единицы продукции, не меньше 4у1 + у2 + у3 ? 29

прибыли, получаемой от реализации единицы 3у1 + 2 у2 ? 10

этой продукции,

причем оценки ресурсов не могут быть отрицательными у1 ? 0, у2 ? 0, у3 ? 0

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

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

Решение полученной задачи легко найти с помощью второй основной теоремы двойственности (о дополняющей нежесткости), в соответствии с которой для того, чтобы Х (х1, х2, х3, х4) и У (у1, у2, у3) являлись оптимальным решением соответствующих задач двойственной пары, необходимо и достаточно выполнение условий

у1 (3х1 +2x2 + 4х3 + 3х4 - 198) = 0

у2 ( 2х1 + 3х2 + х3 + 2 х4 - 96) = 0

у3 (6х1 + 5х2 + х3 - 228) = 0

х1 (3у1 + 2у2 + 6у3 - 48) = 0

х2 (2y1+ 3у2 + 5у3 - 30) = 0

х3 (4у1 + у2 + у3 - 29) = 0

х4 (3у1 + 2у2 - 10) = 0

Ранее было найдено, что в решении исходной задачи x1 >0, x3 > 0, а x2=0 и x4 = 0, поэтому

3у1 + 2у2 + 6у3 - 48 = 0

4у1 + у2 + у3 - 29 = 0

Так как второй ресурс взят в избытке, то y2 =0:

3у1 + 6у3 - 48 = 0 у1= 6

4у1 + у3 - 29 = 0 y3=5

Таким образом, получили двойственные оценки ресурсов: Yопт = (6,0,5)

Причем общая (минимальная) оценка всех ресурсов равна:

Fmin=2328

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

Экономический смысл двойственных оценок ресурсов у1* = 6, у2* = 0, у3* = 5 показывает, что добавление одной единицы 1-го (2-го, 3-го) ресурса обеспечит прирост прибыли на 6 (0, 5) денежных единиц.

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

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

3.1 Задание

Сформулировать задачу о «расшивке узких мест производства» и составить математическую модель. Определить область устойчивости двойственных оценок, где сохраняется структура программы производства. Решить задачу о «расшивке узких мест производства» при условии, что дополнительно можно получить от поставщиков не более одной трети первоначально выделенного объема ресурса любого вида (если задача окажется с двумя переменными, то только графически); найти план приобретения дополнительных объемов ресурсов, дополнительную возможную прибыль.

Составить сводку результатов.

3.2 Формулировка задания и составление математической модели

Решив задачу о рациональном использовании имеющихся ресурсов, мы выяснили, что первый и третий виды ресурсов расходуются полностью, т.е. образуют «узкие места производства». Будем расширять производство за счет увеличения объема дефицитных ресурсов.

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

Пусть T (t1, t2, t3) - вектор дополнительных объемов ресурсов, каждая компонента которого обозначает искомое дополнительное количество соответствующего вида ресурса. Поскольку дополнительно мы заказываем только дефицитные ресурсы, а второй ресурс является избыточным, то t2* = 0

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

W = 6t1 + 0t2 + 5t3 = 6t1 + 5t3

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

H + Q-1T ? 0,

где Q-1 - обращенный базис, т.е. матрица, которая содержится в последней симплексной таблице на месте единичной матрицы в первой симплексной таблице, Н - вектор оптимальных значений базисных переменных в последней симплексной таблице, а Т - искомый вектор дополнительных объемов ресурсов.

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

В данном случае также должно выполняться условие, что дополнительно можно получить от поставщиков не более одной трети первоначально выделенного объема ресурса любого вида:

T ? 1/3 B

Математическая модель задачи будет выглядеть следующим образом:

Найти вектор дополнительных объемов ресурсов T (t1, 0, t3),

максимизирующий суммарный прирост прибыли W = 6t1 + 5t3 > max,

при условии сохранения структуры

производственной программы

и двойственных оценок ресурсов H + Q-1T ? 0:

24 2/7 0 -1/7 t1 0

4 + -4/21 1 -5/21 * 0 ? 0

34 -1/21 0 4/21 t3 0

ИЛИ

- 2/7 t1 + t3/7 ? 24

Область устойчивости 4/21t1+ 5t3/21 ? 4

двойственных оценок ресурсов 1/21t1 - 4/21t3 ? 34

где по дополнительному условию задачи t1 ? 186/3

t3 ? 196/3

и по смыслу задачи t1 ? 0, t3 ? 0

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

3.3 Решение задачи о «расшивке узких мест» графически

Построим систему координат, где на горизонтальной оси будем откладывать значения t1, а на вертикальной - t3, причем нас интересует только правая верхняя полуплоскость данной системы, поскольку по условию задачи t1 ? 0, t3 ? 0.

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

- 2/7 t1 + t3/7 = 24

4/21t1+ 5t3/21 = 4

1/21t1 - 4/21t3 = 34

t1 = 198/3

- ограничивающие прямые IV, V

t3 = 228/3

Построим вектор-градиент grad W = (0, 0); (6, 5), указывающий направление наискорейшего возрастания функции W.

Определяем, что максимального значения в области допустимого множества функция W достигнет в точке Q, которая является пересечением II и IV прямых. Следовательно, координаты этой точки определяют оптимальное дополнительное количество ресурсов:

t1 = 198/3 t1* = 66

t3 = 228/4 t3* = 76

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

W* = 6t1* + 5t3* = 6*66 + 5*76 = 776 денежных единиц

сj

48

30

29

10

b

x4+i

y*i

t*i

3

2

4

3

198

0

6

66

aij

2

3

1

2

96

4

0

0

6

5

1

0

228

0

5

76

х*j

34

0

24

0

2328

412

Дj

0

7

0

8

4. Транспортная задача линейного программирования

4.1 Задание

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

48 30 29 40

40 3 6 4 3

45 2 3 1 3

70 6 5 1 4

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

4.2 Формулировка транспортной задачи

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

Известны:

· Вектор объемов производства, указывающий количество однородного продукта, сосредоточенное в каждом из трех пунктов производства (хранения):

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

· Вектор объемов потребления, указывающий количество данного продукта, необходимое каждому из четырех пунктов потребления:

В ( 48 30 29 40 )

· Матрица транспортных издержек С, в которой каждый элемент сij означает стоимость перевозки единицы продукта из i-го пункта отправления (производства) в j-ый пункт назначения (потребления):

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Требуется:

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

? a = 40 + 45 + 70 = 147

? b = 48 + 30 + 29 + 40 = 155

Таким образом, объем производства больше объема потребления аi < bj на 8 единиц, следовательно, данная модель транспортной задачи является открытой.

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

4.3 Решение транспортной задачи методом потенциалов

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

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

Следует иметь в виду, что по любой транспортной таблице можно восстановить предпочитаемый эквивалент системы уравнений 3) - 4), а в таблице записаны лишь правые части уравнений, причем номер клетки показывает, какая неизвестная в соответствующем уравнении является базисной. Так как в системе 3) - 4) ровно (m + n - 1) линейно независимых уравнений, то в любой транспортной таблице должно быть m + n - 1 занятых клеток.

1

2

3

4

5

Производители

1

3[40]

6

4

3

0

40

2

2[8]

3[30]

1[7]

3

0

45

3

6

5

1[22]

4[40]

0[8]

70

потребители

48

30

29

40

8

Решаем транспортную задачу методом потенциалов, в соответствии с которым каждому пункту производства ставится в соответствие потенциал pi, а каждому пункту потребления - потенциал qj.

Обозначим через м (p1, p2, p3, q1, q2, q3, q4) вектор симплексных множителей или потенциалов.

Каждой клетке транспортной таблицы соответствует некоторая оценка:

ij = pi + qj - cij i = 1, 2, 3; j = 1, 2, 3, 4

Один из потенциалов можно выбрать произвольно, так как в системе уравнений 3) - 4)одно уравнение линейно зависит от остальных.

Положим, что p1 = 0

Остальные потенциалы находим из условия, что для базисных клеток ij = 0:

11 = 0, p1 + q1 - c11 = 0, q1 = 3

12 = 0, p1 + q2 - c12 = 0, q2 = 4

22 = 0, p2 + q2 - c22 = 0, р2 = -1

23 = 0, p2 + q3 - c23 = 0, q3 = 2

24 = 0, p2 + q4 - c24 = 0, q4 = 5

34 = 0, p3 + q4 - c34 = 0, р3 = - 1

35 = 0, p3 + q5 - c35 = 0, q5 = 1

Вычисляем оценки всех свободных клеток вычисляем по формуле ij = pi + qj - cij: 12 = p1 + q2 - c12 = 0+6-6 = 0

13 = p1 + q3 - c13 = 0 + 4 - 4 = 0

14 = p1 + q4 - c14 = 0 + 7 - 3 = 4

15 = p1 + q5 - c15 = 0 + 3 - 0 = 3

24 = p2 + q4 - c24 = -3 + 7 - 3 = 1

25 = p2 + q5 - c25 = -3+3-3 = -3

31 = p3 + q1 - c31 = -3 + 3 - 6= - 6

32 = p3 + q2 - c32 = - 3 + 6 - 5 = -2

Находим наибольшую положительную оценку:

max () = 4 = 14

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

1

2

3

4

5

Производители

1

3[40][-]

6

4

3[+]

0

40

2

2[8][+]

3[30]

1[7][-]

3

0

45

3

6

5

1[22][+]

4[40][-]

0[8]

70

Потребители

48

30

29

40

8

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3) = 7. Прибавляем 7 к объемам грузов, стоящих в плюсовых клетках и вычитаем 7 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

1

2

3

4

5

Производители

1

3[33]

6

4

3[7]

0

40

2

2[15]

3[30]

1

3

0

45

3

6

5

1[29]

4[33]

0[8]

70

Портребители

48

30

29

40

8

Находим новые потенциалы и оценки всех свободных клеток.

11 = 0, p1 + q1 - c11 = 0, q1 = 3

12 = 0, p1 + q2 - c12 = 0, q2 = 4

22 = 0, p2 + q2 - c22 = 0, р2 = - 1

23 = 0, p2 + q3 - c23 = 0, q3 = 0

25 = 0, p2 + q5 - c25 = 0, q5 = -1

34 = 0, p3 + q4 - c34 = 0, q4 = 3

35 = 0, p3 + q5 - c35 = 0, р3 = 1

12 = -2 13 = - 4 14 = 0 15 = -1

23 = -2 24 = 0 25 = -2

31 = -2 32 = 0

Все ij ? 0, следовательно, оптимальным базисным решением будет

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Общая стоимость перевозок составит:

F(x) = 3*33 + 3*7 + 2*15 + 3*30 + 1*29 + 4*33 + 0*8 = 401

Экономический смысл потенциалов и оценок клеток транспортной таблицы.

Оценка свободной клетки ij показывает, насколько уменьшатся суммарные расходы по перевозке груза, если поставить единицу от i-го производителя j-му потребителю (перераспределив основные поставки так, чтобы сохранился баланс по строкам и столбцам).

Потенциалы указывают на то, сколько каждый производитель уплачивает перевозчику (pi) за вывоз единицы груза; каждый потребитель уплачивает перевозчику (qj) за получение единицы груза. При это м необходимо выполнение условия, что сумма цен, взимаемых с пары «производитель - потребитель» не должна превосходить реальной стоимости перевозки груза между ними, что в итоге приводит к задаче, двойственной по отношению к транспортной, и интерпретации оценок клеток и потенциалов, основанной на теоремах двойственности.

В реальных условиях pi и qj - не цены, а надбавки к основному тарифу перевозчика, единому для всех производителей и потребителей.

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

5.1 Задание

Методом динамического программирования решить задачу распределения капитальных вложений между четырьмя предприятиями производственного объединения, располагающего суммой в 700 тыс. руб., при условии, что выделяемые суммы кратны 100 тысячам, используя следующие исходные данные:

xj

0

100

200

300

400

500

600

700

f1(x1)

0

37

64

87

105

120

134

145

f2(x2)

0

48

75

98

120

132

144

156

f3(x3)

0

85

100

111

118

124

129

132

f4(x4)

0

47

70

80

86

91

94

98

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

Рассмотрим нелинейную задачу распределения капитальных вложений между предприятиями производственного объединения.

Пусть 4 фирмы образуют объединение. Рассмотрим задачу распределения инвестиций в размере 700 тыс. рублей по этим 4 фирмам. Размер инвестиций пусть будет кратен 100 тыс. рублей. Эффект от направления i-й фирме инвестиций в размере хj (тыс. рублей) (прирост прибыли на данном предприятии) выражается функцией fi(xi), i = 1, 2, 3, 4. Функции fi(xi) заданы в исходных данных задачи, где, например, число 37 означает, что прирост прибыли на 1-ом предприятии при инвестировании в него 100 тыс. рублей составит 37 тыс. рублей. На практике определение данных функции - довольно трудоемкая экономическая задача.

Приходим к задаче:

Требуется найти такое распределение (х1, х2, х3, х4) капитальных вложений между четырьмя предприятиями, которое максимизирует суммарный прирост мощности или прибыли:

Z = f1(x1) + f2(x2) + f3(x3) + f4(x4) > max

при ограничении по общей сумме капитальных вложений

х1 + х2 + х3 + х4 = 700

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

х1, х2, х3, х4 = 0, или 100 000, или 200 000, или 300 000, или 400 000, или 500 000, или 600 000, или 700 000

где xi - пока еще неизвестный размер инвестиций i-й фирме.

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

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

Воспользуемся методом динамического программирования для решения полученной задачи распределения капитальных вложений. Последовательно ищется оптимальное распределение для k = 2, 3 и 4 фирм.

Пусть первым двум фирмам выделено тыс. рублей инвестиции ( - параметр состояния, который может изменяться от 0 до 700). Обозначим через F2 () максимальный прирост прибыли на первых двух предприятиях.

Если из тыс. рублей 2-ая фирма получит х2 тыс. рублей, то максимальный прирост прибыли на 2-ой фирме можно выразить как f2(x2).

На долю 1-ого предприятия останется - х2 тыс. рублей, а максимальный прирост прибыли на 1-ом предприятии составит F1 ( - х2).

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

F2 () = max {f2(x2) + F1 ( - х2)}

0 ? x2 ? 700

Используя исходные данные из задания, строим Таблицу № 1.1. Значения f2(x2) складываем со значениями F1 (-x2) = f1(-x2) и на каждой побочной диагонали находим наибольшее число, которое помечаем звёздочкой.

Таблица № 1.1

?-х2

0

100

200

300

400

500

600

700

X2

F1(?-x2)

f2(x2)

0

37

64

87

105

120

134

145

0

0

0

37

64

87

105

120

134

145

100

48

48*

85*

112*

135

153

168

182

---

200

75

75

112*

139*

162*

180

195

---

---

300

98

98

135

162*

185

203

---

---

---

400

120

120

157

184

207*

---

---

---

---

500

132

132

169

196

---

---

---

---

---

600

144

144

181

---

---

---

---

---

---

700

156

156

---

---

---

---

---

---

---

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

В Таблицу № 1.2. в графу F2 () заносим значения максимального прироста прибыли на первых двух предприятиях, а в графе указываем соответствующий каждому значению F2() размер инвестиций 2-ому предприятию.

Таблица № 1.2.

0

100

200

300

400

500

600

700

F2()

0

48

85

112

139

162

185

207

()

0

100

100

200

200

300

300

400

100

200

Далее действуем также: находим функции F3 (), F4 (), используя на каждом k-ом шаге основное рекуррентное соотношение:

Fk (о)=max {fk(xk) + Fk-1(о - xk)}

0 ? xk ? 700

для k = 2,3,4

Заполняем Таблицу № 2.1., аналогичным способом определяя максимальный прирост прибыли от распределения капитальных вложений между тремя предприятиями (F3 ()).

Таблица № 2.1.

?-х3

0

100

200

300

400

500

600

700

Х3

F2(?-x3)

f3(x3)

0

48

85

112

139

162

185

207

0

0

0

48

85

112

139

162

185

207

100

85

85*

133*

170*

197*

224*

247*

270*

---

200

100

100

148

185

212

239

262

---

---

300

111

111

159

196

223

250

---

---

---

400

118

118

166

203

230

---

---

---

---

500

124

124

172

209

---

---

---

---

---

600

129

129

177

---

---

---

---

---

---

700

132

132

---

---

---

---

---

---

---

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

В Таблицу № 2.2. в графу F3 () заносим значения максимального прироста прибыли на трех предприятиях, а в графе указываем соответствующий функции F3() размер инвестиций 3-ему предприятию.

Таблица № 2.2.

0

100

200

300

400

500

600

700

F3()

0

85

133

170

197

224

247

270

()

0

100

100

100

100

100

100

100

В Таблице № 3.1., определяющей максимальный прирост прибыли от распределения капитальных вложений между четырьмя предприятиями F4(), заполняем только одну диагональ для значения = 700, поскольку данный этап является завершающим, предприятий всего четыре и между ними необходимо распределить именно 700 тыс. рублей.

Таблица № 3.1.

?-х4

0

100

200

300

400

500

600

700

Х4

F(?-x4)

f2(x4)

0

85

133

170

197

224

247

270

0

0

270

100

47

294*

---

200

70

294*

---

---

300

80

277

---

---

---

400

86

256

---

---

---

---

500

91

224

---

---

---

---

---

600

94

179

---

---

---

---

---

---

700

98

98

---

---

---

---

---

---

---

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

Z max = 294 тыс. рублей,

причем 4-ому предприятию должно быть выделено

х4* = х4 (700) = 200 тыс. рублей

ЛИБО

х4** = х4 (700) = 100 тыс. рублей.

На долю остальных трех предприятий остается в 1-ом случае (х4* = 200) 500 тыс. рублей, во 2-ом случае (х4** = 100) 600 тыс. рублей.

Из Таблицы № 2.2. видно, что 3-ему предприятию должно быть выделено

в 1-ом случае (х4* = 200): х3* = х3 (700 - х4*) = х3 (500) = 100 тыс. рублей

во 2-ом случае (х4** = 100): х3** = х3 (700 - х4**) = х3 (600) = 100 тыс. рублей.

Таким образом, х3* = 100 тыс. рублей.

Продолжая обратный процесс, находим:

в 1-ом случае (х4* = 200): х2* = х2 (700 - х4* - х3*) = х2 (400) = 200 тыс. рублей

во 2-ом случае (х4** = 100): х2** = х2 (700 - х4** - х3*) = х2 (500) = 300 тыс. рублей

ЛИБО

х2*** = х2 (500) = 200 тыс. рублей = х2*.

На долю 1-ого предприятия останется:

х1* = 700 - х4* - х3* - х2* = 200 тыс. рублей

х1** = 700 - х4** - х3** - х2*** = 300 тыс. рублей

х1*** = 700 - х4** - х3** - х2** = 200 тыс. рублей = х1*

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

1-ый вариант

х1* = 200;

Z max = 294

х2* = 200;

х3* = 100;

х4* = 200

2-ой вариант

х1* = 200;

Z max = 294

х2** = 300;

х3* = 100;

х4** = 100

3-ий вариант

х1** = 300;

Z max = 294

х2* = 200;

х3* = 100;

х4** = 100

В качестве проверки правильности решения задачи можно использовать равенство:

Z max = f1(x1) + f2(x2) + f3(x3) + f4(x4)

1-ый вариант: 64 + 75 + 85 + 70 = 294 тыс. рублей

2-ой вариант: 64 + 98 + 85 + 47 = 294 тыс. рублей

3-ий вариант: 87 + 75 + 85 + 47 = 294 тыс. рублей

Следовательно, полученные решения верны.

6. Матричная игра как модель сотрудничества и конкуренции

6.1 Задание

Рассмотреть матричную игру как модель сотрудничества и конкуренции. Найти решение игры. Указать как проявляется конкуренция между игроками и сотрудничество между ними. Использовать следующие данные:

1 -2 1 4 3

-6 -2 -6 -5 -3

8 0 8 -5 3

-6 9 -6 -1 0

Пусть игроки - Первый и Второй, играют в матричную игру с матрицей . Пусть стратегия Первого есть , а Второго - . Тогда выигрыш Первого есть случайная величина (с.в.) с рядом распределения:

W(P,Q)

a11

...

aij

...

amn

p1q1

...

piqj

...

pmqn

Математическое ожидание этой с.в., т.е. есть средний выигрыш Первого. Пусть есть дисперсия этой с.в. Естественно назвать среднее квадратическое отклонение с.в. , т.е. риском для Первого при игре со стратегиями . Поскольку выигрыш Первого есть проигрыш для Второго, то есть случайный проигрыш Второго и вполне естественно можно назвать риском игры с такими стратегиями и для Второго.

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

Математическое ожидание с. в. называется ценой игры, обозначим ее .

Вычислим дисперсию выигрыша Первого при оптимальных стратегиях игроков.

.

Так как , а через сумма обозначена .

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

Заметим теперь, что если Первый играет со стратегией , а Второй отвечает -й чистой стратегией, то выигрыш первого есть с.в. с рядом распределения:

W(P*,j)

a1j

...

aij

...

amj

p1*

...

pi*

...

pm*

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

Теперь можно сделать следующий вывод:

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

Чисто математически можно сказать, что в описанной ситуации риск выигрыша Первого не зависит от его стратегии непрерывно.

6.2. Решение

Вначале проведем анализ на доминирование. В нашем примере 1 строка доминирует 2. Так как строки выбирает первый игрок, мы исключаем из матрицы доминируемые строки. Исключая вторую строку получим:

1 -2 1 4 -3

А = 8 0 8 -5 3

-6 9 -6 -1 0

Третий столбец доминирует первый. Исключаем 3 столбец.

б

1 -2 4 -3 -3

А = 8 0 -5 3 -5

-6 9 -1 0 -6

в 8 9 4 3

Находим минимумы по строкам. Нижняя цена игры б = -3. Найдем максимумы по столбцам. Верхняя цена игры в = 3. Поскольку б ? в, то решения в чистых стратегиях нет. Будем искать решения в смешанных стратегиях. Предварительно прибавим к каждому элементу платежной матрицы 6, сделав их неотрицательными. Решения игры при этом не изменится, а цена игра возрастет на 6 и будет больше 0.

Матрица примет следующий вид:

7 4 10 3

А = 14 6 1 9

0 15 5 6

В силу теоремы Неймана решение сводится к нахождению решений симметричной пары взаимно двойственных задач линейного программирования. Пусть Р = (р1 ;р2; р2); Q = ( q1; q2; q3; q4) - стратегии игроков. Найдем сначала Q*. Проигрыш второго игрока будет не больше чем цена игры.

7q1 + 4q2 + 10q3 + 3q4 ? v

14q1 + 6q2 + q3 + 9q4 ? v

15q2 + 5q3 + 6q4 ? v

Разделим каждое из неравенств на v>0 и введем обозначение q1/v = xi ?0 (I = 1-4)

Получим:

7x1 + 4x2 + 10x3 + 3x4 ? 1

14x1 + 6x2 + x3 + 9x4 ? 1

15x2 + 5x3 + 6x4 ? 1

X1 + x2 + x3 + x4 = 1/v

Имеем задачу линейного программирования. Найти вектор х = (х1, х2, х3, х4), который обеспечивает максимум целевой функции. Z= x1 + x2+ x3 + x4 > max

При следующих линейных ограничениях:

7x1 + 4x2 + 10x3 + 3x4 ? 1

14x1 + 6x2 + x3 + 9x4 ? 1

15x2 + 5x3 + 6x4 ? 1

х1, х2, х3, х4 ? 0

c

Базис

H

1

1

1

1

0

0

0

Пояснения

x1

x2

x3

x4

x5

x6

x7

0

x5

1

7

4

10

3

1

0

0

Min = 1/9

0

0

x6

1

14

6

1

9

0

1

0

0

x7

1

0

15

5

6

0

0

1

Z-Z0

0-Z

-1

-1

-1

-1

0

0

0

C

Базис

H

x1

x2

x3

x4

x5

x6

x7

Пояснения

0

x5

2/3

21/3

2

92/3

0

1

-1/3

0

Min = 2/29

1

x4

1/9

15/9

2/3

1/9

1

0

1/9

0

0

x7

1/3

-91/3

11

41/3

0

0

-2/3

1

Z-Z0

1/9 - Z

5/9

-1/3

-8/9

0

0

1/9

0

C

Базис

H

x1

x2

x3

x4

x5

x6

x7

Пояснения

1

x3

2/29

7/29

6/29

1

0

3/29

-1/29

0

Min = 29/8497

1

x4

3/29

146/87

56/87

0

1

-1/87

10/87

0

0

x7

1/29

-1011/29

103/29

0

0

-13/29

-15/29

1

Z-Z0

5/29 - Z

67/87

-13/87

0

0

8/87

7/87

0

C

Базис

H

x1

x2

x3

x4

x5

x6

x7

Пояснения

1

x3

487780/7145977

3243737/7145977

0

1

0

804837/7145977

-170723/7145977

-174/8497

Все ? J ? 0

1

x4

2170621/21437931

24072963/21437931

0

0

1

121945/7145977

3170570/21437931

-1624/25491

1

x2

29/8497

-1232/8497

1

0

0

-377/8497

-435/8497

29/293

Z-Z0

(3707128/21437931) - Z

13218838/21437931

0

0

0

609725/7145977

1560896/21437931

377/25491

Оптимальный план можно записать так:

x3 = 487780/7145977

x4 = 2170621/21437931

x2 = 29/8497

Z max=0.172923

Цену игры найдем по следующей формуле:

V = 1/Z V= 1/0.172923= 5, 7829072

Q* = v * X*

Q = ( 0; 0,01973648; 0,3947372; 0,58552745)

Найдем теперь оптимальную стратегию Р* первого игрока. Если первый игрок применяет свою оптимальную стратегию, то второй игрок не может улучшить свое положение, отступая от своей оптимальной стратегии. В случае использования вторым игроком своих чистых стратегий, а первым игроком своей оптимальной стратегии выигрыш первого будет не меньше, чем цена игры:

7p1 + 14 p2 ? v

4 p1 + 6 p2 + 15 p3 ? v

10 p1 + p2 + 5 p3 ? v

3 p1 + 9p2 + 6p3 ? v

Разделим каждое из неравенств на V > 0 и введем обозначения:

Рi/v = yi ?0 (I = 1-3)

Получим:

7y1 + 14 y2 ? 1

4 y1 + 6 y2 + 15 y3 ? 1

10 y1 + y2 + 5 y3 ? 1

3 y1 + 9y2 + 6y3 ? 1

Y1 + y2 + y3 = 1/ V

Имеем задачу линейного программирования. Найти вектор y = (y1, y2, y3), который обеспечивает максимум целевой функции. L= y1 + y2+ y3 > min

При следующих линейных ограничениях:

7y1 + 14 y2 ? 1

4 y1 + 6 y2 + 15 y3 ? 1

10 y1 + y2 + 5 y3 ? 1

3 y1 + 9y2 + 6y3 ? 1

Эта задача является двойственной по отношению к рассмотренной выше задаче. Решение задачи возьмем из последней симплексной таблицы.

Y опт = (0, 08532423; 0, 07281001; 0, 01478953)

Lmin = Z max = 0,1729237

V = 1/Z V= 1/0.172923= 5, 7829072

Далее найдем Р*

P* = v* y опт Р* = (0, 49342193; 0, 42105347; 0, 0855263)

Возвращаемся к исходной матрице. Решение этой игры имеет вид:

Р* = (0, 49342193; 0; 0, 42105347; 0, 0855263)

Q *= ( 0; 0,01973648; 0; 0,3947372; 0,58552745)

V=0

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

R0= v12, 2999808

D (p*) = 30, 5197857 r= v30, 5197857

D (p*) = 8, 9013179 r= v8, 9013179

D (p*) = 30, 5197857 r= v30, 5197857

D (p*) = 18, 5066117 r= v30, 5197857

D (p*) = 8, 2302777 r= v8, 2302777

D (p1) = 11, 6644874 r= v 11, 6644874

D (p2) = 15, 2171222 r= v15, 2171222

D (p3) = 15, 1381016 r= v15, 1381016

D (p4) = 1, 9933856 r= v1, 9933856

Минимальное значение риска равно v1, 9933856 и меньше r0. Этот риск соответствует ситуации, когда первый игрок использует свою 4 чистую стратегию р1, а второй игрок оптимальную Q*. Однако играть с таким риском можно только с согласия 2 игроков, т.е. при их сотрудничестве друг с другом.

7. Задача о максимальном потоке в сети

7.1 Задание

Рассмотреть задачу о максимальном потоке в сети. Решить конкретную задачу на сети с 8-9 вершинами.

Рисунок 6

Определить максимальный поток в сети, изображенной на Рисунке 6 из вершины x0 в вершину x8, где числа на дугах, снабженные стрелками, означают пропускные способности этих дуг в указанных направлениях.

7.2 Решение

Составим матрицу пропускных способностей дуг данной сети и представим сеть в матричной форме (см. Таблицу 1).

Таблица 1

xj

xi

x0

x1

x2

x3

x4

x5

x6

x7

x0

2

4

2-

x1

1

5

x2

3

x3

+

5

1

6-

x4

2

5

x5

4

1

3

x6

2

8

x7

+

5

2

В качестве начального возьмем нулевой поток z0ij = 0. Найдем какой-нибудь путь, идущий из x0 в x7 по ненасыщенным дугам. Для этого в нулевой строке таблицы выберем какой-нибудь элемент cij, отличный от нуля, например c03. Из вершины x0 можно перейти в x3. Для наглядности дугу (x0, x3) проведем прямо в нулевой строке таблицы из нулевого столбца в 3-й. Теперь мы находимся в вершине x3. Чтобы зафиксировать это, сместимся по пятому столбцу до строки с тем же 3-м номером. В 3-й строке имеется 3 ненулевых элемента соответственно в 4-м, 5-м и 7-м столбцах. Это означает, что из x3 можно перейти или в x4, в x5 или в x7. Пойдем в сток x7. Этот переход изображен стрелкой в 3-й строке с началом в 3-м столбце и концом в 7-м. Таким образом, по таблице пропускных способностей дуг сети мы нашли путь, ведущий по ненасыщенным дугам из источника в сток:

?1 = [x0, x3, x7].

Теперь по таблице надо узнать пропускную способность ?1 найденного пути и уменьшить пропускные способности всех дуг этого пути на ?1, а симметричных им дуг - увеличить на ?1. Для этого отмечаем знаком «-» числа в тех клетках, где находятся концы дуг, а числа в клетках, симметричных указанным относительно главной диагонали, отмечаем знаком «+». Пропускная способность найденного пути, очевидно, равна наименьшему среди чисел, отмеченных знаком «-» (Таблица 1).

?1 = 2

Из всех чисел, отмеченных знаком «-», вычитаем наименьшую пропускную способность ?1. Получаем Таблицу 2. Это - сеть с измененными пропускными способностями дуг.

Таблица 2

xj

xi

x0

x1

x2

x3

x4

x5

x6

x7

x0

2

4-

x1

1

5

x2

+

3-

x3

2

5

1

4

x4

2+

5-

x5

4

1

3

x6

2

8

x7

2

5+

2

Ищем новый путь, идущий из источника в сток по ненасыщенным дугам и процедуру повторяем. Получаем путь ?2 и пропускную способность ?2:

?2 = [x0, x2, x4, x7]

?2 = 3

Далее

Таблица 3

xj

xi

x0

x1

x2

x3

x4

x5

x6

x7

x0

2-

1

x1

+

1

5-

x2

3

x3

2

5

1

4

x4

5

2

x5

4+

1

3-

x6

2+

8-

x7

2

8

2+

?3 = [x0, x1, x5, x6, x7]

?3 = 2

Таблица 4

xj

xi

x0

x1

x2

x3

x4

x5

x6

x7

x0

1

x1

2

1

3

x2

3

x3

2

5

1

4

x4

5

2

x5

6

1

1

x6

4

6

x7

2

8

4

Из Таблицы 4 видно, что не существует ни одного пути из источника в сток. (Из x0 можно перейти только в x2, а оттуда - обратно в x0). Следовательно, увеличить поток нельзя.

Для определения величины полученного максимального потока вычитаем из элементов Таблицы 1 соответствующие элементы Таблицы 4. Записывая только положительные из найденных разностей, получаем Таблицу 5, указывающую максимальный поток в заданной сети с величиной

w* = z37 + z47 + z67 = ?1 + ?2 + ?3 = 7

Таблица 5

xj

xi

x0

x1

x2

x3

x4

x5

x6

x7

x0

2

3

2

x1

2

x2

3

x3

2

x4

3

x5

2

x6

2

x7

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

8.1 Задание

Провести анализ доходности и риска финансовых операций по следующим исходным данным:

Q1:

2

6

8

12

1/5

1/5

1/5

2/5

Q2:

0

1

5

14

1/5

2/5

1/5

1/5

Q3:

2

4

6

18

1/5

2/5

1/5

1/5

Q4:

0

8

16

20

1/2

1/8

1/8

1/4

Рассмотрим финансовые операции в качестве случайных величин

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

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

Страница:


Подобные документы

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

    Экономико-математическая модель прикрепления пунктов отправления к пунктам назначения, расчет оптимального плана перевозок. Решение транспортной задачи метолом потенциалов (перераспределение ресурсов по контуру), пример вычислительного алгоритма.

    учебное пособие [316,8 K], добавлен 17.10.2010

  • Решение транспортной задачи распределения методом потенциалов

    Формулировка проблемы в практической области. Построение моделей и особенности экономико-математической модели транспортной задачи. Задачи линейного программирования. Анализ постановки задач и обоснования метода решения. Реализация алгоритма программы.

    курсовая работа [56,9 K], добавлен 04.05.2011

  • Экономико-математическое моделирование в менеджменте

    Решение графическим методом задачи линейного программирования с двумя неизвестными. Решение транспортной задачи методом северо-западного угла и методом минимальной стоимости. Системы массового обслуживания. Стохастическая модель управления запасами.

    контрольная работа [458,1 K], добавлен 16.03.2012

  • Математическое моделирование в управлении

    Статистический анализ в Excel. Очистка информации от засорения, проверка закона распределения, корреляционный и регрессионный анализ двумерной и трехмерной модели. Математическая модель и решение задачи оптимального управления экономическим процессом.

    контрольная работа [447,2 K], добавлен 04.11.2009

  • Оптимальный план распределения минеральных удобрений на примере СХПК "Звезда" Батыревского района

    Математическое моделирование экономических явлений и процессов. Разработка рациональной системы удобрения с грамотным сочетанием органических и минеральных удобрений на примере СХПК "Звезда" Батыревского района. Числовая экономико-математическая модель.

    курсовая работа [56,1 K], добавлен 23.12.2013

  • Транспортная задача

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

    курсовая работа [251,0 K], добавлен 03.07.2012

  • Анализ экономических задач оптимизации

    Экономико-математическая модель оптимального плана выпуска продукции. Оптимальная организация рекламной компании. Решение транспортной задачи: нахождение суммарных затрат на перевозку. Задача об оптимальном назначении (линейного программирования).

    контрольная работа [812,0 K], добавлен 29.09.2010

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

    Экономико-математическая модель получения максимальной прибыли, её решение графическим методом. Алгоритм решения задачи линейного программирования симплекс-методом. Составление двойственной задачи и её графическое решение. Решение платёжной матрицы.

    контрольная работа [367,5 K], добавлен 11.05.2014

  • Имитационное моделирование экономических процессов

    Статистическая модель случайного процесса. Численный метод Монте-Карло. Типы имитации, ее достоинства и возможности. Простая имитационная модель системы обработки документов. Использование для моделирования языка Siman. Его основные моделирующие блоки.

    презентация [1,6 M], добавлен 22.10.2014

  • Моделирование хозяйственной деятельности предприятия

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

    контрольная работа [104,3 K], добавлен 30.11.2010

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.

© 2000 — 2023, ООО «Олбест» Все права защищены