- •Тема 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. Алгоритм расчета параметров сг:
6. Метод дифференциальных рент
При решении ТЗ методом дифференциальных рент наилучшим образом распределяют часть продукции между потребителями и на последующих итерациях постоянно уменьшают общую величину нераспределенных поставок.
Алгоритм метода:
1) В каждом столбце определяется минимальный тариф и соответствующая клетка помечается.
2) Отмеченные клетки заполняются максимально возможными поставками.
3) Оцениваются поставщики:
а) строки, соответствующие поставщикам, запасы которых неисчерпаны, являются положительными;
б) строки, соответствующие поставщикам, запасы которых исчерпаны, а потребности отмеченных потребителей неудовлетворены (с учетом всего столбца), являются отрицательными;
в) строки, соответствующие поставщикам, запасы которых исчерпаны, а потребности отмеченных потребителей удовлетворены (с учетом всех заполненных клеток столбца), имеют нулевую оценку; при этом, если заполненная клетка в нулевой строке связана через столбец с заполненной клеткой в отрицательной строке, то данная нулевая строка считается отрицательной, во всех других случаях – положительной.
4) Для каждого столбца, имеющего отмеченный тариф в отрицательной строке, находится разность между отмеченным тарифом и минимальным по величине тарифом, стоящим в положительной строке (может быть отмеченным).
5) Среди полученных разностей, отличных от 0, определяется минимальная. Это число называется промежуточной рентой.
6) Строится новая таблица, при этом тарифы, стоящие в положительных строках, переписываются без изменения, а тарифы, стоящие в отрицательных строках, увеличиваются на величину промежуточной ренты.
7) Переход к пункту 1.
Замечание 8.2. Если в строке или столбце окажется более одной выделенной клетки, то заполняются в первую очередь выделенные клетки, которые являются единственными в строке или столбце.
Замечание 8.3. Если удается распределить все запасы, то получен оптимальный план.
Замечание 8.4. При расчете оптимальной целевой функции необходимо вернуться к тарифам исходной таблицы, так как в последующих таблицах тарифы испорчены дифференциальными рентами.
Решим сформулированную ранее ТЗ методом дифференциальных рент. Построим следующие итерационные таблицы по указанному алгоритму:
|
120 |
50 |
190 |
110 |
оценка |
160 |
|
|
|
|
-140 |
140 |
|
|
|
|
+20 |
170 |
|
|
|
|
+120 |
рента |
- |
- |
2 |
4 |
|
|
120 |
50 |
190 |
110 |
оценка |
160 |
|
|
|
|
-20 |
140 |
|
|
|
|
+20 |
170 |
|
|
|
|
-0 |
рента |
- |
3 |
6 |
4 |
|
|
120 |
50 |
190 |
110 |
оценка |
160 |
|
|
|
|
0 |
140 |
|
|
|
|
0 |
170 |
|
|
|
|
0 |
рента |
- |
- |
- |
- |
|
В последней итерации удалось распределить все запасы, следовательно, получен оптимальный план.
Рассчитаем оптимальное значение целевой функции задачи .
Ответ: , .