Некрасова М.Г. Методы оптимизации - файл n1.doc

приобрести
Некрасова М.Г. Методы оптимизации
скачать (3013.5 kb.)
Доступные файлы (1):
n1.doc3014kb.22.08.2012 14:29скачать

n1.doc

1   ...   4   5   6   7   8   9   10   11   12
Задача 2. На заданной сети дорог имеется несколько маршрутов по доставке груза из пункта 1 в пункт 10. Стоимость перевозки единицы груза  между отдельными пунктами сети проставлена у соответствующих ребер. Необходимо определить оптимальный маршрут доставки груза из пункта 1 в пункт 10, который обеспечил бы минимальные транспортные  расходы.

Вариант 1.

 

Вариант 2.

Вариант 3. 




Вариант 4.

 

Вариант 5.

 

Вариант 6.

 

Вариант 7.

 

Вариант 8.



Вариант 9.



Вариант 10.

 

Вариант 11.

 

Вариант 12.



Вариант 13.

 

Вариант 14.



Вариант 15.

 

Вариант 16.

 

Вариант 17.

 

Вариант 18.



Вариант 19.

Вариант 20.



ПРИМЕР ВЫПОЛНЕНИЯ ЗАДАЧИ 1

Задача 1.1. Планируется деятельность двух предприятий в течение 4 лет. Начальные средства составляют s0 = 700. Средства х, вложенные в предприятие 1, приносят к концу года доход f1(x)=0,7х и возвращаются в размере 1(х)=0,4х; аналогично, средства х, вложенные в предприятие 2, дают доход f2(x)=0,8х и возвращаются в размере 2(х)=0,5х. По истечении года все оставшиеся средства заново перераспределяются между предприятиями 1 и 2, новых средств не поступает и доход в производство не вкладывается.

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

Решение. Уравнение состояний sk = 1(xk) + 2(sk-1xk) примет вид: sk = 0.4xk+0.5(sk-1-xk) или sk = 0.5sk-1-0.1xk.

Целевая функция k-го шага: 0.7xk+0.8(sk-1-xk)=-0.1xk+0.8sk-1.

Целевая функция задачи:

Функциональные уравнения (уравнения Беллмана):



Далее проводим условную оптимизацию.














4-й шаг. Используем уравнение (*). Обозначим через Z4 функцию, стоящую в скобках, Z4 = -0.1x4+0.8s3; функция Z4 – линейная убывающая, так как угловой коэффициент -0,1 меньше нуля. Поэтому максимум достигается на конце интервала [0, s3] (см. рисунок).

Следовательно, Z4* = 0.8s3 при X4* =0.

3-й шаг. Уравнение



Находим s3 из уравнений состояний: s3 = 0.5s2-0.1x3 и, подставив его выражение в правую часть уравнения, получаем:



Как и в предыдущем случае, максимум достигается при  x3 = 0; т. е. Z3*=1.2s2 при X3*=0.

2-й шаг. Из уравнения состояний: s2 = 0.5s1-0.1x2, поэтому первое функциональное уравнение при k=2 примет вид:



Линейная относительно x2 функция Z2* = 1.4s1-0.22x2 убывает на отрезке [0, s1], и поэтому ее максимум достигается при х2 = 0.

При этом: Z2* = 1.4s1, при X2* = 0.

1-й шаг. s1 = 0.5 s0-0.1x1. Первое функциональное уравнение при k=1 имеет вид:



Как и в предыдущем случае, максимум достигается в начале отрезка, т. е.: Z1*=1.5s0 при X1*=0.

На этом условная оптимизация заканчивается. Используя ее результат и исходные данные, получаем:

Zmax = Z1*(700), Zmax =1050.

Далее:

X1* = 0, Y1* = s0 = 700

(все средства выделяются второй отрасли) 

s1* = 0.5700-0.10 = 350 X2* = 0, Y2* = s1 = 350

(все средства выделяются второй отрасли) 

s2* = 0.5350-0.10 = 175 X3* =0 , Y3* = 175

(все средства выделяются второй отрасли) 

s3* = 0.56400-0.10 = 87,5 X4* = 0, Y4* = 87,5

(все средства выделяются второй отрасли).

Оптимальная прибыль за 4 года, полученная от двух отраслей производства при начальных средствах 700 ед., равна 1050 ед. при  условии, что первая отрасль получает по годам (0; 0; 0; 0), а вторая отрасль соответственно (700; 350; 175; 87,5).

