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

A_q,0  A_i,0

------ = min ------ , i = 1,...,m.

A_q,p  i    A_i,p

Элемент A_q,p называется разрешающим элементом, cтрока q симплекс-таблицы, содержащая ведущий элемент, называется, соответственно, разрешающей строкой. Переменная ведущей строки x_q заменяется в базисе переменной разрешающего столбца x_p и становится свободной переменной с значением 0, в то время как новая базисная переменная x_p достигнет максимально возможного значения, равного: max x_p = ( A_q,0 / A_q,p).

После указанного взаимообразного обмена переменными x_p и x_q между наборами свободных и базисных переменных нужно модифицировать исходную каноническую модель задачи путем приведения ее к диагональной форме относительно нового множества базисных переменных. Для указанного преобразования можно формально использовать процедуру исключения Гаусса, которая, как известно, состоит из двух элементарных операций, применяемых к системе алгебраических уравнений ( в данном случае ограничений - равенств):

• умножение уравнения E₁(x) = 0 на константу K₁ и замена уравнения E₁(x) = 0 уравнением K₁*E₁(x) = 0;
• сложение уравнений E₁(x) = 0 и E₂(x) = 0 c последующей заменой уравнения E₂(x) = 0 уравнением E₁(x) + E₂(x) = 0.

Исключения Гаусса позволяют  привести систему уравнений к  диагональной форме относительно желаемого  множества переменных. В данном случае исключение Гаусса применяется так, чтобы все элементы симплекс-таблицы в ведущем столбце, кроме ведущего элемента A_q,p, стали нулевыми, а ведущий элемент стал равным единице:

A_i,p = 0, если i не равно q

и

A_i,p = 1, если i = q.

Указанные шаги симплекс-метода повторяются, пока не будет получена симплекс-таблица, которая одновременно является прямо и двойственно допустимой. Если положит в такой симплекс-таблице текущие базисные переменные равными A_i,0, а свободные - нулю, то будет получено оптимальное решение.

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

Алгоритм решения  задач симплекс – методом

1. Поставленная описательная задача переводится в математическую форму (целевая функция и ограничения).
2. Полученное математическое описание приводят к канонической форме.
3. Каноническую форму приводят к матричному виду.
4. Ищут первое допустимое решение. Для этого матрица должна быть правильной. Матрица в ЗЛП называется правильной, если она содержит минимум m правильных (базисных) столбцов, где m – число строк в матрице. Столбец в канонической ЗЛП называется правильным (базисным), если все его элементы равны нулю, кроме единственного равного единице.
5. Если матрица не является правильной, то ее нужно сделать таковой с помощью искусственного базиса. Для этого в матрицу нужно дописать столько базисных столбцов, чтобы их общее количество вместе с уже имеющимися базисными столбцами составляло m. После этого переходят к пункту 6. Если искусственный столбец выходит из базиса, то его удаляют из матрицы. Если удалены все искусственные столбцы, то получено первое допустимое решение. Если искусственные элементы не удается вывести из базиса, то система не имеет решений.
6. Строят последовательность матриц. Нужно определить разрешающий столбец, разрешающую строку и разрешающий элемент. Элемент, соответствующий разрешающей строке, удаляется из базиса, а на его место ставят элемент, соответствующий разрешающему столбцу. Составляют уравнение пересчета матрицы, выполняют пересчет, а затем проверяют его результаты на оптимальность. Если решение не оптимально, то заново ограничивают ведущий элемент, ведущую строку и ведущий столбец.

Признаком оптимальности  решения является наличие в векторе  решений только отрицательных или  нулевых коэффициентов при всех ограничениях.

Ответ записывается следующим образом:

- Каждому отрицательному коэффициенту в векторе решения ставится в соответствие нулевой коэффициент для соответствующей переменной в ответе.

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

- Фиктивные  переменные в ответе не учитываются.

Разрешающим может быть назначен любой столбец, удовлетворяющий одному из условий:

1) Первый столбец, содержащий положительный элемент в векторе решений.

2) Столбец, содержащий наибольший положительный элемент в строке решения.

3) Если столбец удовлетворяет условию max(C_j min b_j/a_ij) при решении на max, и min(C_j min b_j/a_ij) при решении задач на min.

C_j – коэффициент целевой функции в столбце j, a_ij – коэффициент в столбце j и строке i.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Примеры  решения задач различными методами  ЛП

Задача 1.

Предприятие выпускает  пиломатериалы и фанеру, используя при этом еловые и пихтовые лесоматериалы. Для изготовления 2,5 м³ пиломатериалов необходимо израсходовать 2,5 м³ еловых и 7,5 м³ пихтовых лесоматериалов. Для приготовления 100 м³ фанеры требуется 5 м³ еловых, 10 м³ пихтовых. Запасы предприятия составляют  80 м³ еловых и 180 м³  лесоматериалы. Найти оптимальный план производства предприятия, если по условиям поставки необходимо произвести не менее 10 м³ лесоматериалов и 1200 м³ фанеры. Доход с 1 м³ пиломатериалов составляет 16 у.е., со 100 м² - 60 у.е.

Решение

Введем следующие  обозначения:x₁- площадь фанеры(100 м²); x₂- площадь пиломатериалов (м³).

Доход от реализации фанеры составляет 16x₁, а от реализации пиломатериалов 60x₂, т.е. необходимо максимизировать целевую функцию:

F(x₁,x₂)=16x₁+60x₂→max

Ограничения задачи имеют вид:

5x₁+x₂≤80,         (1)

10x₁+7,5x₂≤180, (2)

x₂≥10,                 (3)

x₁≥12.                 (4)

