Вопрос 25

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

a₁₁x₁+ a₁₂x₂≤b₁

a₂₁x₁+ a₂₂x₂≤b₂

a_m1x₁+ a_m2x₂≤b_m (м.б. ≥,=)

x₁,x₂≥0

Целевая функция F(x₁,x₂)=c₁x₁+c₂x₂. Необходимо изобразить область на плоскости, удовлетворяющую системе ограничений. Графиком уравнения с двумя переменными является прямая. График неравенства – полуплоскость, лежащая ниже прямой, если знак ≤, и выше прямой, если знак ≥. В результате получится выпуклый многоугольник. Его вершины – допустимые решения, одна из них даст оптимальное решение. Для нахождения оптимального решения надо: строят вектор градиента к множеству параллельных прямых c₁x₁+c₂x₂=с (с-параметр) grad F – это нормальный вектор, т.е. grad F=(a₁,c₂). Строится множество прямых этого множества, двигаясь по направлению вектора градиента найдем max F в крайней вершине многоугольника; двигаясь в направлении, противоположном вектору grad – найдем min F в крайней вершине многоугольника. Координаты точки этой вершины и есть оптимальное решение; значение целевой функции в этой точке и есть искомое значение. Если система ограничений несовместна – мы не построим многоугольник. Если получился незамкнутый многоугольник – то задача может иметь множество решений. Если решение задачи не единственное, то прямая c₁x₁+c₂x₂=с совпадает со стороной многоугольника и оптимальных решений два в двух вершинах многоугольника.

Вопрос 26

Симплекс метод. Решение произвольной задачи линейного программирования, т.е. с произвольным количеством переменных осуществляется симплеск-методом. Прежде чем решать задачу этим методом необходимо свести ее к каноническому виду. Этот метод основан на переходе от одного допустимого плана к другому, при котором значение целевой функции возрастает (при условии, что оптимальное решение существует и каждое допустимое значение невырождено). Пусть необходимо решить задачу о нахождении минимума целевой функции. F=c₁x₁+c₂x₂+…+c_nx_n при условии

x₁+a_1(m+1)x_m+1+…+a_1nx_n=b₁

x₂+a_2(m+1)x_m+1+…+a_2nx_n=b₂

x_m+a_m(m+1)x_m+1+…+a_mnx_n=b_m

- F+C_m+1x_m+1+…+c_nx_n= -F₀

x₁,x₂,…,x_n≥0

Такая форма записи задачи называется базисной. В этом случае допустимым решением будет x₁=b₁, x₂=b₂,…, x_m=b_m, x_m+1=0,…, x_n=0; F=F₀ – значение целевой функции. Составляется таблица:

Базис	В	х1	х2	…	хm	xm+1	…	xn
x1	b1	1	0	…	0	a1(m+1)	…	a1n
x2	b2	0	1	…	0	a2(m+1)	…	a2n
…	…	…	…	…	…	…	…	…
xm	bm	0	0	…	1	am(m+1)	…	amn
- F	- F0	0	0	…	0	Cm+1	…	Cn

Если в последней строке таблицы (-F) все коэффициенты положительны c_j≥0, то данное допустимое решение является оптимальным, в противном случае допустимое решение улучшается: выбираем разрешающий столбец – тот, где наибольшее по модулю отрицательное c_j, выбираем разрешающую строку – наименьшее положительное значение b_i/a_ij. На пересечении разрешающей строки и столбца находится разрешающий элемент a_ij. Всю строку делим на этот элемент, переменную x_j переводим в базис, вместо переменной, находившейся в базисе в i-ой строке. Все элементы j-го столбца, кроме j, зануляем с помощью преобразований строк матрицы (включая элемент в последней строке (- F). И так выполняем действия, пока не придем к одному из случаев: 1. Находим оптимальное решение, все коэффициенты последней строки ≥0 (c_j≥0). 2. Все элементы последней строки c_j≤0, тогда задача не имеет решений. Если исходная система не является базисной, т.е. нет таких m переменных с коэффициентом 1, чтобы в остальных уравнениях при них был, коэффициент 0, тогда вводят искусственные переменные с коэффициентом 1. x_k, x_k+1,…,x_k+s и рассматривается функция W= x_k, x_k+1,…,x_k+s равное их сумме. Решается задача минимизации этой функции, т.е. ее добавляют последней строкой в таблицу и решается относительно этой функции, строка – F- промежуточная строка. После того как эта задача решена, будет найдено базисное решение, можно решать задачу минимизации функции F. Замечания: Если надо найти max целевой функции F=c₁x₁+c₂x₂+…+c_nx_n. Вводим функцию Z= - F. Z= - c₁x₁-c₂x₂-…-c_nx_n и решается задача минимизации функции Z. Решение Z=Z₀ дает решения для F= - Z₀; F=F₀.