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

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ PОССИЙСКОЙ

ФЕДЕPАЦИИ

ИPКУТСКИЙ ГОСУДАPСТВЕHHЫЙ

ТЕХHИЧЕСКИЙ УHИВЕPСИТЕТ

МАТЕМАТИЧЕСКИЕ

МЕТОДЫ СИСТЕМ

НОГО АНАЛИЗА И ТЕО

РИЯ ПРИНЯТИЯ РЕШЕ

НИЙ

Методические указания по курсовой работе

для студентов специальности 22.02

"Автоматизированные системы

обработки информации и управления "

Иркутск, 2008 г.

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

принятия решений: Пособие по курсовой работе. – Иркутск, изд-во Иркутск.

гос. технич. ун-та, 2008. – 79 с.

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

учебной дисциплине "Математические методы системного анализа и теория

принятия решений". Пособие предназначено для студентов специальностей

220100 – "Вычислительные машины, системы, сети и комплексы", 220200 –

"Автоматизированные системы обработки информации и управления", 071900

– "Информационные системы в наукоемких технологиях".

Библиогр. 21 назв.

Рецензент:

Подготовила к печати: Брянская А.Г.

План 2007. 2,4 печ. л., 2,5 уч.-изд. л. Тираж 100 экз. Зак. 366

ЛР № 020263 от 30.12.96

Иркутский государственный технический университет

664074, Иркутск, ул. Лермонтова, 83

1.ЦЕЛЬ И ЗАДАЧИ КУРСОВОЙ РАБОТЫ

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

студентами по дисциплине "Математические методы системного анализа и тео-

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

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

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

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

ционного управления;

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

которой разработана и обоснована её математическая модель;

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

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

реализован программный продукт;

- продемонстрировать навыки программиста, т.е. необходимо: составить

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

достоверность;

- оформить программу для передачи другим пользователям;

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

организации, для которой решается данная задача;

- показать способность работать с литературой.

2.ТЕМАТИКА И ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ

Курсовая работа может разрабатываться на базе тем, освещенных в учеб-

ных занятиях по дисциплине "Математические методы системного анализа и

теория принятия решений", однако её специфика, заключающаяся в многообра-

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

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

освоен самим студентом.

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

лированная задача, имеющая некоторый аналог в практике. При этом одна и та

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

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

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

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

ные для работы, метод решения задачи.

3. СОДЕРЖАНИЕ КУРСОВОЙ РАБОТЫ

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

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

ченного для передачи пользователю (заказчику).

Пояснительная записка должна содержать следующие разделы:

- постановка задачи;

- обоснование разработанной математической модели;

- краткие сведения о методе решения поставленной задачи;

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

- фрагмент листинга программы, относящийся к реализации алгоритма ре-

шения задачи;

- проверка достоверности полученных результатов;

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

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

ным индивидуального варианта задания;

- библиографический список, оформленный по ныне действующему ГО-

СТу.

Обратите внимание, в конце этих методических указаний библиографиче-

ский список оформлен, именно по ныне действующему ГОСТу.

4. ЗАЩИТА КУРСОВОЙ РАБОТЫ

Вначале руководителю курсовой работы сдаётся на проверку пояснитель-

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

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

ляются на следующие категории.

1.Замечания, которые требуют безусловного их устранения, например до-

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

устранения этих замечания курсовая работа не может быть зачтена.

2.Замечания, которые могут быть приняты к сведению, а по тем или иным

причинам студент не может (не хочет) их устранить. Оценка курсовой работы

при этом снижается.

3.Замечания, которые снимаются в ходе беседы руководителя курсовой ра-

боты и студента, и никак не влияют на оценку курсовой работы.

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

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

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

ботает с ним, воспользовавшись разделом пояснительной записки "Руко-

водство пользователя". При этом руководитель пояснительной записки может

ввести данные из заданного диапазона их изменения.

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

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

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

предлагает его доработать. Если же студент по тем или иным причинам не мо-

жет (не хочет) дорабатывать свой программный продукт, то руководитель сни-

жает оценку и проставляет её в соответствующих документах.

При приёмке программного продукта действует принцип спасателя: "Нет