Первое ограничение по еловым пиломатериалам 5x₁+x₂≤80. Прямая 5x₁+x₂=80 проходит через точки (0,80) и (16,0).

Второе ограничение  по пихтовым пиломатериалам 10x₁+7,5x₂≤180. Прямая 10x₁+7,5x₂=180 проходит через точки (0,18) и (60,0). Третье ограничение попиломатериалам и четвертое по фанере x₂≥12. Решением этой системы является полуплоскость выше (3) прямой и левее (1). На рис.2 заштрихована область допустимых значений.

Рис.2 Область  допустимых значений

Для определения  направления движения к оптимуму построим вектор-градиент Ñ, координаты которого являются частными производными целевой функции, т.е. =(16,60)

Что бы построить  этот вектор, нужно соединить точку (16;60) с началом координат. При максимизации целевой функции необходимо двигаться в направлении вектора-градиента.

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

5x₁+x₂=80,

x₂=10

Отсюда легко записать решение исходной ЗЛП: max f(x) = 800 и достигается при x₁=14 и x₂=10.

Рис.3. Максимум целевой функции достигается  в точке (14,10).

Таким образом, для оптимального плана производства предприятию  необходимо изготовить 10 м³ пиломатериалов и 14 м² фанеры.

Задача 2.

Завод производит два вида продукции: велосипеды и мотоциклы. При этом цех по сборке велосипедов имеет мощность 100 тыс. штук в год, цех по сборке мотоциклов 30 тыс. Одна группа механических цехов завода может производить детали либо для 120 тыс. велосипедов, либо для 40 тыс. мотоциклов, либо другую комбинацию деталей, ограниченную этими данными.Другая группа механических цехов может выпускать детали либо для 80 тыс. велосипедов, либо для 60 тыс. мотоциклов, либо любую допустимую их комбинацию. В результате реализации каждой тысячи велосипедов завод получает прибыль в 2 тыс. рублей, а с каждой тыс. мотоциклов- 3 тыс. рублей.

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

Решение

В качестве переменных задачи возьмем количество велосипедов  и мотоциклов, выпускаемых заводом  в год (в тыс. штук): x₁ и x_2.

Учитывая возможности  сборочных цехов, необходимо потребовать, чтобы

x₁≤100,  (1)

                                                    x₂≤30     (2)

Проанализируем  возможности цехов. При  этом необходимо учитывать, что при выпуске обоих  видов продукции должно выполняться условие пропорциональности количества продукции данного вида доле производственной мощности , занятой ее выпуском. Если предусматривается производство 1000 велосипедов, то доля занятых производственных мощностей механических цехов первой группы составит 1/120 суммы всех мощностей, принимаемых в данном случае за единицу; на выпуск же x₁ тыс. велосипедов потребуется занять (1/120) x₁ всей мощности. Аналогично для производства x₂ тыс. мотоциклов необходимо выделить (1/40) x₂ всей мощности. Так что для реализации плана (x_1,x₂) потребуется предусмотреть

((1/120)x₁+(1/40)x₂) мощности механических цехов первой группы. Но в производственном процессе может быть использована не более чем вся наличная производственная мощность рассматриваемых цехов, следовательно

(1/120)x₁+(1/40)x₂≤1,  (3)

Точно также  получаем ограничения по производственной мощности механических цехов второй группы:

(1/80)x₁+(1/60)x₂≤1.   (4)

По смыслу задачи:

    x₁≥0,  (5)

x₂≥0     (6)

Любой план (x_1,x₂), удовлетворяющий ограничениям (1)-(6), будет допустимым и дает предприятию прибыль (в тыс. руб): f(x_1,x₂)=2x₁+3x₂

Соотношения образуют математическую модель задачи:

f(x_1,x₂)=2x₁+3x₂→max

          x₁≤100,       (1)

                                                    x₂≤30,            (2)

(1/120)x₁+(1/40)x₂≤1,    (3)

(1/80)x₁+(1/60)x₂≤1.     (4)

                  x₁≥0,   x₂≥0          

Решим данную задачу графическим методом. Для этого  на графике отметим координаты прямой (1/120)x₁+(1/40)x₂=1, она проходит через точки (0,120) и (40,0) и координаты прямой (1/80)x₁+(1/60)x₂=1, которая проходит через точки (0,80) и (60,0).Также отметим на графике          x₁=100 и x₂=30 (рис.3).

Для определения  направления движения к оптимуму построим вектор-градиент Ñ, координаты которого являются частными производными целевой функции, т.е. =(2;3)

Что бы построить  этот вектор, нужно соединить точку (2;3) с началом координат. При максимизации целевой функции необходимо двигаться в направлении вектора-градиента.

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

(1/120)x₁+(1/40)x₂=1

                                       (1/80)x₁+(1/60)x₂=1.    

Из первого  уравнения выразим x₁ и подставим его во второе уравнение:

x₁+3 x₂=120,

x₁=120-3 x_2.

Таким образом, при выпуске 24 тыс. мотоциклов и 48 тыс. велосипе -дов будет получена наибольшая сумма прибыли.

Задача 3.

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

Дано:

F(x)=-2x₁+x₂→max,

x₁+x₂≥4,

-x₁+2x₂≤2,

x₁+2x₂≤10

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

F(x)=-2x₁+x₂→max,

x₁+x₂-x₃=4,

-x₁+2x₂+x₄= 2,

x₁+2x₂+x₅= 10

 

 

1)Построим симплекс-таблицу:

базисные переменные	коэф. переменных					свободные члены	отношения
	x1	x2	x3	x4	x5
0	1	1	-1	0	0	4
0	-1	2	0	1	0	2
0	1	2	0	0	1	10
F	2	-1	0	0	0	0