- •Тема 2. Линейное программирование 1 Лекция 1, практика 1.
- •Математическая модель общей задачи линейного программирования
- •Графическое решение злп.
- •Примеры некоторых типовых злп
- •2. Задача о смесях (планирование состава продукции).
- •3. Транспортная задача.
- •1. Математическая модель общей задачи линейного программирования
- •2. Графическое решение злп
- •1. Составить математическую модель задачи, т.Е. Записать целевую функцию и систему ограничений.
- •2. Построить область допустимых решений злп
- •3. Найти оптимальное решение злп.
- •Тема 2. Практика 1
- •2. Построим область допустимых решений.
- •3. Найдем оптимальное решение злп
- •Алгоритм графического решения злп
- •2. Построить область допустимых решений.
- •3. Найти оптимальное решение
- •Тема 2. Лекция 2, практика 2.
- •Графическое решение злп
- •Двойственность в задачах линейного программирования
- •Решение задачи линейного программирования средствами ms Excel
- •Анализ задач линейного программирования в ms Excel
- •1. Графическое решение злп
- •Решение.
- •1. Запишем экономико-математическую модель задачи.
- •2. Построим одр решений злп.
- •3. Выбор оптимального плана.
- •2. Двойственность в задачах линейного программирования
- •Экономический смысл двойственных оценок.
- •Тема 2. Практика 2.
- •3. Решение задачи линейного программирования средствами ms Excel
- •4. Анализ задач линейного программирования в ms Excel
Решение.
1. Запишем экономико-математическую модель задачи.
Внесем данные в таблицу:
|
Расходы сырья на единицу продукции (кг) |
Запасы сырья (кг) |
|
П1 |
П2 |
||
Сырье I |
2 |
1 |
400 |
Сырье II |
3 |
4 |
900 |
Цены на изделия в тыс ден.ед |
60 |
40 |
|
Пусть выпущено x1 шт. П1 и x2 шт. П2.
Целевая функция представляет собой выражение для расчета выручки от реализации произведенных изделий, которую необходимо максимизировать:
(1)
Для построения системы ограничений найдем затраты сырья каждого типа, идущего на изготовление указанного количества изделий.
Сырье I: (кг.) Сырье II: (кг.)
|
Мы не можем израсходовать сырья больше, чем имеется в наличии. По смыслу задачи . Получаем систему линейных ограничений данной задачи: |
|
Целевая функция вместе с системой линейных ограничений представляет собой экономико-математическую модель ЗЛП.
2. Построим одр решений злп.
Выпишем уравнения прямых, соответствующих каждому из неравенств, входящих в систему ограничений. Вычислим координаты точек пересечения этих прямых с осями координат, построим эти прямые, а затем заштрихуем полуплоскости, отвечающие решениям всех неравенств.
Область пересечения всех этих полуплоскостей и будет искомым решением системы линейных ограничений.
(1)
Если x1=0, то x2=400. Получаем точку (0; 400).
Если x2=0, то x1=200. Получаем точку (200; 0).
(2)
Если x1=0, то x2=225. Получаем точку (0; 225).
Если x2=0, то x1=300. Получаем точку (300; 0).
(3) . Этой прямой соответствует ось Ox1.
(4) . Этой прямой соответствует ось Ox2.
Результаты вычислений и построений представлены на рисунке. Решением системы неравенств является многоугольник OACD, иначе называемый симплексом решений задачи линейного программирования.
Найдем координаты вершин О(0;0), A (0;225), D (200;0) C (140; 120).
3. Выбор оптимального плана.
В линейном программировании доказывается теорема о том, что если оптимальное решение ЗЛП существует, то оно обязательно совпадает с координатами одной из угловых точек симплекса решений системы линейных ограничений.
Вычисляем значения целевой функции в каждой угловой точке и выбираем наибольшее:
Максимальное значение целевой функции достигается в точке C. Следовательно, оптимальный план выпуска изделий равен x1=140 шт. изделий П1 и x2=120 шт. изделий П2. Выручка от реализации в этом случае будет максимальна и составит 13200 тыс. ден.ед.
2. Двойственность в задачах линейного программирования
Каждой задаче линейного программирования, которую будем называть исходной или основной, соответствует двойственная задача линейного программирования. Обе задачи называют взаимно двойственными. Правила записи двойственных задач рассмотри на примере. Пусть имеется исходная задача.
Пример построения пары двойственных задач
Задача 1 – исходная |
Задача 2 – двойственная |
|
|
|
|
Сформулируем правила записи двойственных задач. Пусть дана основная задача, тогда двойственная задача формулируется по следующим правилам:
1. Если основная задача сформулирована на max, то двойственная должна быть сформулирована на минимум.
2. Коэффициенты при неизвестных в целевой функции двойственной задачи являются свободными членами в системе ограничений исходной задачи. А правыми частями в ограничениях двойственной задачи станут коэффициенты при неизвестных в целевой функции исходной задачи.
3. Если А – матрица коэффициентов при неизвестных в системе ограничений основной задачи, то АТ матрица коэффициентов при неизвестных в системе ограничений двойственной задачи.
4. Число переменных в двойственной задаче равно числу ограничений исходной задачи, а число ограничений двойственной задачи соответственно равно числу переменных в исходной задаче.
5. Если в исходной задаче, сформулированной на максимум, все функциональные ограничения имеют знак ≤, то в двойственной задаче все неизвестные ≥ - неотрицательны4.
Математическая запись:
Задача 1 – основная |
Задача 2 – двойственная |
|
|
Взаимосвязь оптимальных решений пары двойственных задач определена теоремой.
Теорема 1. Если одна из задач двойственной пары имеет оптимальное решение, то другая задача также имеет оптимальное решение, причем максимальное значение целевой функции исходной задачи и минимальное значение целевой функции двойственной задачи численно совпадают.
Решая графически, получим ответ.
Ответ: минимальное значение F(y) =13200, при у1= 24 и y2=4