Поиск по базе сайта:
Пояснительная записка по курсовой работе по курсу «Теория принятия решений» вариант 77 студент группы 631 Ульбеков А. Д icon

Пояснительная записка по курсовой работе по курсу «Теория принятия решений» вариант 77 студент группы 631 Ульбеков А. Д




Скачати 120.06 Kb.
НазваПояснительная записка по курсовой работе по курсу «Теория принятия решений» вариант 77 студент группы 631 Ульбеков А. Д
Дата конвертації26.11.2013
Розмір120.06 Kb.
ТипПояснительная записка


Федеральное агентство по образованию
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ
УНИВЕРСИТЕТ
имени академика С.П.КОРОЛЕВА»
Факультет информатики
Кафедра информационных систем и технологий

Пояснительная записка
по курсовой работе
по курсу «Теория принятия решений»

вариант 77

Выполнил:
студент группы 631
Ульбеков А. Д.
Проверил:
Есипов Б. А.

2011 г.

Содержание


1. Тема курсового проекта 3

2. Задание 3

3. Математическое моделирование 3

4. Обоснование и выбор метода решения 4

5. Решение задачи при помощи компьютерных средств 6

5.1 Решение задачи на LINDO 6.1 6

5.2 Решение задачи на Excel 7

6. Формулировка полученного решения 9

Список литературы 10
^

1. Тема курсового проекта


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

2. Задание


Имеется M ремонтных баз, на каждой из которых производится N различных видов ремонта локомотивов. Известно, что стоимость выполнения j-го вида ремонта на i-ой базе равна Cij. Допустимая загрузка базы в течение месяца по каждому из видов ремонта равна kij. Средняя месячная потребность в выполнении ремонтов Bj-го вида известна.

Требуется организовать по рациональному плану размещение различных видов ремонта локомотивов по ремонтным базам. Исходные данные для решения задачи приведены в табл. 1, 2, 3.


Таблица 1

Значение параметра

M

6

N

8


Таблица 2




Месячная потребность в выполнении ремонтов Bj

b1

b2

b3

b4

b5

b6

b7

b8

77

45

27

58

44

29

56

45

51


Таблица 3

j

C1j

K1j

C2j

K2j

C3j

K3j

C4j

K4j

C5j

K5j

C6j

K6j

1

200

25

100

17

150

33

175

27

120

37

135

42

2

1100

370

1800

420

1750

450

1325

370

1570

520

1430

367

3

870

1710

1050

1560

690

1720

780

1930

955

1660

847

1950

4

5120

620

4850

750

5500

830

6200

670

5700

875

5920

763

5

670

3410

710

2980

815

3780

935

4150

797

3780

823

3610

6

35

78

47

56

95

99

67

101

78

67

87

92

7

150

590

175

830

143

633

185

576

197

485

201

675

8

2570

87

2310

125

1980

347

3120

47

2580

876

2610

253



^

3. Математическое моделирование



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

i – номер ремонтной базы;

j – вид ремонта.

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

Xij – количество ремонтов j-ого типа, которые будут производиться на базе i-ого типа.

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

(1)

Далее, введем неуправляемые переменные:

Bj – средняя месячная потребность в выполнении ремонтов j-ого типа, т.е. число ремонтов j-го типа, которое должны произвести ремонтные базы;

Сij – стоимость выполнения j-го вида ремонта на i-ой базе;

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

Теперь построим ограничения. Для нашей задачи необходимо соблюдение условия выполнения потребности в ремонтах, т.е. чтобы суммарное месячное количество выполненных ремонтов j-го типа превышало потребность в их выполнении :

(2)

Еще одно ограничение – допустимая загрузка базы в течение месяца по каждому из видов ремонта :

(3)

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


^

4. Обоснование и выбор метода решения



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

Рассмотрим 2 метода решения задач дискретного программирования: метод отсечения или отсекающих плоскостей и метод ветвей и границ.