Задача 1.2. Распределите оптимальным образом денежные средства величиной 5 млн. р. между 4 предприятиями. В результате выделения средств k-му предприятию в размере u оно дает доход Jk(u).

Таблица 52

u

(млн. р.)

0

1

2

3

4

5

J1(u)

0

1.5

2

3.5

5.5

9

J2(u)

0

3

4.5

5.5

6.5

7.5

J3(u)

0

4

5

5.5

6

9

J4(u)

0

2

3

4

6.5

8

Решение. Для упрощения расчетов предполагаем, что распределение средств осуществляется в целых числах ui = {0, 1, 2, 3, 4, 5} млн. р.

1 этап. Условная оптимизация.

1-й шаг: k = 4. Предположим, что все средства в количестве u3 = 5 млн. р. отданы четвертому предприятию. В этом случае максимальный доход, как это видно из табл. 53, составит J4(U4)=8 тыс. р., следовательно, F4(c4)=J4(U4).

Таблица 53

с4

u4

0

1

2

3

4

5

0

0

-

-

-

-

-

1

-

2

-

-

-

-

2

-

-

3

-

-

-

3

-

-

-

4

-

-

4

-

-

-

-

6,5

-

5

-

-

-

-

-

8

F4(c4)

0

2

3

4

6.5

8

u*4

0

1

2

3

4

5

 

2-й шаг: k = 3. Определяем оптимальную стратегию при распределении денежных средств между четвертым и третьим предприятиями. При этом соотношение Беллмана имеет вид



на основе которого составлена табл.54.

Таблица 54

c3

u3

0

1

2

3

4

5

0

0

2

3

4

6,5

8

1

-

4

6

7

8

10,5

2

-

-

5

7

8

9

3

-

-

-

5,5

7,5

8,5

4

-

-

-

-

6

8

5

-

-

-

-

-

9

F3(c3)

0

4

6

7

8

10,5

u*3

0

1

1

1, 2

1, 2

1

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



на основе которого составлена табл. 55.

Таблица 55

c2

u2

0

1

2

3

4

5

0

0

4

6

7

8

10.5

1

-

3

7

9

10

11

2

-

-

4.5

8.5

10.5

12.5

3

-

-

-

5.5

9.5

11.5

4

-

-

-

-

6.5

10.5

5

-

-

-

-

-

7.5

F2(c2)

0

4

7

9

10.5

12.5

u*2

0

0

1

1

2

2

 

4-й шаг: k = 1. Определяем оптимальную стратегию при распределении денежных средств между первым и тремя  другими предприятиями, используя следующую формулу для расчета суммарного дохода:



на основе которого составлена табл. 56.

Таблица 56

c1

u1

0

1

2

3

4

5

0

0

4

7

9

10.5

12.5

1

-

1.5

5.5

8.5

10.5

12

2

-

-

2

6

9

11

3

-

-

-

3.5

7.5

10.5

4

-

-

-

-

5.5

9.5

5

-

-

-

-

-

9

F1(c1)

0

4

7

9

10.5

12.5

u*1

0

0

0

0

0, 1

0

2 этап. Безусловная оптимизация.

Определяем компоненты оптимальной стратегии.

1-й шаг. По данным табл. 56 максимальный доход при распределении 5 млн. р. между четырьмя предприятиями составляет: с1 = 5, F1(5) = 12,5. При этом первому предприятию нужно выделить u1* = 0 млн. р.

2-й шаг. Определяем величину оставшихся денежных средств, приходящуюся на долю второго и третьего предприятий.

с2 = с1u1* = 5 – 0 = 5 млн. р.

По данным табл. 55 находим, что оптимальный вариант распределения денежных средств размером 5 млн. руб. между третьим и четвертым предприятиями составляет: F2(5)=12,5 при выделении второму предприятию u2* = 2 млн. р.

3-й шаг. Определяем величину средств, приходящуюся на долю третьего и четвертого предприятий:

с3 = с2u2* = 5 – 2 = 3 млн. р.

По данным табл. 55 находим:

F3(3)  = 7 и u3* = 2 млн. р., либо возможен второй вариант F3(3)  = 7 и u3* = 1 млн. р.

4-й шаг. Определяем величину средств, приходящуюся на долю четвертого и пятого предприятий. Рассмотрим последовательно два возможных варианта.

