Куцый Н.Н. Математические методы системного анализа и теория принятия решений. Пособие по курсовой работе

Подождите немного. Документ загружается.

Если разработанный Вами про- граммный продукт может работать

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

ная курсовая работа не может быть оценена выше, чем "удовлетворительно".

Для более высокой оценки разработанный Вами программный продукт должен

обрабатывать числовые значения из заданного диапазона:

а) количество досок в каждой из трёх партий, может быть взято из диапа-

зона 25..250 досок;

б) комплект может состоять или из трёх деталей, или из четырёх деталей,

или из пяти деталей;

в) если комплект состоит из трёх деталей, то или комплект состоит из од-

ной детали длиной 2 м и двух деталей длиной в 1,25 м каждая, или двух дета-

лей длиной по 2 м каждая и одной детали длиной в 1,25 м;

г) если комплект состоит из четырёх деталей, то или комплект из одной

детали длиной 2 м и трёх деталей длиной в 1,25 м каждая, или комплект состо-

ит из двух деталей длиной в 1,25 м каждая, или комплект состоит из трёх дета-

лей длиной по 2 м каждая и одной детали длиной в 1,25 м;

д) если комплект состоит из пяти деталей, то или комплект состоит из од-

ной детали длиной 2 м и четырёх деталей длиной в 1,25 м каждая, или

комплект состоит из двух деталей длиной по 2 м каждая и трёх деталей длиной

в 1,25 м каждая, или комплект состоит из трёх деталей длиной по 2 м каждая и

двух деталей длиной в 1,25 м каждая, или комплект состоит из четырёх деталей

длиной по 2 м каждая и одной детали длиной в 1,25 м.

Вариант 9.1. Решить поставленную задачу методом симплекс-таблиц,

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

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

ных.

Вариант 9.2. Решить поставленную задачу методом симплекс-таблиц,

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

начального допустимого базисного решения метод Данцига.

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

ном на модифицированных жордановых исключениях.

Вариант 9.4. Решить поставленную задачу двойственным симплекс-мето-

дом.

Вариант 9.5. Решить поставленную задачу следующим образом. Вначале

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

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

симплекс-таблиц, основанном на методе полного исключения Гаусса. От полу-

ченного решения перейти к решению прямой задачи.

Вариант 9.6. Решить поставленную задачу, применяя метод Гомори.

ТЕМА 10. УПРАВЛЕНИЕ СИСТЕМОЙ МАРКОВСКОГО ТИПА С

ДОХОДАМИ

Имеется предприятие, выпус- кающее галстуки, которое планирует

свою работу на 12 месяцев вперед.

Предприятие может находиться в одном из двух состояний:

а) модель предыдущего месяца удачна;

б) модель предыдущего месяца неудачна.

Переходы за месяц из одного состояния в другое описываются матрицей

вероятностей

. С каждым переходом из состояния i в состояние j мат-

рица доходов R.

У дирекции предприятия имеется возможность применения одной из трёх

стратегий управления:

а) первая стратегия

)1(

заключается в отказе от проведения каких-либо

дополнительных исследований; при такой стратегии предприятие не несёт рас-

ходов на проведение этих дополнительных исследований, но и не влияет в сто-

рону улучшения для своей деятельности на элементы матрицы

, ве-

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

приходится функционировать предприятию;

б) при выборе второй стратегии

)2(

дирекция решает провести допол-

нительные исследования конъюнктуры спроса; тем самым несёт расходы на

проведение этих дополнительных исследований и может влиять в сторону

улучшения для своей деятельности на элементы матрицы

, выпуская

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

в) третья стратегия

)3(

предполагает проведение рекламной кампании,

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

тегии влияет в сторону улучшения для своей деятельности на элементы матри-

цы

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

Стратегия k = 1

j⇒



1 2

j⇒



1 2

1 0,5 0,5

1 7 3

2 0,3 0,7 2 5 1

Стратегия k = 2

j⇒



1 2

j⇒



1 2

P= 1 0,6 0,4

1 3 -5

2 0,7 0,3 2 1 -18

Стратегия k = 3

j⇒



1 2

j⇒



1 2

P= 1 0,7 0,3 R= 1 2 -8

2 0,8 0,2 2 0 -20

Если разработанный Вами программный продукт может работать только с

конкретными данными матрицы

, то выполненная курсовая работа не

может быть оценена выше, чем "удовлетворительно". Для более высокой оцен-

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

значения из заданного диапазона:

а) элементы матрицы вероятностей

