Минимальное из значений равно 5 и соответствует B₄: 4-ая деталь обрабатывается последней.

2	3
4	6
-	-
-	-
9	5
8	3

Минимальное из значений соответствует A₅: 5-ая деталь обрабатывается первой.

2	3
4	6
6	8
-	-
9	5
8	3

Минимальное из значений равно 7 и соответствует B₆: 6-ая деталь обрабатывается последней.

2	3
4	6
6	8
9	7
9	5
8	3

2	3
4	6
6	8
9	7
9	5
8	3

max(2 , 2 + 8 - 3 , 2 + 8 + 4 - 3 - 3 , 2 + 8 + 4 + 9 - 3 - 3 - 6 , 2 + 8 + 4 + 9 + 6 - 3 - 3 - 6 - 5 , 2 + 8 + 4 + 9 + 6 + 9 - 3 - 3 - 6 - 5 - 8 ) = max(2, 7, 8, 11, 12, 13) = 13
Время простоя при оптимальной перестановке равно:
max(2 , 2 + 4 - 3 , 2 + 4 + 6 - 3 - 6 , 2 + 4 + 6 + 9 - 3 - 6 - 8 , 2 + 4 + 6 + 9 + 9 - 3 - 6 - 8 - 7 , 2 + 4 + 6 + 9 + 9 + 8 - 3 - 6 - 8 - 7 - 5 ) = max(2, 3, 3, 4, 6, 9) = 9

2.2 Задача о назначениях[6].

Задание. Рассматривается вычислительная система состоящая из n вычислительных машин. Имеется n задач. Задана матрица T определяющая время решения i-й задачи на j-м машине. Задачи решаются одновременно с некоторого момента t₀. Найти такое распределение задач по вычислительным машинам, чтобы общее время решения всех задач было бы минимальным при условии что на одной машине может решаться только одна задача.
Решение. Исходная матрица имеет вид:

5	5	M	2	2
7	4	2	3	1
9	3	5	M	2
7	2	6	7	8

Для устранения дисбаланса добавляем дополнительные строки.
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

3	3	M	0	0	2
6	3	1	2	0	1
7	1	3	M	0	2
5	0	4	5	6	2
0	0	0	0	0	0

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

3	3	M	0	0
6	3	1	2	0
7	1	3	M	0
5	0	4	5	6
0	0	0	0	0
0	0	0	0	0

---

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

3	3	M	[0]	[-0-]
6	3	1	2	[-0-]
7	1	3	M	[-0-]
5	[0]	4	5	6
[-0-]	[-0-]	[-0-]	[-0-]	[0]

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

3. Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов: строку 5, столбец 5, строку1,столбец2.

Получаем сокращенную матрицу (элементы выделены):

3	3	M	0	0
6	3	1	2	0
7	1	3	M	0
5	0	4	5	6
0	0	0	0	0

Минимальный элемент сокращенной матрицы (1) вычитаем из всех ее элементов:

3	3	M	0	0
5	3	0	1	0
6	1	2	M	0
4	0	3	4	6
0	0	0	0	0

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

3	4	M	0	1
5	3	0	1	0
6	1	2	M	0
4	0	3	4	6
0	1	0	0	1

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

3	4	M	0	1	0
5	3	0	1	0	0
6	1	2	M	0	0
4	0	3	4	6	0
0	1	0	0	1	0

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

3	4	M	0	1
5	3	0	1	0
6	1	2	M	0
4	0	3	4	6
0	1	0	0	1
0	0	0	0	0

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

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

3	4	M	[0]	1
5	3	[0]	1	[-0-]
6	1	2	M	[0]
4	[0]	3	4	6
[0]	1	[-0-]	[-0-]	1

В результате получаем эквивалентную матрицу Сэ:

3	4	M	0	1
5	3	0	1	0
6	1	2	M	0
4	0	3	4	6
0	1	0	0	1

---

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

3	4	M	[0]	1
5	3	[0]	1	[-0-]
6	1	2	M	[0]
4	[0]	3	4	6
[0]	1	[-0-]	[-0-]	1

Cmin = 2 + 2 + 2 + 2 + 0 = 8

2.3 Задача о  замене оборудования[7]

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

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

Найти оптимальную стратегию эксплуатации оборудования на период продолжительностью 6 лет, если годовой доход r(t) и остаточная стоимость S(t) в зависимости от возраста заданы в таблице, стоимость нового оборудования равна P = 10, а возраст оборудования к началу эксплуатационного периода составлял 1 год.

