--PAGE_BREAK--Методы решения задач линейного программирования.
2.1 Графический метод
Рассмотрим задачу линейного программирования относительно двух неизвестных:
где (2.1) – целевая функция задачи, (2.2) – основные ограничения, (2.3) – условия не отрицательности переменных.
Неравенствам (2.2) на плоскости соответствуют полуплоскости. Чтобы их построить, необходимо сначала построить прямые, отделяющие эти полуплоскости. Уравнения отделяющих прямых получаем их соответствующих неравенств путём замены знака неравенств на " = ". Отделяющие прямые лучше строить по двум точкам, которые являются точками пересечения с осями координат (у этих точек одна из координат равна нулю).
Чтобы выбрать полуплоскость, соответствующую заданному неравенству, достаточно проверить, принадлежит ли точка начала координат (0,0) полуплоскости, подставив координаты (0,0) в неравенство. Если неравенство окажется справедливым, то принадлежит, в противном случае – нет.
Неравенства (2.2) должны выполняться одновременно. Это означает, что решение задачи будет лежать сразу на всех построенных полуплоскостях. С математической точки зрения это равносильно тому, что решение принадлежит пересечению построенных полуплоскостей.
Условие не отрицательности переменных (2.3) требует, чтобы из пересечения полуплоскостей выбрали ту часть, которая лежит в 1 – ой четверти.
Целевая функция (2.1), как функция от двух переменных имеет пространственное представление. Для изображения её на плоскости используют линии уровня, уравнения которых получаем из целевой функции, приравнивая её к различным числовым значениям:
с1х1 + с2х2 = с, где с Î(– ∞, + ∞). (2.4)
Достаточно построить две линии уровня (выбрав произвольные значения С), чтобы, сравнив на них значения целевой функции, определить направление maxили min.
Возможные варианты решения задачи линейного программирования графическим методом представлены на рис 2.1.
Решим задачу линейного программирования
2.2. f(x) = – x1→ max (min)
Строим отделяющие прямые.
1-я отд. прямая
2х1+х2=4
х1=0; х2=4 (0;4)
х2=0; х1=2 (2;0)
2-я отд. прямая
2х1+х2=8
х1=0; х2=8 (0;8)
х2=0; х1=4 (4;0)
3-я отд. прямая
х1-2х2=3
х1=0; х2=-1,5 (0;-1,5)
х2=0; х2=3 (3;0)
4-я отд. прямая
-х1+2х2=6
х1=0; х2=3 (0;3)
х2=0; х1=-6 (-6;0)
Линии уровня
1-я линия
-х1=5
х1=-5
2-я линия
-х1=-5
Х1=5
При решении задачи на максимум целевая функция достигнет своего оптимального значения в точке А, а на минимум в точке В. Найдем координаты этих точек.
А=(1-я отд. прямая) (4 отд. прямая)
2х1+х2=4 х2=4-2х1 -5х1= -2 х2= 4-0,8
-х1+2х2=6 -х1+2(4-2 х1)=6 х1= 0,4 х2= 3,2
А(0,4; 3,2)
В(2-я отд. прямая) (3-я отд. прямая)
2х1+х2=8 х1= 3+2х2 х1=3+0,8
х1 — 2х2=3 2(3+2х2) + х2=8 х1= 3,8
5х2= 2
х2= 0,4
В(3,8; 0,4)
F(max) А -0,4
F(min) В -3,8
2.2 Симплекс метод
Учитывая тот факт, что целевая функция достигает своего оптимального значения в одной из вершин многогранника допустимых решений задачи линейного программирования, то всякая процедура, предусматривающая направленный перебор угловых точек области определения задачи, должна привести к отысканию оптимального решения. Эта идея положена в основу классического метода решения задач линейного программирования – симплекс – метода, который разработан Дж. Данцигом в 1947 году.
Симплекс – метод применяют к задачам линейного программирования, заданным в каноническом виде, где элементы вектора правых частей ограничений принимают неотрицательные значения:
(3.1)
Основные положения, на которых базируется симплекс – метод
1. Каждая вершина многогранника допустимых решений обладает следующими свойствами:
— m её координат имеют значения ≥0 (их называют базисными переменными);
— остальные (n— m) координат равны нулю (их называют свободными переменными);
— вектор – столбцы матрицы коэффициентов А, соответствующие базисным переменным вершины являются линейно независимыми, т.е. с- помощью линейных преобразований их можно привести к единичной матрице.
2. Соседние вершины многогранника допустимых решений отличаются только одной базисной переменной.
3. Переход из одной вершины в другую осуществляется с помощью метода последовательного исключения неизвестных, который называется методом Жордана-Гаусса. В результате чего из базисного решения выводим одну переменную, а вводим другую. Причём, из свободных переменных, не вошедших в базис, вводим ту, которая больше всех уменьшает значение целевой функции. А из базисных переменных выводим ту, которая не нарушает условия неотрицательности базисных переменных у новой вершины. При этом вектор – столбцы матрицы ограничений А, соответствующие новой вершине, так же будет линейно независимыми, т.е. образовывать единичную матрицу.
Алгоритм симплекс – метода
1. Находим первое опорное решение (угловую точку).
2. Составляем симплексную таблицу (см. рис.3.1).
3. Выясняем, имеется ли хотя бы одно отрицательное число ∆j. Если таких чисел нет, то найденное опорное решение является оптимальным. Если же среди чисел ∆j имеются отрицательные, то либо переходят к новому опорному решению, либо устанавливают неразрешимость задачи, когда все коэффициенты столбца матрицы ограничений А, соответствующего отрицательному ∆j, тоже отрицательны.
4. Направляющий столбец (номер вводимой в базис переменной) определяем наибольшим по абсолютной величине отрицательным числом ∆j. Пусть это будет к-ый столбец.
5. Направляющая строка (номер выводимой из базиса переменной) соответствует минимальному из всех соотношений для положительных значений аik. Пусть это l– ая строка.
6. По методу Жордана – Гаусса исключаем переменную Хк из всех ограничений, кроме l–ого, где эта переменная должна быть с коэффициентом 1. Строим, новею симплекс – таблицу.
7. Переходим к этапу 3.
Для поиска первого опорного решения можно использовать следующие методы:
— метод естественного базиса,
— метод искусственного базиса.
Метод естественного базисаприменяется для задач линейного программирования, записанных в виде (3.2), где все ограничения неравенства имеют тип "≤" и элементы вектора правых частей ограничений неотрицательны.
(3.2)
В этом случае задачу (3.2) приводим к каноническому виду (3.3), вводя в левую часть каждого ограничения неравенства самостоятельную переменную, которые и будут образовывать естественный базис.
(3.3)
Метод искусственного базиса
применяется для задач, заданных в каноническом виде, или с ограничениями смешанного типа. Если в задаче ограничения смешанного типа, то её сначала преобразуем к каноническому виду (3.1), причем нужно отслеживать, чтобы элементы вектора правых частей были неотрицательными, а затем в каждое ограничение равенство водим по самостоятельной переменной yj , которые и будут образовывать искусственный базис. При этом в целевой функции переменные искусственного базиса записываются с большими отрицательными коэффициентами. В результате преобразований получим задачу вида (3.4).
(3.4)
базис
Сбазис
b
С1
С2
…
Сn
Х1
Х2
…
Xn
X1базис
С1базис
b1
a11
a12
…
a1n
Х2базис
С2базис
b2
a21
a22
…
a2n
…
…
…
…
…
…
…
Хмбазис
Сmбазис
bm
am1
am2
…
amn
(Cбазис,b)
…
Рис. 3.1. Симплексная таблица
Правила заполнения первой симплексной таблицы
1. Вместо С1, С2, …, Сnзаписываем соответствующие коэффициенты целевой функции.
2. Вместо аijзаписываем коэффициенты при неизвестных из основных ограничений задачи.
3. Вместо Хiбазисзаписываем имена переменных, вошедших в базис, в той последовательности, в которой они образуют единичную матрицу.
4. Вместо Сiбазисзаписываем коэффициенты целевой функции при соответствующих базисных переменных.
5. Вместо biзаписываем элементы вектора правых частей задачи.
6.
7.
Оптимальное значение переменных соответствует элементам из столбца «b» последней симплексной таблицы, а максимальное значение целевой функции содержимому ячейки (сбазис ,b).
2.3 Двойственные задачи
Прежде чем строить двойственную задачу, предварительно исходную задачу линейного программирования нужно привести к виду, где все ограничения неравенства имеют один тип, а целевая функция — направление, противоположное типу ограничений неравенств.
Правила построения двойственной задачи.
1. Целевая функция в двойственной задаче меняет своё направление на противоположное.
2. Количество двойственных переменных равно количеству основных ограничений исходной задачи.
3. Двойственная переменная, соответствующая ограничению равенству, является неограниченной по знаку, а соответствующая ограничению неравенству – неотрицательной.
4. Вектор правых частей ограничений исходной задачи является вектором коэффициентов целевой функции в двойственной задаче.
5. Вектор коэффициентов целевой функции исходной задачи является вектором правых частей ограничений в двойственной задаче.
6. Матрица коэффициентов ограничений двойственной задачи – это транспонированная матрица коэффициентов исходной задачи, т.е. строка коэффициентов исходной задачи, является столбцом коэффициентов двойственной задачи.
7. Неотрицательным переменным исходной задачи соответствуют ограничения неравенства в двойственной задаче, причем тип неравенства меняется на противоположный, по сравнению с исходной задачей. А неограниченной переменной исходной задачи соответствует ограничение равенство в двойственной задаче.
Соотношение двойственности является симметричным, т.е. двойственная задача по отношению к двойственной совпадает с исходной.
Если исходная задача линейного программирования записана в стандартном виде: (с, х)→max
(4.1)
то соответствующая ей двойственная задача записывается следующим образом:
(b, y)→min
(4.2)
Для следующей задачи линейного программирования построим двойственную задачу.
3x1+ 3x2– 4x3→ max
-2х1 — х2 + 3х3 ≤ -18 у1
4х1 - 5 х3 ≤ 12 у2
3х1 — 2 х2 + х3 = 14 у3
х1 ≥ 0; х2≥ 0; х3 ≥ 0
Вводом двойственные переменные
-18у1+12у2+14у3 min
-2у1 + 4у2 + 3у 3≥ 3
-у1 - 2у3 ≥3
3у1 — 5у2 + у3 ≥ -4
у1 ≥0; у2≥0
3 Раздел
Применение экономико-математического моделирования для обоснования
плановых прогнозных решений.
продолжение
--PAGE_BREAK--