Графический метод характеризуется простотой и наглядностью, однако он недостаточно точен и применим только для задач с не более чем тремя переменными. Последнее обусловлено тем, что человек, живущий в трехмерном пространстве, практически не способен представить себе визуально пространство более высокого порядка.
Метод основан на том, что каждое ограничение неравенство отсекает в n -мерном пространстве n -мерную полуплоскость (в данной курсовой работе это двухмерное пространство (плоскость) и простая полуплоскость). Совокупность этих полуплоскостей (если ограничения совместны) образует n -мерный многогранник допустимых решений. Оптимальное решение достигается в одной из вершин многогранника. Для определения этой вершины необходимо построить поверхность уровня целевой функции (в курсовом проекте линию уровня). Затем следует перемещать эту поверхность (линию) в направлении градиента до крайней точки области допустимых решений (ОДР).
Рассмотрим следующий простой пример решения задачи линейного программирования (ЗЛП) графическим методом.
Математическая модель: 2Х1+3Х2≤60;
3Х1+2Х2≤60;
4Х1+20Х2≤200;
Х1≥0; Х2≥0;
F=40Х1+30Х2→Мах.
Перейдем от неравенств к равенствам: 2Х1+3Х2=60;
3Х1+2Х2=60;
4Х1+20Х2=200.
Это уравнения прямых линий, которые могут быть легко построены по двум точкам:
для первого ограничения Х1=0; Х2=20;
Х2=0; Х1=30.
для второго ограничения Х1=0; Х2=30;
Х2=0; Х1=20.
для третьего ограничения Х1=0; Х2=10;
Х2=0; Х1=50.
Градиент целевой функции это вектор, характеризующий направление и скорость изменения функции (в данном случае целевой функции). Он определяется ее частными производными по каждой переменной:
Линия уровня целевой функции перпендикулярна градиенту.
Графическое решение данной задачи приведено на рисунке 6.1.
Рис. 6.1. Графическое решение задачи
Область допустимых решений (ОДР) в данном случае образуется четырехугольником ОВСД. Ни одна точка внутри его или на его границе не противоречит ни одному из ограничений. Оптимальное решение находится в одной из вершин четырехугольника. Для нахождения оптимального решения перемещаем линию уровня целевой функции в направлении градиента до крайней точки ОДР. Такой точкой является точка С с координатами: Х1=16; Х2=8. Значение целевой функции F=40×16+30×8=880. Очевидно, что это решение не отличается высокой точностью, что характерно для графического метода.
Из рисунка видно, что ресурсы второго и третьего видов использованы полностью, а ресурс первого вида оказался в избытке. Для количественной оценки этого избытка определим сначала расход данного ресурса: 2×16+3×8=56. Запас равен 60, тогда остаток составит 6056=4.
- 6.1.2. Симплексный метод решения задач линейного программирования
- Технико-экономический анализ полученного решения
- Технико-экономический анализ полученного решения
- ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
- Вектор градиента целевой функции
- Вектор градиента целевой функции
- 6.1.2. Симплексный метод решения задач линейного программирования
- Технико-экономический анализ полученного решения
- Технико-экономический анализ полученного решения
- ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
- 🔥 Видео
6.1.2. Симплексный метод решения
задач линейного программирования
В отличие от графического метода, симплексный метод абсолютно точен. Кроме того, он дает возможность для точной количественной оценки излишков имеющихся ресурсов, а применение двойственного симплекс-метода дает еще и большие возможности для технико-экономического анализа полученного решения с целью выработки обоснованных рекомендаций по улучшению условий функционирования системы.
Приведем задачу, рассмотренную в предыдущем разделе, к канонической форме: 2Х1+3Х2+Х3=60;
3Х1+2Х2+Х4=60;
4Х1+20Х2+Х5=200;
F-40Х1 -30Х2 =0.
Дополнительные переменные Х3, Х4 и Х5 равны разности между левой и правой частями ограничений и характеризуют недовыполнение данного ограничения (в данном случае излишний запас).
Задача решается в стандартных симплексных таблицах. Исходная таблица (см. табл. 6.1) заполняется коэффициентами модели.
| Базис | Х1 | Х2 | Х3 | Х4 | Х5 | а io | a io / a ip |
|---|---|---|---|---|---|---|---|
| Х3 | 2 | 3 | 1 | 0 | 0 | 60 | 20 |
| Х4 | 3 | 2 | 0 | 1 | 0 | 60 | 30 |
| Х5 | 4 | 20 | 0 | 0 | 1 | 200 | 10 |
| F | 4 | 3 | 0 | 0 | 0 | 0 |
Базисными переменными являются переменные, входящие только в одно уравнение, с коэффициентом +1. Базисным переменным соответствует единичный вектор-столбец. Базисные переменные равны свободным членам. Свободные переменные (переменные, не вошедшие в базис) равны нулю. Таким образом, Х1=0; Х2=0; Х3= 60; Х4= 60; Х5=200; F=0.
Данное решение является опорным, так как в столбце свободных членов нет отрицательных элементов.
В качестве разрешающего столбца выбирается любой столбец с отрицательной оценкой в строке целевой функции F. Выберем в данном случае в качестве разрешающего второй столбец. Для всех его элементов вычисляем симплексные отношения a io /a ip (отношение элемента столбца свободных членов к соответствующему элементу разрешающего столбца) и записываем их в последний столбец таблицы. Разрешающий элемент определяется минимальным симплексным отношением (в таблице он выделен жирным шрифтом). На месте разрешающего элемента ставится 1, а остальные элементы данного столбца равны нулю.
Остальные столбцы, соответствующие базисным переменным остаются без изменения. Столбец, соответствующий выводимой из базиса переменной, пересчитывается по общему правилу, описанному ниже. В данном случае Х2 вводится в базис вместо Х5 и столбец Х5 пересчитывается. Элементы разрешающей строки делятся на разрешающий элемент. Все остальные элементы таблицы пересчитываются по правилу прямоугольника. Пересчитываемый элемент образует с разрешающим элементом и соответствующими элементами разрешающей строки и столбца прямоугольник, изображенный на рисунке 6.2.
Рис. 6.2. Прямоугольник пересчета элементов симплексной таблицы
Пересчет производится по следующей формуле:
| (6.1) |
т.е. пересчитываемый элемент умножается на решающий элемент, минус элемент соответствующего разрешающего столбца, умноженный на соответствующий элемент разрешающей строки, и эта разность делится на разрешающий элемент. Или иначе: произведение элементов главной диагонали минус произведение элементов побочной диагонали, деленное на разрешающий элемент.
Например, пересчет элемента первого столбца первой строки:
| Базис | Х1 | Х2 | Х3 | Х4 | Х5 | а io | a io / a ip |
|---|---|---|---|---|---|---|---|
| Х3 | 1,4 | 0 | 1 | 0 | 0,15 | 30 | 21,4 |
| Х4 | 2,6 | 0 | 0 | 1 | 0,10 | 40 | 15,4 |
| Х2 | 0,2 | 1 | 0 | 0 | 0,05 | 10 | 50 |
| F | 3,4 | 0 | 0 | 0 | 0,150 | 300 |
Решение задачи на любой итерации читается следующим образом: базисные переменные равны свободным членам (предпоследний столбец в таблице) а свободные переменные (те, которые не входят в базис) равны нулю. В данном случае Х3 = 30; Х4 = 40; Х2 = 10; Х1 = Х5 = 0.
Или в краткой форме записи: Х1 = (0; 10; 30; 40; 0), F = 300.
Здесь значения переменных приводятся в порядке возрастания их индексов.
Технико-экономический анализ полученного решения
Выпускается десять единиц продукции второго вида (Х2 = 10). При этом ресурс второго вида останется в количестве тридцати единиц (Х3 = 30), ресурс первого вида останется в количестве сорока единиц (Х4 = 40), а ресурс третьего вида оказывается израсходованным полностью (Х5 = 0).
Проверка полученного решения: 2·0+3·10+30=60;
3·0+2·10+40=60;
4·0+20·10+0=200;
F=40·0+30·10=300.
Данное решение не является оптимальным, так как в строке целевой функции еще есть отрицательный элемент а 1F = 3,4.
Вторая и все последующие итерации выполняются аналогично.
| Базис | Х1 | Х2 | Х3 | Х4 | Х5 | а io | a io / a ip |
|---|---|---|---|---|---|---|---|
| Х3 | 0 | 0 | 1 | 0,54 | 0,1 | 8,5 | |
| Х1 | 1 | 0 | 0 | 0,38 | 0,04 | 15,4 | |
| Х2 | 0 | 1 | 0 | 0,74 | 0,17 | 6,9 | |
| F | 0 | 0 | 0 | 1,3 | 0,28 | 823 |
Х2=(15,4; 6,9; 8,5; 0; 0) → F=823.
Это решение оптимально, так как в строке целевой функции нет отрицательных оценок.
Технико-экономический анализ полученного решения
При имеющихся ресурсах следует выпустить 15,4 единицы (Х1=15,4) продукции первого вида и 6,9 единицы продукции второго вида (Х2=6,9). При этом ресурсы первого вида остаются в количестве 8,5 единицы (Х3=8,5), а ресурсы второго и третьего вида израсходованы полностью (Х4=Х5=0). Прибыль составит 823 у.е.
Проверка: 2·15,4+3·6,9+8,5=60;
3·15,4+2·6,9+0=60;
4·15,4+20·6,9+0=200;
F=40·15,4+30·6,9=823.
Сравнение полученных результатов с результатами графического метода подтверждает, что графический метод при всей своей наглядности не отличается достаточной точностью.
© ФГОУ ВПО Красноярский государственный аграрный университет
Видео:10. ФНП. Градиент и производная по направлению функции двух переменных.Скачать
ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Наиболее простым и наглядным методом решения задачи линейного программирования (ЗЛП) является графический метод. Он основан на геометрической интерпретации задачи линейного программирования и применяется при решении ЗЛП с двумя неизвестными:
Будем рассматривать решение этой задачи на плоскости. Каждое неравенство системы функциональных ограничений геометрически определяет полуплоскость с граничной прямой апх, + + aj2х2 = bn i = 1, т. Условия неотрицательности определяют полуплоскости с граничными прямыми х <= 0, х2 = 0 соответственно. Если система совместна, то полуплоскости, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек; координаты каждой из этих точек являются решением данной системы. Совокупность этих точек называют многоугольником решений. Он может быть точкой, отрезком, лучом, ограниченным и неограниченным многоугольником.
Геометрически ЗЛП представляет собой отыскание такой угловой точки многоугольника решений, координаты которой доставляют максимальное (минимальное) значение линейной целевой функции, причем допустимыми решениями являются все точки многоугольника решений.
Линейное уравнение описывает множество точек, лежащих на одной прямой. Линейное неравенство описывает некоторую область на плоскости.
Определим, какую часть плоскости описывает неравенство 2х <+ Зх2 0, j = 1, п). Координаты любой точки, принадлежащей области определения, являются допустимым решением задачи.
Для нахождения экстремального значения целевой функции при графическом решении ЗЛП используют вектор-градиент, координаты которого являются частными производными целевой функции:
Этот вектор показывает направление наискорейшего изменения целевой функции. Прямая c[xl + с2х2 = f(x0), перпендикулярная вектору-градиенту, является линией уровня целевой функции (рис. 2.2.2). В любой точке линии уровня целевая функция принимает одно и то же значение. Приравняем целевую функцию постоянной величине а. Меняя значение а, получим семейство параллельных прямых, каждая из которых является линией уровня целевой функции.
Рис. 2.2.2. Вектор-градиент и линии уровня
Важное свойство линии уровня линейной функции состоит в том, что при параллельном смещении линии в одну сторону уровень только возрастает, а при смещении в д р у г у ю сторону — только убывает.
Графический метод решения ЗЛП состоит из четырех этапов:
- 1. Строится область допустимых решений (ОДР) ЗЛП.
- 2. Строится вектор-градиент целевой функции (ЦФ) с началом в точке х0 (0; 0): V = (с,, с2).
- 3. Линия уровня CjXj + с2х2 = а (а — постоянная величина) — прямая, перпендикулярная вектору-градиенту V, — передвигается в направлении вектора-градиента в случае максимизации целевой функции f(xv х2) до тех пор, пока не покинет пределов ОДР. При минимизации /(*,, х2) линия уровня перемещается в направлении, противоположном вектору-градиенту. Крайняя точка (или точки) ОДР при этом движении и является точкой максимума (минимума) f(xpjc2).
Если прямая, соответствующая линии уровня, при своем движении не покидает ОДР, то минимума (максимума) функции f(xр х2) не существует.
Если линия уровня целевой функции параллельна функциональному ограничению задачи, на котором достигается оптимальное значение ЦФ, то оптимальное значение ЦФ будет достигаться в любой точке этого ограничения, лежащей между двумя оптимальными угловыми точками, и, соответственно, любая из этих точек является оптимальным решением ЗЛП.
4. Определяются координаты точки максимума (минимума). Для этого достаточно решить систему уравнений прямых, дающих в пересечении точку максимума (минимума). Значение f(x<, х2), найденное в полученной точке, является максимальным (минимальным) значением целевой функции.
Возможные ситуации графического решения ЗЛП представлены в табл. 2.2.1.
Видео:ГрадиентСкачать
Вектор градиента целевой функции
Видео:Векторы. Метод координат. Вебинар | МатематикаСкачать
Вектор градиента целевой функции
Графический метод характеризуется простотой и наглядностью, однако он недостаточно точен и применим только для задач с не более чем тремя переменными. Последнее обусловлено тем, что человек, живущий в трехмерном пространстве, практически не способен представить себе визуально пространство более высокого порядка.
Метод основан на том, что каждое ограничение неравенство отсекает в n -мерном пространстве n -мерную полуплоскость (в данной курсовой работе это двухмерное пространство (плоскость) и простая полуплоскость). Совокупность этих полуплоскостей (если ограничения совместны) образует n -мерный многогранник допустимых решений. Оптимальное решение достигается в одной из вершин многогранника. Для определения этой вершины необходимо построить поверхность уровня целевой функции (в курсовом проекте линию уровня). Затем следует перемещать эту поверхность (линию) в направлении градиента до крайней точки области допустимых решений (ОДР).
Рассмотрим следующий простой пример решения задачи линейного программирования (ЗЛП) графическим методом.
Математическая модель: 2Х1+3Х2≤60;
3Х1+2Х2≤60;
4Х1+20Х2≤200;
Х1≥0; Х2≥0;
F=40Х1+30Х2→Мах.
Перейдем от неравенств к равенствам: 2Х1+3Х2=60;
3Х1+2Х2=60;
4Х1+20Х2=200.
Это уравнения прямых линий, которые могут быть легко построены по двум точкам:
для первого ограничения Х1=0; Х2=20;
Х2=0; Х1=30.
для второго ограничения Х1=0; Х2=30;
Х2=0; Х1=20.
для третьего ограничения Х1=0; Х2=10;
Х2=0; Х1=50.
Градиент целевой функции это вектор, характеризующий направление и скорость изменения функции (в данном случае целевой функции). Он определяется ее частными производными по каждой переменной:
Линия уровня целевой функции перпендикулярна градиенту.
Графическое решение данной задачи приведено на рисунке 6.1.
Рис. 6.1. Графическое решение задачи
Область допустимых решений (ОДР) в данном случае образуется четырехугольником ОВСД. Ни одна точка внутри его или на его границе не противоречит ни одному из ограничений. Оптимальное решение находится в одной из вершин четырехугольника. Для нахождения оптимального решения перемещаем линию уровня целевой функции в направлении градиента до крайней точки ОДР. Такой точкой является точка С с координатами: Х1=16; Х2=8. Значение целевой функции F=40×16+30×8=880. Очевидно, что это решение не отличается высокой точностью, что характерно для графического метода.
Из рисунка видно, что ресурсы второго и третьего видов использованы полностью, а ресурс первого вида оказался в избытке. Для количественной оценки этого избытка определим сначала расход данного ресурса: 2×16+3×8=56. Запас равен 60, тогда остаток составит 6056=4.
6.1.2. Симплексный метод решения
задач линейного программирования
В отличие от графического метода, симплексный метод абсолютно точен. Кроме того, он дает возможность для точной количественной оценки излишков имеющихся ресурсов, а применение двойственного симплекс-метода дает еще и большие возможности для технико-экономического анализа полученного решения с целью выработки обоснованных рекомендаций по улучшению условий функционирования системы.
Приведем задачу, рассмотренную в предыдущем разделе, к канонической форме: 2Х1+3Х2+Х3=60;
3Х1+2Х2+Х4=60;
4Х1+20Х2+Х5=200;
F-40Х1 -30Х2 =0.
Дополнительные переменные Х3, Х4 и Х5 равны разности между левой и правой частями ограничений и характеризуют недовыполнение данного ограничения (в данном случае излишний запас).
Задача решается в стандартных симплексных таблицах. Исходная таблица (см. табл. 6.1) заполняется коэффициентами модели.
| Базис | Х1 | Х2 | Х3 | Х4 | Х5 | а io | a io / a ip |
|---|---|---|---|---|---|---|---|
| Х3 | 2 | 3 | 1 | 0 | 0 | 60 | 20 |
| Х4 | 3 | 2 | 0 | 1 | 0 | 60 | 30 |
| Х5 | 4 | 20 | 0 | 0 | 1 | 200 | 10 |
| F | 4 | 3 | 0 | 0 | 0 | 0 |
Базисными переменными являются переменные, входящие только в одно уравнение, с коэффициентом +1. Базисным переменным соответствует единичный вектор-столбец. Базисные переменные равны свободным членам. Свободные переменные (переменные, не вошедшие в базис) равны нулю. Таким образом, Х1=0; Х2=0; Х3= 60; Х4= 60; Х5=200; F=0.
Данное решение является опорным, так как в столбце свободных членов нет отрицательных элементов.
В качестве разрешающего столбца выбирается любой столбец с отрицательной оценкой в строке целевой функции F. Выберем в данном случае в качестве разрешающего второй столбец. Для всех его элементов вычисляем симплексные отношения a io /a ip (отношение элемента столбца свободных членов к соответствующему элементу разрешающего столбца) и записываем их в последний столбец таблицы. Разрешающий элемент определяется минимальным симплексным отношением (в таблице он выделен жирным шрифтом). На месте разрешающего элемента ставится 1, а остальные элементы данного столбца равны нулю.
Остальные столбцы, соответствующие базисным переменным остаются без изменения. Столбец, соответствующий выводимой из базиса переменной, пересчитывается по общему правилу, описанному ниже. В данном случае Х2 вводится в базис вместо Х5 и столбец Х5 пересчитывается. Элементы разрешающей строки делятся на разрешающий элемент. Все остальные элементы таблицы пересчитываются по правилу прямоугольника. Пересчитываемый элемент образует с разрешающим элементом и соответствующими элементами разрешающей строки и столбца прямоугольник, изображенный на рисунке 6.2.
Рис. 6.2. Прямоугольник пересчета элементов симплексной таблицы
Пересчет производится по следующей формуле:
| (6.1) |
т.е. пересчитываемый элемент умножается на решающий элемент, минус элемент соответствующего разрешающего столбца, умноженный на соответствующий элемент разрешающей строки, и эта разность делится на разрешающий элемент. Или иначе: произведение элементов главной диагонали минус произведение элементов побочной диагонали, деленное на разрешающий элемент.
Например, пересчет элемента первого столбца первой строки:
| Базис | Х1 | Х2 | Х3 | Х4 | Х5 | а io | a io / a ip |
|---|---|---|---|---|---|---|---|
| Х3 | 1,4 | 0 | 1 | 0 | 0,15 | 30 | 21,4 |
| Х4 | 2,6 | 0 | 0 | 1 | 0,10 | 40 | 15,4 |
| Х2 | 0,2 | 1 | 0 | 0 | 0,05 | 10 | 50 |
| F | 3,4 | 0 | 0 | 0 | 0,150 | 300 |
Решение задачи на любой итерации читается следующим образом: базисные переменные равны свободным членам (предпоследний столбец в таблице) а свободные переменные (те, которые не входят в базис) равны нулю. В данном случае Х3 = 30; Х4 = 40; Х2 = 10; Х1 = Х5 = 0.
Или в краткой форме записи: Х1 = (0; 10; 30; 40; 0), F = 300.
Здесь значения переменных приводятся в порядке возрастания их индексов.
Технико-экономический анализ полученного решения
Выпускается десять единиц продукции второго вида (Х2 = 10). При этом ресурс второго вида останется в количестве тридцати единиц (Х3 = 30), ресурс первого вида останется в количестве сорока единиц (Х4 = 40), а ресурс третьего вида оказывается израсходованным полностью (Х5 = 0).
Проверка полученного решения: 2·0+3·10+30=60;
3·0+2·10+40=60;
4·0+20·10+0=200;
F=40·0+30·10=300.
Данное решение не является оптимальным, так как в строке целевой функции еще есть отрицательный элемент а 1F = 3,4.
Вторая и все последующие итерации выполняются аналогично.
| Базис | Х1 | Х2 | Х3 | Х4 | Х5 | а io | a io / a ip |
|---|---|---|---|---|---|---|---|
| Х3 | 0 | 0 | 1 | 0,54 | 0,1 | 8,5 | |
| Х1 | 1 | 0 | 0 | 0,38 | 0,04 | 15,4 | |
| Х2 | 0 | 1 | 0 | 0,74 | 0,17 | 6,9 | |
| F | 0 | 0 | 0 | 1,3 | 0,28 | 823 |
Х2=(15,4; 6,9; 8,5; 0; 0) → F=823.
Это решение оптимально, так как в строке целевой функции нет отрицательных оценок.
Технико-экономический анализ полученного решения
При имеющихся ресурсах следует выпустить 15,4 единицы (Х1=15,4) продукции первого вида и 6,9 единицы продукции второго вида (Х2=6,9). При этом ресурсы первого вида остаются в количестве 8,5 единицы (Х3=8,5), а ресурсы второго и третьего вида израсходованы полностью (Х4=Х5=0). Прибыль составит 823 у.е.
Проверка: 2·15,4+3·6,9+8,5=60;
3·15,4+2·6,9+0=60;
4·15,4+20·6,9+0=200;
F=40·15,4+30·6,9=823.
Сравнение полученных результатов с результатами графического метода подтверждает, что графический метод при всей своей наглядности не отличается достаточной точностью.
© ФГОУ ВПО Красноярский государственный аграрный университет
Видео:Нахождение градиента функции в точкеСкачать
ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Наиболее простым и наглядным методом решения задачи линейного программирования (ЗЛП) является графический метод. Он основан на геометрической интерпретации задачи линейного программирования и применяется при решении ЗЛП с двумя неизвестными:
🔥 Видео
Вектор-градиент (теория)Скачать
Графический метод решения задачи линейного программирования (ЗЛП)Скачать
Математика без Ху!ни. Частные производные функции нескольких переменных. Градиент.Скачать
Оператор набла (оператор Гамильтона) и оператор ЛапласаСкачать
#12. L1-регуляризатор. Отличия между L1- и L2-регуляризаторами | Машинное обучениеСкачать
Метод покоординатного спускаСкачать
Вектор. Сложение и вычитание. 9 класс | МатематикаСкачать
Графический метод для задачи с n переменными.Скачать
Графический метод решения задач линейного программирования | Высшая математика TutorOnlineСкачать
ГрадиентСкачать
18+ Математика без Ху!ни. Скалярное произведение векторов. Угол между векторами.Скачать
Стереометрия с нуля до уровня ЕГЭ. Координатно-векторный метод. Задачи на доказательствоСкачать
Векторная функция одного и нескольких переменных. Градиент | 37 | Константин Правдин | ИТМОСкачать
Градиенты и частные производныеСкачать
Градиентный метод | метод скорейшего спуска + примерСкачать
Математика без Ху!ни. Экстремум функции 2х переменных.Скачать