Начало формы

Конец формы

T	0	1	2	3	4	5	6
r(t)	8	8	7	7	6	6	5
S(t)	10	7	6	5	4	3	2

Решение:
I этап. Условная оптимизация (k = 6,5,4,3,2,1).
Переменной управления на k-м шаге является логическая переменная, которая может принимать одно из двух значений: сохранить (С) или заменить (З) оборудование в начале k-го года.
1-й шаг: k = 6. Для 1-го шага возможные состояния системы t = 1,2,3,4,5,6, а функциональные уравнения имеют вид:
F₆(t) = max(r(t), (C); S(t) - P + r(0), (З ) )
F₆(1) = max(8 ; 7 - 10 + 8) = 8 (C)
F₆(2) = max(7 ; 6 - 10 + 8) = 7 (C)
F₆(3) = max(7 ; 5 - 10 + 8) = 7 (C)
F₆(4) = max(6 ; 4 - 10 + 8) = 6 (C)
F₆(5) = max(6 ; 3 - 10 + 8) = 6 (C)
F₆(6) = max(5 ; 2 - 10 + 8) = 5 (C)
2-й шаг : k = 5. Для 2-го шага возможные состояния системы t = 1,2,3,4,5, а функциональные уравнения имеют вид:
F₅(t) = max(r(t) + F₆(t+1) ; S(t) - P + r(0) + F₆(1))
F₅(1) = max(8 + 7 ; 7 - 10 + 8 + 8) = 15 (C)
F₅(2) = max(7 + 7 ; 6 - 10 + 8 + 8) = 14 (C)
F₅(3) = max(7 + 6 ; 5 - 10 + 8 + 8) = 13 (C)
F₅(4) = max(6 + 6 ; 4 - 10 + 8 + 8) = 12 (C)
F₅(5) = max(6 + 5 ; 3 - 10 + 8 + 8) = 11 (C)
3-й шаг : k = 4. Для 3-го шага возможные состояния системы t = 1,2,3,4, а функциональные уравнения имеют вид:
F₄(t) = max(r(t) + F₅(t+1) ; S(t) - P + r(0) + F₅(1))
F₄(1) = max(8 + 14 ; 7 - 10 + 8 + 15) = 22 (C)
F₄(2) = max(7 + 13 ; 6 - 10 + 8 + 15) = 20 (C)
F₄(3) = max(7 + 12 ; 5 - 10 + 8 + 15) = 19 (C)
F₄(4) = max(6 + 11 ; 4 - 10 + 8 + 15) = 17 (C/ З )
4-й шаг : k = 3. Для 4-го шага возможные состояния системы t = 1,2,3, а функциональные уравнения имеют вид:
F₃(t) = max(r(t) + F₄(t+1) ; S(t) - P + r(0) + F₄(1))
F₃(1) = max(8 + 20 ; 7 - 10 + 8 + 22) = 28 (C)
F₃(2) = max(7 + 19 ; 6 - 10 + 8 + 22) = 26 (C/ З )
F₃(3) = max(7 + 17 ; 5 - 10 + 8 + 22) = 25 ( З )
5-й шаг : k = 2. Для 5-го шага возможные состояния системы t = 1,2, а функциональные уравнения имеют вид:
F₂(t) = max(r(t) + F₃(t+1) ; S(t) - P + r(0) + F₃(1))
F₂(1) = max(8 + 26 ; 7 - 10 + 8 + 28) = 34 (C)
F₂(2) = max(7 + 25 ; 6 - 10 + 8 + 28) = 32 (C/ З )
6-й шаг : k = 1. Для 6-го шага возможные состояния системы t = 1, а функциональные уравнения имеют вид:
F₁(t) = max(r(t) + F₂(t+1) ; S(t) - P + r(0) + F₂(1))
F₁(1) = max(8 + 32 ; 7 - 10 + 8 + 34) = 40 (C)
Результаты вычислений по уравнениям Беллмана F_k(t) приведены в таблице, в которой k - год эксплуатации, а t - возраст оборудования.

---

k / t	1	2	3	4	5	6
1	40	0	0	0	0	0
2	34	32	0	0	0	0
3	28	26	25	0	0	0
4	22	20	19	17	0	0
5	15	14	13	12	11	0
6	8	7	7	6	6	5

В таблице выделено значение функции, соответствующее состоянию (З) - замена оборудования.

