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

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

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

линейный программирование оптимальность симплексный

Исходные данные:

Графическим методом найти max и min значение целевой функции:

= 2Х₁ + 6Х₂

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

.5X₁ + 4X₂ ≥ 5000₁ + 3X₂ ≤ 8000

.7X₁ - 1.5X₂ ≥ 90

Х₁ ≥ 0 Х₂ ≥ 200

Алгоритм решения:

.        Каждое из неравенств считается уравнением, для каждого строится прямая;

.        Находится полуплоскость области допустимых значений (ОДЗ) для каждой из прямой;

.        Находится область допустимых значений из прямой;

. Определяется значение целевой функции Z, для этого:

.1. Определяется экстремальная точка ОДЗ;

.2. Находится значение координат x₁; x₂.

Решаем неравенства, приравняв их к значению после знака ≥ или ≤.

)        1.5X₁ + 4X₂ = 5000₁=0=>4X₂=5000₂=1250 (0; 1250)₂=0=>1.5X₁=5000₁=3333 (3333; 0)

)        X₁ + 3X₂ = 8000₁=0=>3X₂=8000₂=2667 (0; 2667)₂=0=> X₁=8000 (8000; 0)

)        5.7X₁-1.5X₂ = 90₁=0=>-1.5X₂=90₂=-60 (0; - 60)₂=0=>5.7X₁=90₁=16 (16; 0)

)        Х₁ = 0

)        Х₂ = 200

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

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

Проведем проверку, для этого подставим координаты любой точки (возьмем точку K) из ОДЗ и подставим ее в каждое неравенство:

К (2000; 1000)

) 1.5*2000+4*1000≥5000

≥5000 условие верно

) 2000+3*1000≤8000

≤8000 условие верно

) 5.7*2000-1.5*1000≥ 90

≥ 90 условие верно

) 2000≥0 условие верно

) 1000≥200 условие верно

Построим прямую, соответствующую целевой функции Z = 2Х₁ + 6Х₂→max, для чего приравняем ее к 0.

Х₁ + 6Х₂=0₁=0=>X₂=0 (0; 0)₁=1=>Х₂=-0.3 (1; 0.3)

Для проверки, приравняем целевую функцию к 5.

=5

Х₁ + 6Х₂=5₁=0=>X₂=0.8 (0; 0.8)₁=5=> Х₂=-0.8 (5; 0.8)

Целевые функции между собой должны быть параллельны.

Как видно на графике, условие параллельности соблюдено.

В многоугольнике CDEF находим максимальную точку, которая совпадает с целевой функцией.

Целевой функции Z = 2Х₁ + 6Х₂ соответствует семейство параллельных прямых с разным значениями Z. При движении в одну сторону Z увеличивается, в другую - уменьшается. Так как начальная координата Z=0, а нам нужно найти Z_max, то перемещаем ее параллельно вверх до тех пор, пока она не выйдет за пределы многоугольника CDEF.

Последней точкой, с которой совпадает прямая Z, стала точка D.

Найдем координаты точки D, решив систему уравнений.

 ₁=7400

Подставим полученные координаты точки в целевую функцию Z.

Координаты точки D (7400; 200)

Подставим координаты точки D в целевую функцию._max = 2*7400+6*200=16000

Далее по условию задачи требуется найти минимальное значение целевой функции.

= 2Х₁ + 6Х₂→min

Точка C является минимальной, найдем ее координаты, решив систему уравнений.

=5000

=5000-800

=4200/1,5

=2800

Точка С имеет координаты С (2800; 200)

Подставим координаты в целевую функцию._min=2*2800+6*200=6800

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

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

Такие задачи содержат много переменных и ограничений. ОДЗ этих задач представляет собой многогранник (симплекс).

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

Исходные данные (вариант 10):

Решить симплексным методом:

Х₁ + 40Х₂ - Х₃ → max.

Х₁ + Х₂ ≤ 30

Х₁ - 0,4Х₃ ≤ 0

,1Х₁ + 2Х₂ - 10Х₃ ≤1800

Х₁ + Х₃ ≤ 100

Х₂≤45

математическая формулировка задачи;

приведение неравенств к канонической форме;

нахождение первого базисного плана, соответствующего одной из вершин выпуклого многогранника;

проверка плана на оптимальность;

последовательное улучшение плана для получения оптимального;

проверка решения.

Сначала необходимо определить основные (Х₁, Х₂, Х₃) и дополнительные (S₁, S₂, S₃, S₄) переменные.