^ Метод отсекающих плоскостей. Для группы методов отсечения, или отсекающих плоскостей, характерна так называемая «регуляризация» задачи, состоящая в погружении исходной области допустимых решений в объемлющую ее выпуклую область, т.е. во временном отбрасывании условий дискретности. Затем к получившейся регулярной задаче применяются стандартные методы оптимизации. Если полученное в результате решение удовлетворяет требуемым условиям дискретности, то задача решена. В противном случае необходим дальнейший переход к целочисленному решению, причем этот переход не может быть получен простым округлением компонент нецелочисленного решения.

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

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

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

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



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

Для ветвления используется следующий алгоритм. Пусть какая-то управляемая переменная хl = d – дробное число, тогда все варианты решения можно разбить на 2 подмножества:

G1: (2) & хl ≤ [d]

G2: (2) & хl ≥ [d+1]

Решаем задачу линейного программирования на 1 и 2 подмножествах. Если на обоих подмножествах решение не целочисленное, то сравниваем эти оценки и выбираем перспективное подмножество. Эту операцию производим пока не получим целое решение х*. Проверяем условие оптимальности. Если оно выполняется, то это и есть искомое оптимальное решение, а если нет, то снова находим перспективное подмножество и т.д. Далее мы либо получим новое решение, либо покажем, что х* - оптимальное.


^

5. Решение задачи при помощи компьютерных средств



Для решения нашей задачи воспользуемся двумя программами – пакетом экономических расчетов LINDO 6.1 и программой Microsoft Excel.

^

5.1 Решение задачи на LINDO 6.1


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

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

После ввода решаем задачу. Получаем решение за 37 шагов.





Итак, в результате решения задачи получили значение целевой функции равное 450695, при этом х12 = 27, х14 = 12, х15 = 29, х16 = 56, х18 = 3, х21 = 17, х24 = 15, х28 = 5, х33 = 58, х34 = 15, х37 = 45, х38 = 17, х51 = 28, х54 = 2, х58 = 26, все остальные переменные равны нулю.

^

5.2 Решение задачи на Excel


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

Решая задачу в программе Excel нужно сначала выделить ячейки для хранения переменных, ограничений и целевой функции. После этого выбираем в меню Сервис -> Поиск решения. В появившемся окне задаем ячейку, в которой лежит целевая функция, указываем, что ее нужно устремить к максимуму. Далее вводим номера ячеек, в которых лежат управляемые переменные и ячейки, в которых находятся формулы ограничений. При этом нужно для каждой переменной указать, что она является целым числом.




Нажав на кнопку «Выполнить», получаем в ячейках переменных и целевой функции соответствующие значения:

Таким образом, в результате решения на Excel получили значение целевой функции равное 450695, при этом х12 = 27, х14 = 12, х15 = 29, х16 = 56, х18 = 3, х21 = 17, х24 = 15, х28 = 5, х33 = 58, х34 = 15, х37 = 45, х38 = 17, х51 = 28, х54 = 2, х58 = 26, все остальные переменные равны нулю.

Видно, что оптимальные значение переменных и значение целевой функции получились точно такие же, как и в LINDO.
^

6. Формулировка полученного решения



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

На 1 ремонтной базе должно быть выполнено:

27 ремонтов 2-го типа;

12 ремонтов 4-го типа;

29 ремонтов 5-го типа;

56 ремонтов 6-го типа;

3 ремонта 8-го типа.

На 2 ремонтной базе должно быть выполнено:

17 ремонтов 1-го типа;

15 ремонтов 4-го типа;

5 ремонта 8-го типа.

На 3 ремонтной базе должно быть выполнено:

58 ремонтов 3-го типа;

15 ремонтов 4-го типа;

45 ремонтов 7-го типа;

17 ремонтов 8-го типа;

На 4 ремонтной базе должно быть выполнено:

28 ремонтов 1-го типа;

2 ремонтов 4-го типа;

26 ремонтов 8-го типа;

При этом сумма затраченных денег будет равна 450695 руб.

Список литературы


1. Методы оптимизации и исследование опрераций. Конспект лекций: учеб. Пособие / Б.А. Есипов,. – Самара: Изд-во Самар. гос. аэрокосм. ун-та, 2007. – 90 с.

2. Зайченко Ю.П. «Исследование операций», Киев 1979г.




Схожі:




База даних захищена авторським правом ©lib.exdat.com
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації