Краткий курс лекций Саратов 2012 министерство сельского хозяйства






НазваниеКраткий курс лекций Саратов 2012 министерство сельского хозяйства
страница4/7
Дата публикации21.01.2015
Размер1.23 Mb.
ТипУчебное пособие
e.120-bal.ru > Документы > Учебное пособие
1   2   3   4   5   6   7

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

В результате получили следующую ЗЛП, приведенную к допустимому виду




.
Эту задачу называют М-задачей.

Сформулируем утверждения, устанавливающие связь между решениями исходной задачи и М-задачи.

  1. Если в оптимальном решении М-задачи все искусственные переменные равны 0, то соответствующие значения остальных переменных дают оптимальное решение исходной задачи (т.е. , если ).

  2. Если имеется оптимальное решение М-задачи, в котором хотя бы одна из искусственных переменных отлична от 0, то исходная задача не имеет допустимого решения.

  3. Если М-задача не имеет оптимального решения, то исходная задача неразрешима (т.е. если , то либо , либо нет ни одного допустимого решения).

Из этих утверждений следует следующее правило решения M-задачи симплекс-методом:

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

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

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

Составим симплекс-таблицы решаемой задачи.


Базисные неизвест

ные

Свободные

члены






























6

1

3

–1

0

0

1

0

0



9

3

1

0

–1

0

0

1

0



8

1

8


0

0

–1

0

0

1

G



















0

0

0



3




0

–1

0




1

0






8



0

0

–1




0

1






1




1

0

0




0

0




G







0










0

0









0

0

–1






1












1

0

0







0












0

1

0







0







G




0

0










0












0

0







1







–1






1

0







0







0






0

1







0







0

G

39

0

0

–5

–1

0











ЛЕКЦИЯ 6
Динамическое программирование. Принцип оптимальности и функциональности. Функциональное уравнение Беллмана
Теории управления – развивающаяся область современной математики. Ей посвящена обширная литература , в которой исследуются различные типы управленческих систем. Рассмотрим классический метод оптимизации процесса управления, разработанный Р. Беллманом.

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

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

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

Динамическое программирование (ДП) – раздел математического программирования, в котором процесс принятия решений и управления является многошаговым.

Схема процесса принятия решений методом ДП представлена на рис. 5


Рис. 5

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

Состояние системы S в конце k-го шага зависит лишь от предшествующего состояния и управления и не зависит от остальных предшествующих состояний и управлений. Такое требование называется в теории управления Беллмана условием отсутствия последействия, согласно которому уравнения состояний имеют вид:
, . (37)
Обозначим показатель эффективности (оптимальности) k-го шага через
, .
Тогда согласно еще одному требованию в теории управления Беллмана, называемому условием аддитивности, целевая функция имеет вид
(38)
Таким образом, задача ДП (ЗДП) формулируется так: найти такое управление , переводящее систему S из состояния в состояние , при котором целевая функция (38) принимает экстремальное значение.

Сформулируем принцип оптимальности Беллмана:

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

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

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

Рассмотрим решение конкретных ЗДП.
Пример 1. Задача оптимального распределения оборудования.

Производственное объединение распределяет средства в четыре дочерние фирмы на покупку пяти производственных линий. Эксплуатация производственной линии в дочерней фирме под номером в зависимости от количества выделенных этой дочерней фирме линий приносят прибыль . Функции заданы таблицей 3.
Таблица 3


















1

12

14

16

14

2

17

16

18

15

3

20

18

21

18

4

22

20

24

20

5

26

24

26

24


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

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

– количество производственных линий, выделяемых дочерней фирме под номером ;

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

– начальное состояние системы, т. е. наличие производственных линий до начала их распределения по фирмам;

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

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

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

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

ЭММ задачи примет вид

при условиях

Отметим, что заданные функции , заменяют показатели эффективности k-го шага , содержащиеся в функциональных уравнениях Беллмана (39) и (40), т. е.
.
Результаты анализа возможных размещений производственных линий сведены в таблицу 4.

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

В столбец 1 внесены возможные распределения линий в конце -го шага, изменяющиеся от 0 до 5.

В столбец 2 внесены возможные управления на k-ом шаге для заданного количества производственных линий .

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

Анализ состояния системы начнем с последнего (четвертого) шага. Запишем функциональное уравнение Беллмана (39):
.
Из уравнения состояния (все производственные линии распределены) находим и потому
.
Переходим к третьему шагу. Запишем функциональное уравнение Беллмана (40):
.
Пусть , тогда возможны два варианта:

  1. ,

,

  1. ,

.

