Решение задач линейного программирования симплексным методом

 
 

Содержание 

1. Решение задачи линейного программирования                                                графическим способом
2. Решение задачи линейного программирования                                                                                                           симплексным методом
3. Решение задачи линейного программирования                                                                                           симплексным методом с искусственным базисом
4. Решение двойственных задач
5. Анализ двойственных задач

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1. Решение задачи линейного  программирования графическим  способом

 

Задание: графическим методом найти максимальное и минимальное значение целевой функции:    Z=3X₁+5X₂,

При ограничениях:

6Х₁+4Х₂≤20000

2Х₁+4Х₂≥8000

Х₁≥1000, Х₂≥1500 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Выполнение  работы

   Основные  переменные: Х₁ и Х₂

   Основные  ограничения: 1) Х₁≥1000

                                             2) Х₂≥1500

                                             3) 6Х₁+4Х₂≤20000

                                             4) 2Х₁+4Х₂≥8000

   Функция цели:                 Z=3X₁+5X₂    

   1 способ: 

   1) Х₁≥1000 

   2) Х₂≥1500 

   3) 6Х₁+4Х₂≤20000

       Х₁=0           Х₂=5000

       Х₁=3333,3  Х₂=0 

   4) 2Х₁+4Х₂≥8000

       Х₁=0        Х₂=2000

       Х₁=4000  Х₂=0  

   В данной задаче только две основные переменные, что позволяет дать ее наглядное геометрическое представление (рис. 1), в нем используется декартовая система координат, осям которой соответствуют переменные Х₁ и Х₂.

   Рисунок 1 показывает, что областью допустимых значений, характерной для данной задачи, является треугольник АВС. Любая совокупность переменных, которая находиться в ОДЗ является решением системы уравнений. 

   Координаты  вершин треугольника АВС определяют по рисунку 1. 

   т. А    Х₁=1000     Х₂=1500

   т. В    Х₁=2330     Х₂=1500

   т. С    Х₁=1000     Х₂=3500 

   Затем находим значение целевой функции  для каждой точки:

   т. А     Z=3*1000+5*1500=10500

   т. В     Z=3*2330+5*1500=14490

   т. С     Z=3*1000+5*3500=20500

   таким образом, минимальное значение целевой  функции (10500) находится      в т. А, а максимальное (20500) находится в т. С. 
 
 
 
 
 
 

   2 способ: 

   Пусть функция цели будет равна 25000

                             Z=3Х₁+5Х₂=25000

   Найдем  координаты:

                           Х₁=0             Х₂=5000

                           Х₁=8333,3    Х₂=0

   Граничная прямая для функции цели изображается на рисунке 1. перемещая прямую функции  цели (Z) параллельно самой себе, определяем точки экстремума: т. С – точка максимума, т. А – точка минимума. 

   Чтобы убедиться окончательно в правильности нахождения максимального и минимального значений целевой функции Z=3Х₁+5Х₂, необходимо выполнить проверку для определения точек экстремума (т. А и т. С), используя исходные ограничения 

   Поверка т. А (Х₁=1000; Х₂=1500)

   1) Х₁≥1000

       1000=1000

   2) Х₂≥1500

       1500=1500

   3) 6Х₁+4Х₂≤20000

       6*1000+4*1500≤20000

       12000<20000

   4) 2Х₁+4Х₂≥8000

       2*1000+4*1500≥8000

       8000=8000 

   Все ограничения  для точки А соблюдены. 

   Проверка  т. С (Х₁=1000; Х₂=3500)

    1) Х₁≥1000

       1000=1000

   2) Х₂≥1500

       3500>1500

   3) 6Х₁+4Х₂≤20000

       6*1000+4*3500≤20000

       20000=20000

   4) 2Х₁+4Х₂≥8000

       2*1000+4*3500≥8000

       16000>8000 

   Все ограничения  для точки С соблюдены. 

   Ответ: максимальное значение функции цели находится в точке С, минимальное значение находится в точке А. 
 
 

   2 Решение задачи линейного программирования симплексным методом

    

   Задание: решить симплексным методом

   5Х₁-3Х₂-7Х₃+15Х₄→max 

   При следующих ограничениях

   2Х₁-3Х₂+8Х₃+5Х₄≤14

   -2Х₁+5Х₂+Х₃ ≤5

   2Х₂+2Х₂-3Х₄≤6

   2Х₁-Х₂+3Х₃≤5 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

   Выполнение  работы 

   Симплексный метод является универсальным, он позволяет  находить оптимальное решение большого количества любых задач линейного программирования.

   На  первом этапе решения задачи симплексным  методом выписываются существующие ограничения и функция цели.

   1) 2Х₁-3Х₂+8Х₃+5Х₄≤14

   2)-2Х₁+5Х₂+Х₃ ≤5

   3)2Х₂+2Х₂-3Х₄≤6

   4)2Х₁-Х₂+3Х₃≤5 
 

    Z= 5Х₁-3Х₂-7Х₃+15Х₄→max 
 

   На  первой стадии второго этапа приводят задачу к канонической форме:

   1) 2Х₁-3Х₂+8Х₃+5Х₄+S1=14

   2)-2Х₁+5Х₂+Х₃ +S2=5

   3)2Х₂+2Х₂-3Х₄+S3=6

   4)2Х₁-Х₂+3Х₃+S4=5 

   Z= 5Х₁-3Х₂-7Х₃+15Х₄+0*S₁+0*S₂+0*S₃+0*S₄→max 

   Далее находят количество небазисных переменных как разность количества переменных (n) и количества ограничений (m).

   В данном случае, n=8 (Х₁; Х₂; Х₃; Х₄;S1; S₂; S₃; S₄) и m=4. Следовательно, количество небазисных переменных равно четырем.

   Формальным  признаком оптимальности плана  является содержание индексной строки. Данная задача решается на определение максимума, поэтому план будет оптимальным, когда в индексной строке будут отсутствовать отрицательные коэффициенты.

   В первую симплексную таблицу записываются числовые значения, взятые из ограничений  и функции цели (таблица 1).

   В индексной  строке при условии максимума  по абсолютной величине число (- ) среди  отрицательных коэффициентов. Этот коэффициент означает главный столбец – k.

   Далее определяют, какую базисную переменную необходимо вывести из плана. Это определяют через симплексное отношение, то есть через отношение свободных членов базиса на соответствующие коэффициенты главного столбца (таблица 1, столбец   ).

   Выбирается  наименьшее положительное неравное нулю симплексное отношение (). Эта строка является главной – l (таблица 1).

   Затем определяют главный элемент (а_kl) на пересечении главного столбца с главной строкой. 
 
 
 
 

   Вторая  симплексная таблица заполняется следующим образом:

1. Заполняются коэффициенты главной строки как отношение старых элементов к главному элементу:

   2.       Заполняются коэффициенты по  старому главному столбцу. Применяется      процедура на основе системы Гаусса, где все элементы принимаются за нуль.

   3.       Все прочие элемен6ты заполняются  по правилу прямоугольника –  берем главный элемент и бывшее значение и через эти две строим прямоугольник. От старого значения отнимаем дробь, где в знаменателе показатель главного элемента, а в числителе произведение не задействованных элементов противоположных углов прямоугольника. 

   

 

Расчет по столбцу 3               Расчет по столбцу 4            Расчет по столбцу 5   

                                      -                                                                                                                                                  

                                                             

                                                                

                                                 

                            

Расчет  по столбцу 6              Расчет по столбцу 8             Расчет по столбцу 9

                                                                    
 
 
 
 
 
 

   Расчет  по столбцу 10         Расчет по столбцу 11  

                                    

   Аналогично  рассчитывается третья симплексная таблица.

   Таблица 1

   Первая  симплексная таблица