К канонической форме системы неравенств приводятся путем введения дополнительных переменных. Если задача задана в виде линейных неравенств, она называется стандартной, если в виде уравнений - канонической. Если в неравенстве тип ограничений ≤, дополнительная переменная вводится со знаком +. Если в неравенстве тип ограничения ≥, дополнительная переменная вводится со знаком -.

В уравнение целевой функции также вводятся дополнительные переменные.

Х₁ + Х₂ +S₁= 30

Х₁ - 0,4Х₃+ S₂ = 0

,1Х₁ + 2Х₂ - 10Х₃+ S₃ =1800

Х₁ + Х₃ + S₄ = 100

Х₂+ S₅ = 45=18Х₁ + 40Х₂ - Х₃ + 0S₁+ 0S₂+ 0S₃+ 0S₄+ 0S₅=> max

Предполагаем, что основные переменные равны «0», следовательно:

S₁ = 30₂ = 0₃ = 1800     Z = 18X₁+40Х₂ - Х₃+0S₁+ 0S₂+ 0S₃+ 0S₄+ 0S₅ =0

S₄ = 100₅=45

Нахождение первого базисного плана, соответствующего одной из вершин многогранника, отражено в таблице 1.

Таблица 1 - Первый базисный план

Проверка плана на оптимальность.

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

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

Данный базисный план не оптимальный, поэтому требует улучшения.

Последовательное улучшение плана до оптимального.

Для улучшения необходимо определить переменную, которая позволить приблизить план к точке экстремума, то есть выбрать главный столбец. В индексной строке при условиях максимума выбирается максимальное по абсолютной величине число среди отрицательных коэффициентов. В нашем случае главный столбец при переменной Х₂ (в таблице выделен). Значит переменная Х₂ должна войти в базис.

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

Симплексное отношение - отношение свободных членов базисов на соответствующие коэффициенты главного столбца.

Выбирается наименьшее положительное не равное 0 симплексное отношение. Это главная строка или узкое место (в таблице выделено).

Симплексное отношение: 30: 1 = 30 - главная строка

: 2 = 900

: 1 = 45

Следовательно, переменная Х₂ должна войти в базис на место дополнительной переменной S₁. Пересечение главной строки с главным столбцом указывает главный элемент.

Рассчитываем коэффициенты строки, которая в предыдущей таблице была главной, делением старого значения на главный элемент.

_ijH = a_jlC / a_kl (1)

:1=1

:1=1

Изменяем главный столбец, превращая его в нулевой вектор столбец.

Все остальные коэффициенты рассчитываются по правилу прямоугольника, включая элементы строки целевой функции.

_ijH = a_ijC - a_ljC * a_kiC / a_kl (2)

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

Таблица 2 - Оптимальный базисный план

Полученный базисный план оптимальный, так как в индексной строке отсутствуют отрицательные коэффициенты.

Ответ: Х₂ =30₂=0

S₃=1740₄=100₅=15

Z=1200

Переменные X₁, X₃ и S₁ не вошли в базисный план.

Проверка подразумевает подстановку полученного плана во все уравнения:

)        0 + 30 + 0 = 30   30=30

)        0 - 0,4*0+0 = 0   0=0

)        2,1*0+2*30-10*0+1740=1800                  1800=1800

)        0+0+100=100      100=100

)        30+15=45  45=45

)        Z=18*0+40*30-0=1200                   1200=1200

3. Анализ и корректировка результатов решения задач линейного программирования симплексным методом

) Анализ показателей последней симплексной таблицы;

) Анализ последней индексной строки;

) Использование коэффициентов замещения последней симплексной таблицы.

1) Экономический анализ-это последний этап математического моделирования, он основан на использовании коэффициентов последней симплексной таблицы и двойственных оценок.

Необходимость проведения анализа вызвана рядом обстоятельств:

·        Модель не может быть полным аналогом процессов;

·        Необходимость изменения, вызвана действием случайных факторов.

В результате решения получены 5 базисные переменные: 1 из них основная (Х2) и 4 дополнительные (S2, S3, S4, S5). В оптимальный план вошли Х2=30.

Отсутствие в базисе основных переменных Х1 и X3 говорит о том, что они равны 0.

Отсутствие в базисе дополнительной переменной S1 говорит о том, что ресурс S1 использован полностью.

Частично недоиспользованы S2=0; S3=1740; S4=100; S5=15, т. к. данная переменная находится в базисном плане.