Наибольшее значение из двух полученных (14 и 16) равно 16. Следовательно, условный максимум целевой функции – (строка 2 столбца 5), который достигается при условно оптимальном количестве производственных линий, вложенных в третью фирму, равном 1, т. е. (строка 2 столбца 6).

Аналогично проводятся расчеты для случаев , , и (строки 3, 4, 5 и 6 столбцов 4, 5 и 6).

Второй шаг. Запишем функциональное уравнение Беллмана (14.4):
.
Пусть , тогда возможны два варианта:

  1. ,

,


  1. ,

.

Условный максимум целевой функции – при .

Пусть , тогда возможны три варианта:

  1. ,

,

  1. ,

,

  1. ,

.

Условный максимум целевой функции – при .

Аналогично проводятся расчеты для случаев , и .

Первый шаг. Запишем функциональное уравнение Беллмана (14.4):

.

Приведем расчеты аналогично предыдущему и заполним таблицу 14.2.

В результате получим следующие выводы:

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

ден. ед.
при оптимальном внедрении двух производственных линий .

б) Оптимальное количество линий, оставшихся в конце первого шага,



В столбце 9 таблицы 14.2 находим (строка 4). Оставшиеся три дочерние фирмы принесут прибыль 44 ден. ед. при вложении во вторую фирму одной линии .

в) Оптимальное количество линий, оставшихся в конце второго шага,



В столбце 6 таблицы 14.2 находим (строка 3). Оставшиеся две дочерние фирмы принесут прибыль 32 ден. ед. при вложении в третью фирму одной линии . Оставшаяся одна линия вкладывается в четвертую фирму, которая принесет прибыль 14 ден. ед.

Ответ: оптимальное решение задачи при ден. ед.


Таблица 4

Номер строки




















































1

2

3

4

5

6

7

8

9

10

11

12

1

0

0

0

0

0

0

0

0

0

0

0

0

2

1

0

1

1

0

0+14=14

16+0=16

16

1

0+16=16

14+0=14

16

0

0+16=16

12+0=12

16

0

3

2

0

1

2

2

1

0

0+15=15

16+14=30

18+0=18

30

1

0+30=30

14+16=30

16+0=16

30

1

0+30=30

12+16=28

17+0=17

30

0

4

3

0

1

2

3

3

2

1

0

0+18=18

16+15=31

18+14=32

21+0=21

32

2

0+32=32

14+30=44

16+16=32

18+0=18

44

1

0+44=44

12+30=42

17+16=33

20+0=20

44

0

5

4

0

1

2

3

4

4

3

2

1

0

0+20=20

16+18=34

18+15=33

21+14=35

24+0=24

35

3

0+35=35

14+32=46

16+30=46

18+16=34

20+0=20

46

1

0+46=46

12+44=58

17+30=47

20+16=36

22+0=22

58

1

6

5

0

1

2

3

4

5

5

4

3

2

1

0

0+24=24

16+20=36

18+18=36

21+15=36

24+14=38

26+0=26

38

4

0+38=38

14+35=49

16+32=48

18+30=48

20+16=36

24+0=24

49

1

0+49=49

12+46=58

17+44=61

20+30=50

22+16=38

26+0=26

61

2



ЛЕКЦИЯ 7
Модели потребительского выбора. Функция полезности. Линии безразличия. Оптимизация функции полезности. Функции спроса и предложения.
Пусть потребитель, располагая некоторой суммой средств, полностью тратит ее на приобретение товаров. Набор товаров покупает исходя из имеющейся суммы средств и собственных предпочтений. Математическая модель поведения такого потребителя называется моделью потребительского выбора.
Функция полезности
Рассмотрим потребительский набор из двух товаров (), где x и y количество единиц первого и второго товаров соответственно. Потребительский набор – это точка в прямоугольной системе координат xOy с координатами ().

Отношение потребителя к различным наборам товаров называют выбором потребителя.

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

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

при имеем ;

при имеем .

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

– предельная полезность первого продукта;

– предельная полезность второго продукта.

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

3.  Вторая частная производная от предельной полезности продукта по другой переменной должна быть положительной, т.е. предельная полезность увеличивается с ростом другой переменной (другого продукта). Таким образом,
.
Если функция полезности в задаче потребительского выбора не обладает свойствами 2 и 3, она тем не менее может описывать реальное поведение потребителя.
Линии безразличия
Линии уровня функции полезности потребителя называются линиями безразличия.

Линии безразличия являются функциями одной переменной. Данная функция имеет вид:
,
где .

Множество линий безразличия называется картой линий безразличия (рис. 5).

На рис. 5 изображены линии безразличия, имеющие уровни полезности потребителя , и . Линии безразличия не касаются и не пересекаются. При увеличении уровня функции полезности линии безразличия смещаются вправо вверх. Для примера рис. 11.1 справедливо неравенство .