спасения – нет вознаграждения", и никакие объяснения спасателей в своё

оправдание не принимаются. В на- шем случае этот принцип трансфор-

мируется следующим образом: "Если программный продукт или не выдал ре-

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

прос об оценке курсовой работы снимается.

ВАРИАНТЫ ТЕМ КУРСОВОЙ РАБОТЫ

ТЕМА 1. ЗАДАЧА ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ СУДОВ

ПО РЕГУЛЯРНЫМ ЛИНИЯМ

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

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

при эксплуатации на той или иной линии имеют различные характеристики. В

частности, различные суда имеют различное число заходов в промежуточные

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

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

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

Все эти причины приводят к тому, что эксплуатационные расходы, приходящи-

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

Исходя из данных о себестоимости грузокилометра и коммерческой за-

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

а) величина

−

месячный объем перевозок одним судном j-го типа i-ой

регулярной линии;

б) величина

−

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

но j-го типа, используемое на i-ой линии.

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

зок

))1(1( mia

по каждой линии, а также число

))1(1( njN

судов j-го типа,

при этом возможны два варианта задания. В первом из них

∑

где

- общее число судов и всё это число судов необходимо распределять по

m линиям.

Во втором варианте число судов

, которое будет распределено по m ре-

гулярным линиям может быть и не равно общему числу судов

, т.е. число су-

дов

−

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

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

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

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

расходов при выполнении (перевыполнении) заданного объема перевозок.

Все условия данной задачи сведены в таблицу 1.

Таблица 1

№ типа

судна ⇒

№ линии

⇓

• • •

Мини-

мальный

объем пе-

ревозок

• • •

• • • • • • • • • • • • • • • • • • • • •

• • •

• • • • • • • • • • • • • • • • • • • • •

• • •

Число

судов

• • •

Конкретные числовые значения представлены в таблице 2, при этом необ-

ходимо отметить следующее.

1.В верхних отделениях клеток таблицы указаны числа

в тыс. тонн, а в

нижних

в тыс. рублей, объем перевозок

в тыс. тоннах.

2.Отсутствие чисел

в i-ой строке и в j-ом столбце означает невоз-

можность использования судна j-го типа на i-ой регулярной линии.

Таблица 2

№ типа

судна

⇒

№ ли-

нии ⇓

1 2 3 4

Минимальный

объем

Перевозок

500

200

100

Число

судов

55 95 30 45

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

конкретными числовыми значениями таблицы 2, то выполненная курсовая ра-

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

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

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

а) количество номеров типов судов может быть 3, или, 4, или 5;

б) количество номеров линий может быть 3, или 4, или 5;

в) число судов каждого типа может взять из диапазона 25..100;

г) числа

могут быть взяты из диапазона

606

≤≤

;

д) числа

могут быть взяты из диапазона

503

≤≤

;

е) числа

могут взяты из диапазона

55080

≤≤

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

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

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

[9]. При этом необходимо распределить весь парк

судов по регулярным ли-

ниям.

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

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

начального допустимого базисного решения метод Данцига [9]. При этом необ-

ходимо распределить весь парк

судов по регулярным линиям.

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

ном на модифицированных жордановых исключениях [11]. При этом необхо-

димо распределить весь парк

судов по регулярным линиям.

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

дом [9]. При этом необходимо распределить весь парк

судов по регулярным

линиям.

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

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

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

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

полученного решения перейти к решению прямой задачи [9]. При этом необхо-

димо распределить весь парк

судов по регулярным линиям.

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

граммирование (метод Гомори) [9]. При этом необходимо распределить весь

парк

судов по регулярным линиям.

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

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

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

[9]. При этом допускается распределение не всего парка

судов по регуляр-

ным линиям; не востребованные суда, сдаются в аренду, принося тем самым

дополнительный доход.

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

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

начального допустимого базисного решения метод Данцига [9]. При этом до-

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

судов по регулярным линиям; не

востребованные суда, сдаются в аренду, принося тем самым дополни-

тельный доход.

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

ном на модифицированных жордановых исключениях [11]. При этом допус-

кается распределение не всего парка

судов по регулярным линиям; не вос-

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

ход. .

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