могут принимать значения из

диапазона

≤≤

;

б) элементы матрицы доходов

могут принимать значения из диапазона

1030

≤≤−

Вариант 10.1. Применив рекуррентный метод динамического програм-

мирования найти оптимальную стратегию управления, обеспечивающую мак-

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

Вариант 10.2. Применив метод итераций по стратегиям Ховарда найти оп-

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

предприятия.

ТЕМА 12. ЗАДАЧА О ДОБЫЧЕ ПЕСКА В КАРЬЕРАХ И ЕГО ДО-

СТАВКЕ

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

строительных площадки. Данные о производительности карьеров за сутки (

тоннах), потребностях в песке строительных площадках (

в тоннах), затратах

на добычу песка (

руб/тонна) и транспортных расходах приведены в следую-

щей таблице

↓ b

→

40 35 30 45 d

46 4 3 2 5 2

34 1 1 6 4 3

40 3 5 9 4 1

Недостающее количество песка – 30 т за сутки можно обеспечить следую-

щими тремя путями:

1)увеличение производительности 1-го карьера, что повлечет за собой до-

полнительные затраты на добычу 1 т в 3 руб.

2)увеличение производительно- сти 2-го карьера в дополнительными

затратами в 2 руб. на добычу 1 т.

3)эксплуатация нового карьера с затратами на добычу 1 т – 5 руб., и на

транспортировку к указанным строительным площадкам -

., 2

рубc

. 1 и . 3

4342

рубсрубc

Определить план закрепления строительных площадок за карьерами и ва-

риант расширения поставок песка, при которых затраты на доставку песка и на

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

Вариант 12.1. Поставленную задачу решить методом потенциалов, исполь-

зовав для нахождения начального опорного плана метод минимального элемен-

та.

Вариант 12.2. Поставленную задачу решить методом потенциалов, ис-

пользовав для нахождения начального опорного плана метод "северо-западно-

го угла".

Вариант 12.3. Поставленную задачу решить венгерским методом.

ТЕМА 13. ЗАДАЧА О ПОПОЛНЕНИИ ЗАПАСОВ

Акционерное общество "Меркурий" имеет сорок автоцистерн для перевоз-

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

поэтому желательно иметь в своем распоряжении не слишком больший запас;

но при отсутствии шин в запасе акционерное общество терпит убытки из-за не-

возможности выполнить отдельные заказы на перевозки.

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

о ее состоянии. Он подметил, что шина, изношенная на 20% прошла 6000 км;

на 40% - 12 000 км; на 60 % - 18 000 км; на 80 % - 24 000 км и на 100 % - 30 000

км. Но, как бы там ни было, не все шины выдерживают 30 000 км.

Исследование, которое проводилось в течение многих лет, показало, что

согласно статистике, на 100 шин, введенных в эксплуатацию, 5 выходят из

строя после 6000 км, 10 – между 6000 и 12 000 км; 25 – между 12 000 и 18 000

км; 30 – между 18 000 и 24 000 км; 30 между 24 000 и 30 00 км. Таким образом,

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

число шин, находящихся еще в эксплуатации после пробега 6000, 12 000 и т.д.

километров.

Дирекция планирует ездки машин на неделю; важно заказывать шины в

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

повреждения. Допустим, что машина пробегает за неделю 2000 км; что за неде-

лю дает пробег в 80 000 км для всех машин и 800 000 км для всех шин.

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

поступления запасов?

Вариант 13.1. Решить поставленную задачу рекуррентным способом [10].

Вариант 13.2. Решить поставленную задачу, применяя расчет по матема-

тическим ожиданиям [10].

ТЕОРЕТИЧЕСКИЕ ПОЛО- ЖЕНИЯ

1.Сведение к задаче линейного программирования задачи темы 1.

Пример. Пусть три типа судов следует распределить между четырьмя регу-

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

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