Оптимальный план обеспечивает наибольший размер прибыли Z= 1200; любые изменения приведут к уменьшению прибыли.

Z=18Х₁ + 40Х₂ - Х₃ + 0S₁+ 0S₂+ 0S₃+ 0S₄+ 0S₅=> max

Z=18*0+40*30-0=1200→ max

Анализ последней индексной строки

Анализ последней индексной строки под основные переменные Х1, Х2, Х3 - показывает на какую величину должна измениться целевая функция, чтобы переменная вошла в базис.

Коэффициенты индексной строки по столбцу Х1 (22) показывает на сколько уменьшится целевая функция при введении в план единицы.

Мы предполагаем, что Х1=1, тогда функция цели Z должна уменьшится на 22.= 1200-22=1178

Анализ индексной строки под дополнительные переменные.

Двойственные оценки - коэффициенты, полученные в индексной строке под дополнительные переменные. Единицы измерения двойственных оценок одинаковые, что и функция цели.

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

Двойственная оценка ровна нулю, если ресурс находится в избытке (S2, S3, S4, S5), оценка так же может быть положительной и отрицательной.

Коэффициенты индексной строки под дополнительными переменными (S1) показывают на сколько изменится целевая функция (Z) при изменении ресурса на 1. В нашем примере дефицит наблюдается только у ресурса S1 (40).

Если S1 увеличить на 1 (30+1=31), то функция цели увеличится на величину двойственной оценки 40 и будет составлять: Z= 1200+40 = 1240

Свойства двойственных оценок (ДО):

Первое свойство ДО связано с мерой дефицитности ресурса;

Второе свойство - устойчивость оценок;

Третье свойство связано с мерой влияния ограничения на функционал;

Четвертое свойство относится к взаимозаменяемости ресурсов или продуктов;

Пятое свойство связано с мерой рентабельности отдельных способов (производств);

Шестое свойство связано с определением оптимальности плана.

Использование коэффициентов замещения последней симплексной таблицы.

Последняя симплексная таблица необходима для анализа и корректировки полученного оптимального решения. С помощью нее можно не пересчитывая всей задачи откорректировать оптимальный план. Анализ и корректировка полученного оптимального решения с использованием коэффициентов замещения проводится в целях:

Определения возможных последствий при изменении параметром модели;

Оценка устойчивости оптимального плана к изменению отдельных параметров;

Получение нового варианта без решений.

Коэффициенты замещения при основных переменных не вошедших в базисный план показывают на сколько изменятся значения соответствующих базисных переменных при введении в базис основных небазисных переменных с единичной интенсивностью. Коэффициент замещения со знаком «-» показывает увеличение базиса, а со знаком «+» уменьшение.

В моем примере, на S=30 занять 1 под Х1.

Х1=1; Х2=29; Х3=0

+29=30

Коэффициент замещения по столбцу Х1: +1 показывает, что S↓ на 1

(Х2 = 30-1 = 29)

Коэффициент замещения +1 показывает, что объём недоиспользованных ресурсов S2 ↓ на 1 (S2= 0-1 = -1)

Коэффициент замещения +0,1 показывает, что объём недоиспользованных ресурсов S3 ↓ на 0,1 (S3= 1740-0,1 = 1739,9)

Коэффициент замещения +1 показывает, что объём недоиспользованных ресурсов S4 ↓ на 1 (S4= 100-1 = 99)

Коэффициент замещения -1 показывает, что объём недоиспользованных ресурсов S5 ↑ на 1 (S5= 15+1 = 16)

Коэффициенты замещения при дополнительных переменных показывают

А) В случаях ↑ объема ресурсов «+» коэффициенты показывают ↑ переменных, а «-» - показывает ↓;

Б) В случаях ↓ объема ресурсов наоборот «+» коэффициенты показывают ↓,

а «-» показывают ↑.

Так как более дефицитным является ресурс S1, то дополнительные переменные увеличиваем на 1 (S1=30+1=31)

Х2=30; S2=0; S3=1740; S4=100; S5=15

Коэффициент замещения +1 показывает, что Х2 ↑ на 1 и будет Х2= 30+1=31

Коэффициент замещения 0 показывает, что S2 не изменится

Коэффициент замещения -2 показывает, что S3 ↓ на 2 и будет S3=1740-2=1738

Коэффициент замещения 0 показывает, что S4 не изменится

Коэффициент замещения -1 показывает, что S5 ↓ на 1 и будет S5=15-1=14=1200+40=1240.