- •Тема 1. Математическая модель задачи линейного программирования (злп)
- •1. Предмет математического программирования
- •2. Математическая модель мп
- •3. Основные типы задач мп:
- •4. Многокритериальная оптимизация
- •5. Основные понятия теории оптимизации
- •6. Постановка злп. Различные формы записи ее математической модели
- •Тема 2. Графический метод решения злп. Закономерности и общие свойства решения злп
- •1. Геометрическая интерпретация решения злп
- •2. Алгоритм решения злп графическим методом
- •3. Возможные случаи области допустимых решений при решении злп графическим методом:
- •4. Основные свойства решений злп:
- •5. Классификация решений злп
- •6. Решение злп с точки зрения линейной алгебры
- •Тема 3. Симплексный метод решения задач линейного программирования
- •1. Суть симплексного метода
- •2. Критерий оптимальности решения злп
- •3. Алгоритм основного симплекс-метода:
- •4. Алгоритм двойственного симплекс-метода:
- •5. Алгоритм смешанного симплекс-метода:
- •6. Особые случаи симплекс-метода:
- •Тема 4. Модифицированный симплекс-метод решения злп. Устойчивость оптимального решения злп
- •1. Обращенный базис и симплекс-множители
- •2. Модифицированный симплекс-метод
- •3. Устойчивость оптимального решения злп:
- •Тема 5. Двойственность в линейном программировании
- •1. Понятие двойственности и теневой цены
- •2. Правила построения двойственной злп
- •3. Основные теоремы двойственности и их экономическое содержание
- •Тема 6. Элементы теории матричных игр
- •1. Основные понятия
- •2. Теоремы теории игр для парных матричных игр с нулевой суммой
- •3. Способы решения задач ти:
- •Тема 7. Матричные статистические игры
- •1. Понятие статистической игры
- •2. Критерии выбора оптимальной стратегии при решении статистической игры
- •3. Кооперативные игры
- •Тема 8. Транспортная задача (тз)
- •1. Постановка тз
- •2. Математическая модель тз
- •3. Решение тз методом потенциалов
- •4. Проверка плана на оптимальность
- •5. Цикл пересчета
- •6. Метод дифференциальных рент
- •7. Дополнительные ограничения тз
- •Тема 9. Дискретное программирование
- •1. Задача целочисленного линейного программирования
- •2. Метод Гомори
- •3. Метод ветвей и границ
- •Тема 10. Элементы нелинейного программирования
- •1. Постановка задачи нелинейного программирования
- •2. Метод множителей Лагранжа
- •3. Задача выпуклого программирования
- •4. Задача квадратического программирования
- •Тема 11. Метод динамического программирования
- •1. Общая постановка задачи динамического программирования
- •2. Принцип оптимальности. Функциональные уравнения Беллмана
- •3. Задача оптимального распределения инвестиций
- •4. Задача о замене оборудования
- •Тема 12. Программирование на сетях
- •1. Основные понятия теории графов
- •2. Экстремальное дерево графа
- •3. Матричные способы задания графов. Упорядочение элементов орграфа
- •4. Потоки на сетях. Постановка задачи о максимальном потоке
- •5. Разрез на сети. Теорема Форда-Фалкерсона. Алгоритм решения задачи о максимальном потоке
- •Тема 13. Планирование на сетях
- •1. Понятие сетевого графика
- •2. Основные параметры сг
- •3. Связь временных параметров сг
- •4. Алгоритм расчета параметров сг:
4. Задача о замене оборудования
В начале планового периода из N лет имеется оборудование возраста t лет. Для каждого года планового периода известны стоимость r(t) произведенной с использованием имеющегося оборудования продукции и затраты u(t), связанные с его эксплуатацией. Эти характеристики зависят от возраста t оборудования. Известны также остаточная стоимость S оборудования, не зависящая от его возраста, и цена р единицы нового оборудования, не меняющаяся в рассматриваемом плановом периоде. Требуется разработать оптимальную политику в отношении имеющегося оборудования, то есть в начале каждого года планового периода установить, сохранить в этом году оборудование или продать его по остаточной стоимости S и купить новое по цене р, с тем чтобы ожидаемая прибыль за N лет достигла максимальной величины.
Здесь шаг – год планового периода. Число шагов равно числу лет планового периода. Состояние системы характеризуется возрастом оборудования. В начале каждого шага может быть выбрано одно из двух управлений: «сохранение» или «замена» оборудования. Целевая функция за плановый период . Ограничения определяются критерием замены оборудования: прибыль при дальнейшей эксплуатации старого меньше прибыли после его замены с учетом всех издержек. Если прибыль от нового оборудования равна прибыли при старом, то старое сохраняется еще на год, так как оно уже досконально изучено.
Задача решается с помощью принципа оптимальности Беллмана. Рассмотрим годы планового периода от конца к началу (обратный ход). Введем последовательность функций – максимальная прибыль, получаемая от оборудования возраста t за последние i лет планового периода.
Здесь , где t0 – возраст оборудования в начале планового периода.
Для последнего года оптимальная политика и максимальная прибыль находятся из условия:
– сохранение – замена
Рассмотрим прибыль за последние два года:
– сохранение – замена
Аналогично, для i последних лет:
– сохранение – замена
Для i = n: .
После этого остается пройти процесс в прямом направлении и сформулировать безусловную оптимальную политику в отношении имеющегося оборудования.
Для заполнения расчетной таблицы можно использовать следующий алгоритм:
1) Найти , .
2) Заполнить строку , переписав из таблицы данных соответствующие значения , все значения заменить на .
3) Начиная с i=2, расчет по строкам производится в следующей последовательности:
а) вычислить , где берется из уже заполненной строки;
б) вычислить , где сумма и слагаемые образуют треугольник, у которого одна из вершин всегда в первой строке над искомым значением, а вторая – в последней заполненной строке следующего столбца. Получаемые значения вносить в соответствующие клетки строки, начиная с первого , оставшиеся клетки строки заполнить значением ;
в) клетки с первым значением в процессе заполнения таблицы отделить от расположенных в строке левее разделительной границей смены управления;
г) если таблица не заполнена до последней строки, перейти к пункту а) и выполнить расчет для следующего значения индекса i.
Задача. Пусть s = 2, p = 15, t0 = 4. Прибыль и издержки предприятия в зависимости от возраста оборудования заданы таблицей:
t |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
r(t) |
30 |
30 |
29 |
29 |
29 |
28 |
28 |
u(t) |
10 |
10 |
12 |
13 |
14 |
15 |
16 |
j (t) = r(t) – u(t) |
20 |
20 |
17 |
16 |
15 |
13 |
12 |
Обратный ход.
Определим .
Заполним следующую таблицу по ранее указанному алгоритму:
Zi(t)/t |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
mi |
Z1(t) |
20 |
20 |
17 |
16 |
15 |
13 |
12 |
7 |
Z2(t) |
40 |
37 |
33 |
31 |
28 |
27 |
27 |
27 |
Z3(t) |
57 |
53 |
48 |
44 |
44 |
44 |
44 |
44 |
Z4(t) |
73 |
68 |
61 |
60 |
60 |
60 |
60 |
60 |
Z5(t) |
88 |
81 |
77 |
76 |
75 |
75 |
75 |
75 |
Z6(t) |
101 |
97 |
93 |
91 |
90 |
88 |
88 |
88 |
Прямой ход.
Максимальная прибыль при оптимальной политике .
Эта клетка находится слева от границы, следовательно, для достижения максимальной прибыли в начале первого года планового периода оборудование надо сохранить. В течение первого года оборудование постареет на год. Таким образом, за пять лет до конца планового периода будем иметь оборудование возраста пяти лет. Из таблицы возьмем . Эта клетка справа от границы, следовательно, во втором году планового периода меняем оборудование, и по окончании этого года за четыре года до конца планового периода будем иметь оборудование возраста один год и т.д. Получаем оптимальную политику управлений:
Итак, заменить оборудование необходимо только на втором году планового периода с тем, чтобы получить максимальную прибыль в размере 75 усл. ед.
Замечание 11.2. По решению для шестилетнего планового периода можно получить решение по оптимальной политике замен на каждом плановом периоде длительностью, не превосходящей шести лет.
Например, для N = 3: и
Замечание 11.3. Задачу можно усложнить, например, допуская замену не новым оборудованием, а уже проработавшим некоторое время. При этом возможны три управления: сохранение старого, покупка нового, покупка не нового оборудования.
Педагогический комментарий. Данное лекционное занятие закладывает основы для формирования следующих профессиональных умений студентов-экономистов: умение выявлять проблемы экономического характера при анализе конкретных ситуаций, предлагать способы их решения и оценивать ожидаемые результаты; умение разрабатывать и обосновывать варианты эффективных многошаговых производственно-технологических решений; умение ставить цель и формулировать задачи, связанные с профессиональной деятельностью, умение использовать для их решения методы изученных дисциплин; умение логически мыслить; умение совершенствовать составление оперативно-производственного плана с использованием инструментария математического программирования; умение эффективно управлять экономическими процессами и регулировать использование комплекса имеющихся ресурсов; умение осуществлять выбор объектов финансовых инвестиций; умение рассчитывать календарно-плановые нормативы.