II этап. Безусловная оптимизация (k = 6,5,4,3,2,1)
Безусловная оптимизация начинается с шага при k = 1. Максимальной возможный доход от эксплуатации оборудования за годы с 1-го по 7-й составляет F₁(1) = 40. Этот оптимальный выигрыш достигается, если на первом году не производить замены оборудования.
К началу 2-го года возраст оборудования увеличится на единицу и составит: t₂ = t₁ + 1 = 1 + 1 = 2.
Безусловное оптимальное управление при k = 2, x₂(2) = (C/З), т.е. для получения максимума прибыли за оставшиеся годы необходимо в этом году провести замену оборудования.
К началу 3-го года возраст оборудования увеличится на единицу и составит: t₃ = t₂ + 1 = 0 + 1 = 1.
Оптимальное управление при k = 3, x₃(1) = (C), т.е. максимум дохода за годы с 3-го по 6-й достигается, если оборудование сохраняется, т.е. не заменяется.
К началу 4-го года возраст оборудования увеличится на единицу и составит: t₄ = t₃ + 1 = 1 + 1 = 2.
Оптимальное управление при k = 4, x₄(2) = (C), т.е. максимум дохода за годы с 4-го по 6-й достигается, если оборудование сохраняется, т.е. не заменяется.
К началу 5-го года возраст оборудования увеличится на единицу и составит: t₅ = t₄ + 1 = 2 + 1 = 3.
Оптимальное управление при k = 5, x₅(3) = (C), т.е. максимум дохода за годы с 5-го по 6-й достигается, если оборудование сохраняется, т.е. не заменяется.
К началу 6-го года возраст оборудования увеличится на единицу и составит: t₆ = t₅ + 1 = 3 + 1 = 4.
Оптимальное управление при k = 6, x₆(4) = (C), т.е. максимум дохода за годы с 6-го по 6-й достигается, если оборудование сохраняется, т.е. не заменяется.

Таким образом, за 6 лет эксплуатации оборудования замену надо произвести в начале 2-го года эксплуатации.

Заключение

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

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

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

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

---

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

Литература

1. Л.В. Михайлова.- М-: ИТЦ МАТИ, 2002. Учебное пособие – С. 14-17. Формирование и оперативное управление производственными системами на базе поточно-группового производства в автоматизированном режиме.

2. В.А. Колемаев.- М-: Юнити-Дана, 2007. Учебник – С. 297-298. Математические методы и модели исследования операций.

3. Л.В. Михайлова.- М-: ИТЦ МАТИ, 2002. Учебное пособие– С. 25-29. Формирование и оперативное управление производственными системами на базе поточно-группового производства в автоматизированном режиме.

4. Л.В. Михайлова.- М-: ИТЦ МАТИ, 2002. Учебное пособие – С. 36-38. Формирование и оперативное управление производственными системами на базе поточно-группового производства в автоматизированном режиме.

5. Д.И. Коган.- Н. Новнород-: ННГУ, 2004. – Учебное пособие С. 52-53.

Задачи и методы конечной оптимизации.

6.Учебник / М.С. Красс, Б.П. Чупрынов.- М-: Финансы и статистика, 2007. – С. 306-311. Математика в экономике: Математические методы и модели.

7.Учеб. пособие. — 2-е изд., перераб. и доп. / Е.В. Бережная — М.: Финансы и статистика, 2006. - С. 368-374 / Математические методы моделирования экономических систем.

В.А. Колемаев.- М-: Юнити-Дана, 2007. – С. 592. Математические методы и модели исследования операций: Учебник ;

Л.В. Михайлова.- М-: ИТЦ МАТИ, 2002. – С. 60.

Формирование и оперативное управление производственными системами на базе поточно-группового производства в автоматизированном режиме;

Д.И. Коган.- Н. Новнород-: ННГУ, 2004. – С. 150.

Задачи и методы конечной оптимизации: Учебное пособие, 3 часть;

М.С. Красс, Б.П. Чупрынов.- М-: Финансы и статистика, 2007. – С. 544.

Математика в экономике:  Математические методы и модели: Учебник ;

Е.В. Бережная — М.: Финансы и статистика, 2006. - С. 432.

Математические методы моделирования экономических систем: Учебное пособие— 2-е изд., перераб. и доп.;

---

Смотрите также файлы

• Минералогия. Экзамен.docx

• Аристотель о материи и форме.docx

• ОЖД- для 1 курса 2014 год.docx

• нарушения угл. обмена.docx

• Лылов доп темы по MP-14.docx