Автор: Пользователь скрыл имя, 13 Марта 2012 в 18:00, контрольная работа
Теория познания (гносеология, эпистемология;), являясь одним из фундаментальных методологических разделов философии, изучает возможности и закономерности познания от ощущений, представлений, понятий к объективной реальности, к объективной данности, к действительности; всесторонне исследует этапы, ступени и формы познавательного процесса, условия и критерии, достигая установления его достоверности и истинности.
1.Экономический анализ и теория познания.
2. Экономический анализ и основные принципы диалектики.
3. Экономическая теория и экономический анализ.
4. Системность методологического подхода к анализу.
Задание 2.
Доказать возможности применения методов линейного программирования и методов динамического программирования в решении конкретных аналитических задач.
1.Линейное программирование.
2.Динамическое программирование.
Список используемой литературы.
При больших m и n эта задача решается на ЭВМ. Для этого нужно ввести в машину исходные данные, помещенные в таблице 1 и воспользоваться разработанной программой. При небольших m и n задача может быть решена вручную с использованием общих методов решения. Для значений m и n до 5-6 задачу часто удается решить путем прикидочных расчетов, перебором вариантов и логических размышлений.
Задача. Для обеспечения ГСМ четырех танковых соединений имеется три склада. Известны запасы ГСМ и потребности в нем соединений. Определение стоимости доставки одной тонны ГСМ из каждого склада в любое соединение.
Все исходные данные записаны в таблице 2.
Сформулировать задачу линейного программирования для данных условий и определить такой план снабжения ГСМ соединений, при котором суммарный расход на его провозку будет минимальным.
Решение: Обозначим через xij(i=1,2,3; j=1,2,3,4) количество ГСМ, планируемых для доставки с i-того склада (i=1,2,3) j-тому соединению (j=1,2,3,4).
Таблица 2.
|Склады | Соединения
| |
| | 1 | 2 | 3 | 4 | |
| 1 |x11=350 |x12=0 |x13=50 |x14=500 | 900 |
| |3* |4 | |3* | |
| 2 |x21=0 |x22=200 |x23=0 |x24=0 | 300 |
| |5 |4 |7 |8 | |
| 3 |x31=0 |x32=250 |x33=350 |x34=0 | 60 |
| |4 |3* |5* |4 | |
|Потребнос| 350 | 450 | 400 | 500 | |
|ть в ГСМ | | | | | |
Выбор планов зависит от запасов ГСМ на складах и потребностей в нем
соединений, что математически определяется выражениями:
[pic] (21)
[pic] (31)
Суммарные расходы на перевозку ГСМ определяются линейными
выражениями:
[pic] (41)
Требуется определить такие значения xij (выбрать такой план) удовлетворяющий выражениям (21) и (31), которые критерий эффективности
обращают в минимум. Так формулируется задача линейного программирования для
данных условий.
Эта задача решается элементарными подсчетами и рассуждениями.
Отметим в столбцах звездочками минимальные значения стоимости перевозки одной тонны ГСМ. В каждое соединение нужно планировать доставку из того склада, для которого эта стоимость будет наименьшей или близкой к ней, но с учетом расходов на доставку ГСМ и в другие соединения. Очевидно, в 1-е и 4-е соединение целесообразно завозить ГСМ полностью из 1-го склада, поэтому целесообразно выбрать x11=350, x14=500. Во второе соединение выгодно доставить горючее целиком с 3-го склада. Но тогда будут большие расходы при доставке ГСМ в 3-е соединение из 2-го склада. Поэтому тцелесообразно выбрать x13=50, x33=350, т.е. завести горючее в 3-е соединение с 1-го и 3-го складов, а 200 т. для 2-го соединения завести из склада, x22=200, x32=250. Результаты расчетов занесены в таблице 2, по которой удобно проверить выполнение условий (21), (31), найдя суммы xij по строкам и столбцам.
При таком плане расходы будут минимальными:
[pic]
Для сравнения, какую можно иметь экономию в средствах, выбрав оптимальный план, рассмотрим один из возможных планов:
x11=350, x12=450, x13=x14=0, x21=x22=x23=0,
x24=300, x31=x32=0, x33=400, x34=200
При этом плане стоимость перевозок будет равна:
[pic]
Она больше на 1950 единиц Kmin, что составляет более чем 30%.
Полученное оптимальное решение является основой для применения
объективного решения на снабжение ГСМ соединений с учетом конкретной
обстановки.
2.ЗАДАЧИ ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ СРЕДСТВ ПОРАЖЕНИЯ.
Задачи оптимального распределения средств поражения в общем виде
формулируются так: имеется некоторое количество средств поражения и целей.
Требуется так распределить средства поражения по целям, чтобы общий эффект
применения был в определенном смысле оптимален.
Поражение противника является одним из важных элементов боевых
действий. Поэтому решение задач на поражение является важным этапом при
планировании и управлении боевыми действиями.
Различают два основных типа задач целераспределения:
- для средств поражения, находящихся в обороне;
- для средств поражения нападения;
Распределение средств поражения обороны осуществляется в ходе
боевых действий, выявляемые цели и возникающие условия заранее неизвестны и
во многом определяются противником. Расчеты нужно производить очень быстро,
что возможно при наличии современных вычислительных средств.
Распределение средств нападения по выявленным целям может быть
спланировано заранее на основе расчетов. Однако резкой границы между этими
вариантами нет потому, что в обоих случаях выявляются новые цели,
изменяются условия и потребуется производить перерасчеты.
Задача распределения средств поражения при ведении боевых действий
в полной мере очень сложна и требует учета большого числа факторов.
Некоторые же частные задачи успешно решаются с помощью линейного
программирования.
Рассмотрим первую из таких задач. Имеется m различных средств
поражения и n целей. Принимаются следующие допущения:
- число средств поражения не превосходит числа целей m(n;
- цели имеют разную важность, определяемую коэффициентом важности
kj (j=1,2,…,n);
- за каждой целью не может быть закреплено более одного средства
поражения, то есть должно быть обстреляно максимальное число
целей;
- известны вероятности pij поражения i-ым средством j-ой цели,
которые составляют таблицу вероятностей поражения [pic]:
[pic] (5)
Таблица вероятности поражения вычисляется по соответствующим
формулам теории стрельбы.
Закрепление или не закрепление i-того средства поражения за j-той
целью выражается величиной xij, принимающей значение 1, когда имеется
закрепление, и 0, когда его нет.
План распределения средств по целям будет определяться таблицей
(таблицей 1). За критерий эффективности в общем случае выберем взвешенное
математическое описание числа уничтоженных целей, которое определяется
выражением
[pic] (6)
где kj (j=1,2,…,m) – коэффициенты, определяющие важность целей.
Если цели имеют одинаковую важность, то k1=k2=…=km=1. При этих значениях
выражение (6) является математическим ожиданием числа уничтоженных целей.
Требование, чтобы каждое средство было закреплено за какой либо целью,
определяется выражениями
[pic] (i=1,2,…,m) (7)
Условия, что за каждой целью закрепляется не более одного средства
поражения, определяются выражением
[pic] (j=1,2,…,n)
В случае знака равенства во всех выражениях (8) имеет место m=n, в
противном случае m
Динамическое программирование представляет собой математический аппарат, разработанный для эффективного решения некоторого класса задач математического программирования. Этот класс характеризуется возможностью естественного (а иногда и искусственного) разбиения всей операции на ряд взаимосвязанных этапов. Термин "динамическое" в названии метода возник, видимо, потому что этапы предполагаются разделенными во времени. Однако этапами могут быть элементы операции, никак не связанные друг с другом показателем времени. Тем не менее, метод решения подобных многоэтапных задач применяется один и тот же, и его название стало общепринятым, хотя в некоторых источниках его называют многоэтапным программированием.
Модели динамического программирования могут применяться, например, при разработке правил управления запасами, устанавливающими момент пополнения запасов и размер пополняющего заказа; при разработке принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию; при распределении дефицитных капиталовложений между возможными новыми направлениями их использования; при составлении календарных планов текущего и капитального ремонта сложного оборудования и его замены; при разработке долгосрочных правил замены выбывающих из эксплуатации основных фондов и т. д.
Для определения сущности динамического программирования рассмотрим задачу:
Представим себе некоторую операцию О, состоящую из ряда последовательных "шагов" или этапов, например, деятельность отрасли промышленности в течение ряда хозяйственных лет. Пусть число шагов равно m. Выигрыш (эффективность операции) Z за всю операцию складывается из выигрышей на отдельных шагах:
где zi- выигрыш на i-м шаге.
Если Z обладает таким свойством, то его называют аддитивным критерием.
Операция О является управляемым процессом, то есть мы можем выбирать какие-то параметры, которые влияют на его ход и исход, причем на каждом шаге выбирается решение, от которого зависит выигрыш и на данном шаге, и выигрыш за операцию в целом. Эти решения называются шаговыми.
Совокупность всех шаговых управлений является управлением операцией в целом. Обозначим его буквой х, а шаговые управления- буквами х1, х2, ... , хm: х=х(х1, х2, ... , хm). Требуется найти такое управление х, при котором выигрыш Z обращается в максимум:
То управление х*, при котором этот максимум достигается, называется оптимальным управлением. Оно состоит из совокупности оптимальных шаговых управлений: х*=х*(х1*, х2*, ... , хm*).
Максимальный выигрыш, который достигается при этом управлении, обозначим следующим образом:
,
где Х- множество допустимых (возможных) управлений.
Самый простой способ решения задачи- полный перебор всех вариантов. Когда количество вариантов невелико, этот способ вполне приемлем. Однако на практике задачи с небольшим числом вариантов встречаются весьма редко, поэтому полный перебор, как правило, неприемлем из-за чрезмерных затрат вычислительных ресурсов. Поэтому в таких случаях на помощь приходит динамическое программирование.
Динамическое программирование часто помогает решить задачу, переборный алгоритм для которой потребовал бы очень много времени. Этот метод использует идею пошаговой оптимизации. В этой идее есть принципиальная тонкость: каждый шаг оптимизируется не сам по себе, а с "оглядкой на будущее", на последствия принимаемого "шагового" решения. Оно должно обеспечить максимальный выигрыш не на данном конкретном шаге, а на всей совокупности шагов, входящих в операцию.
Метод динамического програмирования может применяться только для определенного класса задач. Эти задачи должны удовлетворять таким требованиям:
1. Задача оптимизации интерпретируется как n-шаговый процесс управления.
2. Целевая функция равна сумме целевых функций каждого шага.
3. Выбор управления на k-м шаге зависит только о состояния системы к этому шаге, не влияет на предшествующие шаги (нет обратной связи).
4. Состояние sk после k-го шага управления зависит только от предшествующего состояния sk-1и управления xk (отсутствие последействия).
5. На каждом шаге управление Xk зависит от конечного числа управляющих переменных, а состояние sk- от конечного числа параметров.
В основе решения всех задач динамического программирования лежит "принцип оптимальности" Беллмана, который выглядит следующим образом:
Каково бы ни было состояние системы S в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный.
Этот принцип впервые был сформулирован Р. Беллманом в 1953 г. Беллманом четко были сформулированы и условия, при которых принцип верен. Основное требование- процесс управления должен быть без обратной связи, т.е. управление на данном шаге не должно оказывать влияния на предшествующие шаги.
Принцип оптимальности утверждает, что для любого процесса без обратной связи оптимальное управление таково, что оно является оптимальным для любого подпроцесса по отношению к исходному состоянию этого подпроцесса. Поэтому решение на каждом шаге оказывается наилучшим с точки зрения управления в целом.
Динамическое программирование. (ДП)
Динамическими называются задачи экономики, организации и управления, в которых необходимо распределять ресурсы на каждом этапе какого – либо промежутка (времени). Формулировка задачи ДП:
Имеется некая система S, находящаяся в первоначальном состоянии S. Данная система имеет какие – либо параметры. При переходе системы из одной точки в другую необходимо в каждый момент времени выбирать направление дальнейшего движения из нескольких допустимых направлений при условии, что каждому направлению соответствует своя эффективность (параметры системы изменяются по разному), и необходимо таким образом спланировать маршрут из начальной точки в конечную, чтобы критерий эффективности достигал экстремального значения.
Иными словами из множества допустимых управлений U=(U1, U2, …, Un) необходимо найти оптимальное, при котором система переходит из своего начального состояния в конечное таким образом, что критерий оптимальности W достигает своего максимума.
Динамическое программирование представляет собой метод оптимизации многошаговых процессов по шагам. Локальный оптимум на каждом шаге должен рассчитываться не как оптимальный на данном этапе, а как дающий максимальное значение критерия оптимальности в конце движения. Несоблюдение этого правила приводит к серьезным ошибкам, поэтому при решении задач ДП двигаются обычно из конца пути в начало, рассчитывая затраты при движении в каждом направлении, а затем из начала в конец, находя локальный оптимум из рассчитанных затрат на каждом шаге. Таким образом получаем максимальное значение критерия оптимальности.
В основе расчетов методом динамического программирования лежит принцип Беллмана. Он звучит:оптимальное управление обладает тем свойством, что какавы бы ни были достигнутые состояния и решения до данного момента, последующее решение должно составлять оптимальное поведение относительно состояния, достигнутого на данный момент.
Решение задачи динамического программирования. Распределение ресурсов предприятиям.
Данные возьмем из задачи нелинейного программирования: количество составов и прибыль на 1 состав для каждого предприятия:
Предприятие 1.
Количество составов Прибыль на 1 состав
6,17 676,8
4,31 – 6,17 388,8
3,08 – 4,31 244,8
1,85 – 3,08 172,8
до 1,85 100,8
Предприятие 2.
Количество составов Прибыль на 1 состав
6,18 459,25
4,33 – 6,18 305,25
3,09 – 4,33 151,25
1,85 – 3,09 74,25
до 1,85 -78,75
Предприятие 3.
Количество составов
5,66 294,68
3,96 – 5,66 40,28
2,83 – 3,96 -214,12
1,7 – 2,83 -298,92
до 1,7 -458,52
Количество составов,выделенных всем трем предприятиям (N), равно 14.
Рассчитаем эффективность использования средств предприятиями. Для этого прибыль на один состав умножим на количество составов, при которых достигается эта прибыль на каждом из предприятий.
, где n – количество составов, Pn – прибыль при этом количестве составов.
Количество составов Предприятие 1 Предприятие 2 Предприятие 3
1 100,8 -78,15 -458,52
2 345,6 148,5 -597,94
3 518,4 222,75 -642,36
4 979,2 605 161,12
5 1944 1526,25 201.40
6 2332,8 1831,5 1768,08
Рассчитаем - максимально возможное количество составов для предприятий 1 и 2. составов. Теперь рассчитаем минимально возможное количество составов для предприятий 1 и 2, исходя из того, что максимально возможное количество составов для предприятия 3 равно = 6 составов, тогда составов. Составим таблицу выделения средств двум предприятиям (1 и 2). Здесь x - общее количество ресурсов (составов) для двух предприятий; x = x1 + x2; 0 x1 6 – допустимое количество составов для предприятия 1; 0 x2 6 – допустимое количество составов для предприятия 2. Отсюда видно, что 0 x, однако количество составов для предприятия 3 не может превышать 6, следовательно x, следовательно x; 8x12. q1, q2 – эффективность использования средств предприятиями 1 и 2 соответственно взятая из предыдущей таблицы. W2 = q1 + q2 – суммарная эффективность обоих предприятий.Наибольшую суммарную эффективность для каждого значения x будем подчеркивать.
x x1 X2 Эффективность
q1 q2 W2
8 2 6 345,6 1831,5 2177,1
3 5 518,4 1526,25 2044,65
4 4 979,2 605 1584,2
5 3 1944 222,75 2166,75
6 2 2332,8 148,5 2481,3
9 3 6 518,4 1831,5 2349,9
4 5 979,2 1526,25 2505,45
5 4 1944 605 2549
6 3 2332,8 222,75 2555,55
10 4 6 979,2 1831,5 2810,7
5 5 1944 1526,25 3470,25
6 4 2332,8 605 2937,8
11 5 6 1944 1831,5 3775,5
6 5 2332,8 1526,25 3859,05
12 6 6 2332,8 1831,5 4164,3
Теперь составим таблицу выделения средств всем трем предприятиям. Так как N – общее количество составов равно 14, а максимально возможное количество составов для предприятий 1 и 2 =12, то всем трем предприятиям может быть выделено 13 или 14 составов. W3 – суммарная эффективность всех трех предприятий.
Количество Составов x3 x Эффективность использования ресурсов
q3 W2 W3
13 1 12 -458,52 4164,3 3705,78
2 11 -597,94 3859,05 3261,11
3 10 -642,36 3470,25 2827,89
4 9 161,12 2555,55 2716,67
5 8 201,4 2481,3 2682,7
14 2 12 -597,94 4161,3 3563,36
3 11 -642,36 3859,05 3216,69
4 10 161,12 3470,25 3631,12
5 9 201,4 2555,55 2756,95
6 8 1768,08 2481,3 4249,38
W3 максимальное равно 4249,38, следовательно Z = 4249,38.
x3 = 6; x2 = 2; x3 = 6.
Вывод:
В результате решения задачи динамического программирования я получил, что максимальное значение целевой функции Z = = 4249,38 получается при количестве составов, выделенных 3 предприятиям N = 14, и количестве составов выделенных предприятию 3 x3 = 6. При этом количество составов для предприятий 1 и 2 равно 8. Максимальная эффективности использования 8 составов предприятиями 1 и 2 достигается при выделении предприятию 1 - 6 составов, а предприятию 2 – 2 состава, и она равна 2481,3. Следовательно x1 = 6, x2 = 2, x3 = 6, Z = 4249,38.