Рис. 5 Линии безразличия
Из приведенных выше свойств функции полезности следует, линия безразличия в системе координат хОу является убывающей и выпуклой вниз (вогнутой) функцией.

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

Так как числитель и знаменатель дроби – величины положительные (свойство 1), то производная функции безразличия является отрицательной, т.е. данная функция является убывающей.

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

Если перейти от бесконечно малых приращений dx и dy к конечным приращениям и , то можно записать следующее приближенное равенство:
.
Сопоставив данное выражение с (41), найдем
. (42)
Дробь называется нормой замены первого продукта вторым. Норма замены показывает, насколько изменится потребление второго продукта при изменении потребления первого продукта на единицу. Если известна функция полезности то норма замены рассчитывается по формуле (42).

Пример. Пусть в течение месяца потребляется 45 единиц продукта х и 36 единиц продукта у. Функция полезности потребителя задана соотношением

.

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

Решение. Норму замены первого продукта вторым находят из соотношения (42):


При уменьшении потребления продукта х на 10 единиц потребление продукта у возрастет на 12,5 единиц. Действительно,

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

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

Бюджетным ограничением называется денежная сумма (доход), предназначенная на покупку данного набора товаров.

Если товаров два, то бюджетное ограничение I и цены на первый и второй товары связаны соотношением
. (43)
Задачу математического выбора можно записать в виде ЗМП:

при условиях
(44)
При решении задачи математического выбора (44) обычно бюджетное ограничение заменяют на равенство . Это связано с тем, что значение функции полезности увеличивается при увеличении x и y. Максимум лежит на крайних правых и нижних точках. Следовательно, задачу математического программирования можно заменить задачей на условный экстремум: при условиях
(45)
где - целевая функция; – функция связи.

Функция Лагранжа для этой задачи имеет вид:
.
Составляем систему линейных уравнений, для чего приравниваем к нулю первые частные производные функции Лагранжа:
;

;

.
Умножим первое уравнение на , а второе – на и вычтем второе уравнение из первого:
.
Таким образом, систему уравнений для укороченной подозрительной точки функции Лагранжа можно переписать в виде:
; (46)

. (47)
Сопоставив (46) с (42), получим ,
т.е. норма замены первого продукта вторым равна отношению цены первого продукта к цене второго.

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

Градиент функции в точке направлен вправо вверх. Действительно,
, .
Поэтому
,
а и положительны по условию задачи.

Точно так же направлен градиент функции в точке .

Рис. 6

ЛЕКЦИЯ 8
Элементы теории игр в задачах оптимального управления экономическими процессами.
1   2   3   4   5   6   7

Похожие:

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconРоссийской Федерации Федеральное государственное бюджетное образовательное...
Учет и анализ: Краткий курс лекций для студентов направления подготовки 080200. 62 Менеджмент / Сост.: Кудряшова Е. В., Павленко...

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconИнформация подготовлена по материалам, полученным из сети «Интернет»11. 03. 2012
России по реализации федеральной целевой программы «Социальное развитие села до 2013 года». Как сообщили 6 марта корреспонденту в...

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconСписок новых книг, поступивших в библиотеку в ноябре 2012 года
Агафонов В. В. Криминалистика: краткий курс лекций – М.: Юрайт, 2013. – 184с. 10 экз

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconПоложение о Министерстве сельского хозяйства и продовольствия Республики...
Министерство сельского хозяйства и продовольствия Республики Татарстан (далее Министерство) является исполнительным органом государственной...

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconПрограмма импортозамещения продукции в пензенской области на 2015-2017 годы
Министерство сельского хозяйства Пензенской области, Министерство строительства и жилищно-коммунального хозяйства Пензенской области,...

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconКраткий курс лекций Производственная безопасность. Часть 3
Пламя возникает в результате сложного взаимодействия химических и физических процессов

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconКраткий курс лекций по экономике апк
Федеральное государственное образовательное учреждение высшего профессионального образования Ставропольский государственный аграрный...

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconД. А. Медведев [и др.] // Экономика сельского хозяйства России. 2012. № С. 7-13
Агропромышленный комплекс требует повышенного внимания [Текст] / Д. А. Медведев [и др.] // Экономика сельского хозяйства России....

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconКраткий курс лекций по дисциплине
Учебное пособие предназначено для студентов Стгау всех направлений, изучающих курс «История, традиции и обычаи народов Северного...

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconКраткий курс лекций по статистике автор: ильина г. Г.,к э. н
Статистика-наука,которая изучает приемы и методы сбора и обработки информации о каких –либо явлениях и процессах, происходящих в...






При копировании материала укажите ссылку © 2016
контакты
e.120-bal.ru
..На главную