Линейное программирование

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

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

Задание:

Дана математическая модель задачи ЛП:

F = x1 + kx2 → min

x1 + 3x2 <= 6- kx2 >=11 + x2 >= 5

x1 - 2x2 <= 4k

x1 >= 0, x2 >=0

k= 1 + = 1,23

Требуется найти решение задачи:

) графическим методом

) симплекс методом

. Графическим методом

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

Задана целевая функция

F = 1,63x1 + 1,23 x2 → min

И система ограничений

x1 + 3x2 <= 6

x1 - 1,23x2 >=1

,23 x1 + x2 >= 5

x1 - 2x2 <= 4,92

x1 >= 0, x2 >=0

Очевидно, что при данной постановке задачи допустимое множество X в плоскости (x1, x2) представляет собой многоугольник (не обязательно замкнутый), образованный пересечением полуплоскостей, соответствующих ограничениям вида ai1x1 + ai2x2 ≤ bi в исходной задаче. Линии уровня функции f(x) = (c, x) образуют семейство параллельных прямых.

При этом grad f(x) = c, т.е. градиент целевой функции всюду одинаков и является нормалью каждой из данных полуплоскостей.

Поиск решения задачи сводится к нахождению максимального числа α* среди всех таких α, что полуплоскость Hcα имеет непустое пересечение с X.

Построим график по точкам

. -2x1 + 3x2 - 6 = 0

x2 =

2. x1 - 1,23x2 -1=0

-1,23x2 = -x1 +1

Мы получаем 4 точки A , B , C, D принадлежащие области.

Найдем точные координаты точек. A (4,06;0)

B (4,92;0 )

C (19,2;14,8)

D (2,86;1,5)

Подставим точки в функцию

FA = 1,63 ∙ 4,06+ 1,23 ∙ 0 = 6,62

FB = 1,63 ∙ 4,92= 8,02

Fc = 1,63 ∙19,3+ 1,23 ∙ 4,8=37,4

FD = 1,63 ∙ 2,86 + 1,23 ∙ 1,5 = 6,55

Вывод: минимум функции существует в точке D (2,86;1,5) и FD равен 6,55.

. Симплексный метод

Задана целевая функция

F = 1,63x1 + 1,23 x2 → min и система ограничений

x1 + 3x2 <= 6

x1 - 1,23 x2 >=1

,23 x1 + x2 >= 5

x1 - 2x2 <= 4,92

x1 >= 0, x2 >=0

Введем искусственный базис x3, x4, x5, x6

-2x1 + 3x2 + x3 <= 6

x1 - 1,23 x2 + x4=1

,23 x1 + x2 + x5= 5

x1 - 2x2 +x6 <= 4,92

Добавим балансные переменные z1, z2

x1 + 3x2 + x3 - z1= 6

x1 - 1,23 x2 + x4=1

,23 x1 + x2 + x5= 5- 2x2 +x6 - z2= 4,92

0 = z -1,63x1 - 1,23x2

Задача приведена к каноническому виду, составим симплекс-таблицу.

Таблица 1.1 - Первое приближение