- •Тема 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. Задача квадратического программирования
Одним из частных видов ЗВП является задача, в которой целевая функция содержит квадратичное слагаемое, а ограничения носят линейный характер. Такая задача относиться к квадратичному программированию.
В качестве основной в квадратичном программировании рассматривается задача минимизации функции
,
при ограничениях .
Далее будем считать, что решаемая задача квадратичного программирования является частным случаем ЗВП.
Функция Лагранжа в данном случае имеет вид:
.
Найдем стационарные точки функции Лагранжа:
С учетом ориентации и применяя теорему Куна-Таккера:
(10.1)
(10.2)
Преобразуем систему (10.1) к системе уравнений:
Отсюда:
Тогда систему уравнений (10.2) можно записать в виде:
. (10.3)
Чтобы учесть условие (10.3) при решении ЗНП надо следить за тем, чтобы среди базисных переменных не было u и x с одним и тем же индексом, аналогично λ и v.
Далее задача решается методом искусственного базиса.
Задача. Минимизировать функцию при ограничениях:
Составим функцию Лагранжа:
.
Составим локальные условия Куна-Таккера:
Преобразуем полученную систему ограничений к допустимому виду канонической формы:
Далее решаем задачу методом искусственного базиса, учитывая условие (10.3):
N |
б.п. |
x1 |
x2 |
λ1 |
λ 2 |
u1 |
u2 |
v1 |
v2 |
z |
b |
0 |
u1 |
-0,4 |
0 |
-2 |
-2 |
1 |
0 |
0 |
0 |
0 |
2 |
z |
0 |
0,4 |
3 |
1 |
0 |
-1 |
0 |
0 |
1 |
3 |
|
v1* |
2 |
3 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
13 |
|
v2 |
2 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
10 |
|
G |
0 |
-0,4* |
-3 |
-1 |
0 |
1 |
0 |
0 |
0 |
3 |
|
1 |
u1 |
-0,4 |
0 |
-2 |
-2 |
1 |
0 |
0 |
0 |
0 |
2 |
z* |
-4/15 |
0 |
3 |
1 |
0 |
-1 |
-2/15 |
0 |
1 |
19/15 |
|
x2 |
2/3 |
1 |
0 |
0 |
0 |
0 |
1/3 |
0 |
0 |
13/3 |
|
v2 |
4/3 |
0 |
0 |
0 |
0 |
0 |
-1/3 |
1 |
0 |
17/3 |
|
G |
41/5 |
0 |
-3* |
-1 |
0 |
1 |
2/15 |
0 |
0 |
19/15 |
|
2 |
u1 |
|
0 |
0 |
|
1 |
|
|
0 |
|
128/45 |
λ1 |
-4/45 |
0 |
1 |
1/3 |
0 |
-1/3 |
-2/45 |
0 |
1/3 |
19/45 |
|
x2 |
2/3 |
1 |
0 |
0 |
0 |
0 |
1/3 |
0 |
0 |
13/3 |
|
v2 |
4/3 |
0 |
0 |
0 |
0 |
0 |
-1/3 |
1 |
0 |
17/3 |
|
G |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
Получили оптимальный план решения задачи . Найдем значение целевой функции в данной точке:
.
Ответ: , .
Педагогический комментарий. Данное лекционное занятие закладывает основы для формирования следующих профессиональных умений студентов-экономистов: умение разрабатывать и обосновывать варианты эффективных производственно-технологических решений; умение ставить цель и формулировать задачи, связанные с профессиональной деятельностью, умение использовать для их решения методы изученных дисциплин; умение логически мыслить; умение совершенствовать составление оперативно-производственного плана с использованием инструментария математического программирования; умение эффективно управлять экономическими процессами и регулировать использование комплекса имеющихся ресурсов; умение использовать аналитические методы решения задач математического программирования при наличии нелинейных функциональных зависимостей экономических переменных.