Вариант 1: с4 = с3u3* = 3 – 2 = 1 млн. р., F4(1)  = 2 и u4* = 1 млн. р.

Вариант 2: с4 = с3u3* = 3 – 1 = 2 млн. р., F4(2)  = 3 и u4* = 2 млн. р.

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

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

F1(5) = J1(0) + J2(2) + J3(2) + J4(1) = 0+4.5+5+2=11.5  млн. р.,

F2(5) = J1(0) + J2(2) + J3(1) + J4(2) = 0+4.5+4+3=11.5  млн. р.

ПРИМЕР ВЫПОЛНЕНИЯ ЗАДАЧИ 2













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

Решение.1 этап. Условная оптимизация.

1-й шаг. k=1.

F1(i)=Ci10

На первом шаге в пункт 10 груз может быть доставлен из пунктов 7, 8 или 9.

Таблица 57

j

i

10

F1(i)

j*

7

7

7

10

8

8

8

10

9

10

10

10

 

2-й шаг. k=2.

Функциональное уравнение на втором шаге принимает вид



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

Таблица 58

j

i

7

8

9

F2(i)

j*

5

14+7

6+8

-

14

8

6

-

12+8

9+10

19

9

 

3-й шаг. k=3.



     Таблица 59

j

i

5

6

F3(i)

j*

2

12+14

-

26

5

3

-

6+19

25

6

4

-

11+19

30

6

 

4-й шаг. k=4.



Таблица 60

j

i

2

3

4

F3(i)

j*

1

11+26

10+25

3+30

33

4

 

2 этап. Безусловная оптимизация.













На этапе условной оптимизации получено, что минимальные затраты на перевозку груза из пункта 1 в пункт 10 составляют F4(1)=33. Данный результат достигается при движении груза из 1-го пункта в 4-й. По данным таблицы четвертого шага необходимо двигаться в пункт 6, затем – в пункт 9 (см. таблицу второго шага) и из него – в конечный пункт (см. таблицу первого шага). Таким образом, оптимальный маршрут доставки груза: 1 4  6  9  10. На графе жирными стрелками показан оптимальный путь.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1.      Васильков Ю.В. Компьютерные технологии вычислений в математическом моделировании/ Ю.В. Васильков, Н.Н. Василькова – М.: Финансы и статистика, 2002.

2.      Геминтерн В. И., Каган Б. М. Методы оптимального проектирования. – М.: Энергия, 1980.

3.      Данко П.Е., Попов А.Г., Кожевникова Т.Я. Высшая математика в упражнениях и задачах: Ч. 1. – М.: Высш. шк., 1999.

4.      Сборник задач по математике для втузов. Методы оптимизации/ Под ред.            А.В. Ефимова – М.: Наука, 1990.

5.      Зайцев М.Г., Зайцева Н.В. Методические материалы по курсу «Высшая математика» для факультетов менеджмента и экономики. – М.: Международный Университет Бизнеса и Управления «Братья Карич», 1997.

6.      Замков О.О. Математические методы в экономике/ О.О. Замков,                 Ю.А. Черемных, А.В. Толстопятенко– М.: Дело и Сервис, 1999.

7.      Запорожец Г.И. Руководство к решению задач по математическому анализу. – М.: Высш. шк., 1966.

8.      Интрилигатор М. Математические методы оптимизации и экономическая теория. – М.: Прогресс, 1975.

9.      Калихман И.Л., Войтенко М.А. Динамическое программирование в примерах и задачах. – М.: Высш. шк., 1979.

10.    Колесников А.Н. Краткий курс математики для экономистов: Учеб. пособие. – М.: ИНФРА-М, 1998.

11.    Красс М.С. Математика для экономических специальностей. – М.: ИНФРА-М, 1999.

12.    Ланкастер К. Математическая экономика. – М.: Советское радио, 1972.

13.    Малыхин В.И. Математика в экономике: Учеб. пособие. – М.: ИНФРА-М, 2001.

14.    Реклетис Г. Оптимизация в технике/ Г. Реклетис, А. Рейвиндран, К. Рэгсдел– М.: Мир, 1986.

15.    Шуп Т. Решение инженерных задач на ЭВМ. – М.: Мир, 1982.
1   ...   4   5   6   7   8   9   10   11   12


Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации