- •Тема 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. Алгоритм расчета параметров сг:
Тема 3. Симплексный метод решения задач линейного программирования
План лекции:
1. Суть симплексного метода
2. Критерий оптимальности решения ЗЛП
3. Алгоритм основного симплекс-метода
4. Алгоритм двойственного симплекс-метода
5. Алгоритм смешанного симплекс-метода
6. Особые случаи симплекс-метода
1. Суть симплексного метода
Суть симплекс-метода заключается в том, что решение ЗЛП осуществляется итерационно и основывается на переходе от одного допустимого базисного решения к другому, при котором значение целевой функции улучшается. Этот процесс длится до тех пор, пока дальнейшее улучшение целевой функции станет невозможно.
В алгебраических терминах симплекс-метод предполагает:
1) умение находить начальный опорный план;
2) наличие признака оптимальности опорного плана;
3) умение переходить к нехудшему опорному плану.
Геометрический смысл симплекс-метода состоит в последовательном переходе от одной вершины многогранника ОДР к соседней, в которой целевая функция принимает лучшее значение, до тех пор, пока не будет найдено оптимальное решение.
Симплексный метод универсален, поскольку позволяет решить любую ЗЛП.
2. Критерий оптимальности решения злп
Для использования симплекс-метода ЗЛП должна быть приведена к каноническому виду с предпочтительными переменными.
Критерий оптимальности. Решение ЗЛП является оптимальным, если неотрицательны коэффициенты целевой функции при переменных, имеющих определенный смысл (экономический, технологический, физический), и все свободные члены в правой части уравнений системы ограничений ( ).
В ходе решения ЗЛП могут возникнуть 4 случая:
1) , следовательно, план не оптимален и используется основной симплекс-метод;
2) , следовательно, план не оптимален и применяется двойственный симплекс-метод;
3) , следовательно, план не оптимален и применяется смешанный симплекс-метод;
4) , следовательно, согласно критерию оптимальности, план оптимален.
3. Алгоритм основного симплекс-метода:
1) Записать математическую модель в допустимом предпочтительном виде канонической формы.
2) Составить нулевую итерацию, записав математическую модель ЗЛП в первую симплекс-таблицу и взяв в качестве базисных переменных предпочтительные.
3) При наличии отрицательных коэффициентов целевой функции сj осуществить подготовку к переходу к новому решению по следующей схеме:
а) среди отрицательных коэффициентов целевой функции выбрать максимальный по модулю, соответствующий столбец в симплекс-таблице называется разрешающим и помечается знаком *.
б) среди всех отношений правых частей системы ограничений к положительным элементам разрешающего столбца выбрать минимальное, соответствующая строка называется разрешающей и помечается знаком *.
в) элемент, стоящий на пересечении разрешающего столбца и разрешающей строки, называется разрешающим и помещается в рамку .
4) Заполнить следующую симплекс-таблицу:
а) базисную переменную (б.п.) в разрешающей строке заменить на переменную разрешающего столбца, все остальные переменные оставить в неизменном порядке;
б) заполнить столбцы базисных переменных: на пересечении столбца и строки базисной переменной поставить 1, остальные элементы столбца приравнять нулю;
в) если в разрешающем столбце прежней таблицы есть 0, то соответствующую ему строку переписать без изменений;
г) если в разрешающей строке прежней таблицы есть 0, то соответствующий ему столбец переписать без изменений;
д) построить опорную строку (·) в новой таблице, разделив все элементы разрешающей строки прежней таблицы на разрешающий элемент;
е) все остальные элементы новой таблицы определяются по правилу треугольника: новый элемент равен прежнему минус произведение соответствующего по строке элемента в разрешающем столбце прежней таблицы на элемент опорной строки в столбце искомого элемента новой таблицы; исключением является элемент, стоящий на пересечении строки целевой функции и столбца свободных членов ограничений, для которого в правиле треугольника "–" следует заменить на "+".
5) Целевая функция в новой таблице проверяется на оптимальность: если при реальных переменных, то получен оптимальный план решения ЗЛП, а если среди сj есть отрицательный коэффициент, то перейти к пункту 2 алгоритма.
Задача. Для изготовления двух видов , продукции используют три вида ресурсов , , . Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в технологической таблице:
Вид ресурса |
Число единиц ресурсов, затрачиваемых на изготовление единицы продукции |
Объем ресурса |
|
|
|
||
|
1 |
2 |
12 |
|
0 |
1 |
8 |
|
2 |
1 |
20 |
Прибыль от реализации единицы продукции, ден. ед. |
2 |
4 |
|
Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной.
Решение задачи:
Введем обозначения: х1 – количество продукции первого вида, х2 – количество продукции второго вида. Тогда экономико-математическая модель задачи примет вид:
.
Преобразуем математическую модель ЗЛП к допустимому предпочтительному виду канонической формы:
.
По алгоритму основного симплекс-метода заполним симплексную таблицу задачи:
|
б.п. |
|
|
|
|
|
|
0 |
|
1 |
1 |
1 |
0 |
0 |
12 |
* |
0 |
1 |
0 |
1 |
0 |
8 |
|
|
2 |
1 |
0 |
0 |
1 |
20 |
|
|
F |
–2 |
–4* |
0 |
0 |
0 |
0 |
1 |
* |
1 |
0 |
1 |
–1 |
0 |
4 |
|
0 |
1 |
0 |
1 |
0 |
8 |
|
|
2 |
0 |
0 |
–1 |
1 |
12 |
|
|
F |
–2* |
0 |
0 |
4 |
0 |
–32 |
2 |
|
1 |
0 |
1 |
–1 |
0 |
4 |
|
0 |
1 |
0 |
1 |
0 |
8 |
|
|
0 |
0 |
–2 |
1 |
1 |
4 |
|
|
F |
0 |
0 |
2 |
2 |
0 |
–40 |
Итак, получили, что . Следовательно, согласно критерию оптимальности, план оптимален.
Ответ:
Таким образом, для получения максимальной прибыли в размере 40 ден. ед. надо продать 4 изделия первого вида и 8 изделий второго вида.