тодом [9]. При этом допускается распределение не всего парка

судов по ре-

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

мым дополнительный доход.

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

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

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

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

полученного решения перейти к решению прямой задачи [9]. При этом допус-

кается распределение не всего парка

судов по регулярным линиям; не вос-

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

ход.

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

граммирование (метод Гомори) [9]. При этом допускается распределение не

всего парка

судов по регулярным линиям; не востребованные суда, сдаются

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

ТЕМА 2. ЗАДАЧА СОСТАВЛЕНИЯ ОПТИМАЛЬНОГО ГРАФИКА

РЕМОНТА ИНСТРУМЕНТА

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

танной на

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

−

го дня

))1(1( njr

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

Поэтому часть (или весь) этого инструмента в конце

−

го дня сдается в обыч-

ный ремонт, часть (или весь) в срочный ремонт, а часть (или весь) изношенного

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

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

дней и

стоит

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

дней и стоит

рублей за единицу инструмента. Новый инструмент

стоит

рублей.

Требуется так составить график ремонта и покупки инструмента, чтобы

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

последовательных дней.

Конкретные числовые условия задачи сведены в таблицу 3.

Таблица 3

сутки

кол-во еди-

сутки

рублей

сутки

рублей

ниц

)4)1(1(

)7,6(

3 2 2 4 6

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

конкретными числовыми значениями таблицы 3, то выполненная курсовая ра-

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

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

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

а) количество последовательных дней может быть или 6, или 7, или 8

дней; при этом день, когда

, может быть любым из принятого диапазона;

б) количество единиц инструмента может быть взято из диапазона 15..45;

в) длительность обычного ремонта может быть или 2 суток, или 3 суток,

или 4 суток; а его стоимость или 1 руб. за единицу инструмента, или 2 руб. за

единицу инструмента, или 3 руб. за единицу инструмента;

г) длительность срочного ремонта может быть или 1 сутки, или 2 суток,

или 3 суток; а его стоимость или 3 руб. за единицу инструмента, или 4 руб. за

единицу инструмента, или 5 руб. за единицу инструмента;

д) стоимость нового инструмента или 5 руб. за единицу инструмента, или

6 руб. за единицу инструмента, или 7 руб. за единицу инструмента;

Примечание. В тот день, в который требуемое количество инструмента

, ремонтная служба и склад, на который сдаётся изношенный инструмент

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

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

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

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

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

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

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

[9].

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

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

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

эту задачу

к эквивалентной ей транспорт- ной задаче. Последнюю решить ме-

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

метод северо-западного угла [9,11].

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

эту задачу к эквивалентной ей транспортной задаче. Последнюю решить мето-

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

тод минимального элемента [9,11].

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

эту задачу к эквивалентной ей транспортной задаче. Последнюю решить вен-

герским методом [9,11].

ТЕМА 3. ТРАНСПОРТНАЯ ЗАДАЧА ПО КРИТЕРИЯМ СТОИМО-

СТИ И ВРЕМЕНИ

Имеется

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

определенное количество единиц однородного продукта, предназначенного к

отправке: в первом пункте имеется

единиц этого продукта, во втором -

единиц, в

−

м пункте

единиц, и, наконец, в

−

м пункте

единиц про-

дукта. Этот продукт следует доставить в

пунктов назначения (потребления),

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

единиц продукта, во

второй -

единиц, в

−

й пункт

единиц, и, наконец, в

−

й пункт

еди-

ниц продукта.

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

которым маршрутом (число таких маршрутов

), причем известна удель-

ная стоимость

перевозки одной единицы продукта из

−

го пункта отправле-

ния в

−

й пункт назначения. Общая стоимость перевозки по любому маршру-

ту пропорциональна количеству перевозимого продукта. Известно также время

перевозки продукта из

−

го пункта отправления в

−

й пункт назначения,

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

Удельные стоимости

и время перевозок

приведены в таблице, при

этом:

1) на пропускные способности коммуникаций ограничения не накладыва-

ются;

- количество условных единиц продукта;

3) в верхних отделениях клеток таблицы помещены удельные стоимости

в рублях, а в нижних - время перевозок

в часах.

Таблица 4

⇒

⇓

180