линии и соответствующие эксплуатационные расходы.

N типа

судна ⇒

N линии

⇓

1 2 3

Мини-

мальный

объем

перевозок

300000

200000

100000

40000

50000

500000

Число судов 50 95 30

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

ния следующего содержания. Математическую модель составить для двух ва-

риантов: 1.поставлено требование, чтобы в перевозках участвовали все суда; 2.

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

разрешается сдавать в аренду.

Обозначим через

число судов j-го типа (j=1,2,3), которое планируется

закрепить за i-й (i-1,2,3,4) регулярной линией.

С учетом введенных обозначений математическая модель задачи для 1-го

варианта может быть представлена

найти

++++++=

221241312111

287040252015min(min xxxxxx

)654070404515

433323134232

xxxxxx

++++++

при ограничениях

;95

;50

;500451750

;100301020

;200502510

;300253015

43332313

42322212

41312111

434241

333231

232221

131211

=+++

≥++

xxxx

xxx

и при

).3,2,1;4,3,2,1( 0

==≥

jix

Последние три ограничения в виде равенств учитывают требования перво-

го варианта о задействовании в перевозке груза всех судов.

Математическая модель для 2-го варианта может быть представлена

;95

;50

;500451750

;100301020

;200502510

;300253015

43332313

42322212

41312111

434241

333231

232221

131211

≤+++

≥++

xxxx

xxx

и при

).3,2,1;4,3,2,1( 0

==≥

jix

Рекомендация. В большинстве учебных пособий симплекс-метод, метод

симплекс-таблиц изложен так, что переменные задачи линейного програм-

мирования имеют один индекс, т.е.

Поэтому имеет смысл ввести новые

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

первого варианта:

найти

++++++=

654321

287040252015min(min xxxxxx

)654070404515

121110987

xxxxxx

++++++

при ограничениях

;95

;50

;500451750

;100301020

;200502510

;300253015

12963

11852

10741

121110

987

654

321

=+++

≥++

xxxx

xxx

и при

).12)1(1( 0

=≥

Из сопоставления двух моделей для

видно, что

соответствует

,..., - ,

12211

xxx

соответствует

2.Сведение к задаче линейного программирования задачи темы 2

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

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

-го дня

)5)1(1(

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

шивается, при этом

;15

;25

;35

;45

.55

Часть (весь) изно-

шенного инструмента в конце

-го дня может сдаваться в обычный ремонт,

часть (весь) в срочный, а часть (весь) может не сдаваться в ремонт, оставаясь

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

Пусть обычный ремонт одного инструмента длится

дня и стоит

руб., а срочный ремонт одного инструмента длится

день и стоит

рублей. Кроме того, один новый инструмент стоит

рублей.

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

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

−

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

−+

)1( j

й день;

−

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

-го дня;

−

число инструментов, сдаваемых в срочный ремонт в конце

−

го дня;

−

число изношенных инструментов, оставшихся не сданными в ремонт

к концу

−

го дня.

Тогда число

инструментов, поступающих в употребление в начале

−

го дня, состоит:

из

−−

инструментов, сданных в обычный ремонт

дней назад и полу-

ченных из ремонта в конце

−−

)1( j

го дня;

из

−−

инструментов, сдан- ных в срочный ремонт

дней назад

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

−−

)1( j

го дня;

из

−

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

−

го дня, т.е.

111

−−+−−

++=

qjpjjj

zyxr

),5)1(1(

где

−

количество инструмента, купленного для использования в 1-й день;

,0 ...

===

−

0 ...

===

−

, так как до начала выполнения производствен-

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

первые

дней (в нашем случае 2 дня) еще не поступит из ремонта в упо-

требление ни одного инструмента, сданного даже в срочный ремонт, а в первые

дней (в нашем случае 3 дня) не поступит в употребление ни одного

инструмента, сданного в обычный ремонт.

В конце

−

го дня окажутся использованными

инструментов, бывших в

употреблении в этот день и

−

инструментов, оставшихся не сданными в ре-

монт к концу

−−

)1( j

го дня, т.е.

−

, из них

единиц поступает в обыч-

ный ремонт,

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

единиц инструмента

−

−++=

jjjjj

uuzyr

.0 );5)1(1(

При этом надо учесть, что инструмент, который возвратится из ремонта в

конце

−

го (в нашем случае 5-го дня) и позже, уже не понадобится. Поэтому

еще за

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

вать его в обычный ремонт, т.е.

,0 ...

====

+−−

npnpn

yyy

и за

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

вать его в срочный ремонт, т.е.

.0 ...

====

+−−

nqnqn

zzz

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

∑

−

инструментов и израсходовано на это

∑

−

рублей; будет сдано в

обычный ремонт

∑

−−

инструментов и израсходовано

∑

−−

рублей; будет

сдано в срочный ремонт

∑

−−

инструментов и израсходовано на это

∑

−−

z–

рублей.

Тем самым задача заключается в минимизации общей стоимости из-

держек

∑ ∑ ∑

−

−−

++=

jjj

zcybxaf

при ограничениях

,0 ,)1(1(

,0... ,0...

),,...,1(

111

===−++

======

==++

−

−−

−−−−−

unjruuzy

zzyy

njrzyx

jjjjj

jqjpjj

и условиях

).,...,1,( 0 ),,...,1,( 0

))1(1( ,0 ,0 ,0 ,0

nqnqnjznpnpnjy

njuzyx

jjjj

+−−==+−−==

=≥≥≥≥

3.Сведение к транспортной задаче задачи темы 2.

Задача о составлении графика ремонта инструмента может быть сведена к

эквивалентной ей транспортной задаче и тем самым для её решения могут быть

применены методы решения транспортных задач. Будем считать, что в этой за-

даче "производится" изношенный инструмент и таких пунктов производства

равно

с "производительностью" в каждом пункте

njr

)1(1(

изношенного

инструмента. Имеется еще один пункт производства инструмента, под которым

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

∑

единиц, т.е. если бы перед нами не была поставлена задача мини-

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

бы на каждый день новый инструмент.

Имеется

пунктов потребления и в каждом пункте потребляется или но-

вый инструмент, приобретенный в магазине, или прошедший ремонт (обычный

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

njr

)1(1(

единиц.

Назначим следующие стоимости перевозок

единицы товара (в нашем

случае инструмента) из

−

го пункта производства в

−

й пункт потребления

при

, , aMqij

> >+≤

при

,pijqi

+≤<+

bс

при

jpi

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

требления

).)1(1( ,

njac

Поясним каждое назначение. Первая строчка делает невозможным потреб-

ление изношенного инструмента, не прошедшего хотя бы срочного ремонта,

длительность которого

дней. Вторая строка определяет, что изношенный в

−

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

−

й день, где

,,,2 ,1 piqiqij

+++++=



только после срочного ремонта, так как для

−

го

дня, где

,,,2 ,1 npipij



++++=

успеет поступить инструмент, который про-

шел обычный ремонт стоимостью

.cb

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

−

й день может

поступить в

−

й день, где

,,,2 ,1 npipij



++++=

после обычного ремонта и

нет необходимости прибегать к срочному ремонту.

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

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

отправлен на склад без всяких затрат. Подчеркнем, что в рассматриваемом слу-

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

мент, стоимость единицы которого

с другой - на склад отправляется изно-

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

срочный). Тем самым стоимость перевозки

означает "перемещение"

на складе и поэтому эта стоимость равна нулю.

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

ной на пять дней, требуется ежедневно по десять единиц некоторого инстру-

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

производственной программы, рассчитанной на пять дней, требуется ежеднев-

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

шивается. Известно, что срочный ремонт одного инструмента длится один день

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

стоит один рубль, а один новый инструмент стоит шесть рублей.

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

пяти дней при минимальных издержках на его ремонт и покупку.

Условия эквивалентной транспортной задачи представлены в виде следу-

ющей таблицы.

10 10 10 10 10 50

∞ ∞

5 1 1 0

∞ ∞ ∞

5 1 0

∞ ∞ ∞ ∞

5 0

∞ ∞ ∞ ∞ ∞

50 6 6 6 6 6 0

Здесь для уравновешивания баланса производства и потребления с потреб-

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