Типовой расчет №1 «Линейное программирование» (стр. 2 )

Решения, найденные графически и симплексным методом, совпадают

X=(800;1000), Fmax(x1,x2)=1 780 000.

Первоначальный план, составленный методом минимального элемента лучше (общая стоимость при нем меньше на 400 ед., чем при методе северо-западного угла), т. к. при его составлении непосредственно учитывались стоимости перевозок (таблица составлялась так, что сначала выбирались поставки с наиболее дешевой перевозкой)

Задача 2

Дана каноническая задача линейного программирования

А) Решить задачу графически

Б) Найти начальную угловую точку методом искусственного базиса

В) Найти оптимальное решение симплекс-методом

Г) Проверить правильность решения при помощи двойственной задачи. Кроме того, указать решение прямой задачи в оптимальной таблице двойственности и наоборот.

Решение.

А) Число уравнений 2, число переменных 4, значит, число базисных переменных равно 2, а число свободных 4-2=2. В качестве свободных переменных выберем x1 и x2 , а базисные переменные x3 и x4 выразим через них, т. е. приведем систему уравнений к единичному базису:

Т. е. целевую функцию выразили через свободные переменные. С учетом того, что по условию задачи все переменные больше нуля, получили:

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

или в виде

Запишем уравнения граничных прямых

Построим прямые L1 и L2 на плоскости X1OX2

L1	X1	0	-2
X2	2	0

L2	X1	0	4
X2	4	0

Построим график целевой функции

L: 3x2=x1+10

L	X1	0	-4
X2	10/3	2

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

Наискорейшее возрастание функции происходит в направлении вектора её градиента (1; -3), т. е. линии уровня будем перемещать перпендикулярно направлению вектора (1; -3).

График целевой функции L передвигается в направлении, обозначенном стрелкой (в направлении своего градиента), до тех пор, пока не достигнет граничной точки многоугольника – в нашем случае это точка M пересечения L2 и x2 =0. В этой точке M (4;0) целевая функция будет достигать максимума .

Б)

У нас только один единичный вектор, соответствует x1, поэтому в левую часть второго уравнения системы ограничений задачи добавим дополнительную неотрицательную переменную x5 (искусственная переменная) и рассмотрим расширенную задачу, состоящую в максимизации функции при условиях

Расширенная задача имеет опорный план X=(0, 0, 0, 0, 6), определяемый системой двух единичных векторов A1, A5, где М большая неопределенная постоянная величина. Составим первую таблицу для итерации, содержащую 3 строки.

Симплекс-таблицу составим так: в графе Базис записываются вектора переменных, принимаемые за базисные. На первом этапе это – A1, A5. Базисными будут переменные, каждая из которых входит только в одно уравнение системы, и нет такого уравнения, в которое не входила бы хотя бы одна из базисных переменных. В следующий столбец Cб запишем коэффициенты целевой функции, соответствующие каждой переменной. Столбец А0 – столбец свободных членов. Далее идут столбцы коэффициентов Ai при i–ой переменной.

i	Баз.	С баз.	А0	2	0	1	2	-М
A1	A2	A3	A4	A5
1	А1	2	0	3	-1	-2	1	0
2	А5	-М	6	0	2	1	1	1

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

i	Баз.	С баз.	А0	2	0	1	2	-М
A1	A2	A3	A4	A5
1	А1	2	0	1	-1/3	-2/3	1/3	0
2	А5	-М	6	0	2	1	1	1
3			L0=-6М	∆1=0	∆2=-2М-2/3	∆3=-M-7/3	∆4=-M-4/3	∆5=0

Для заполнения строки 3 вычислим:

В строке 3 получили три отрицательных числа, содержащих М, значит, опорный план расширенной задачи не является оптимальным. Поэтому переходим к новому опорному плану расширенной задачи, в качестве разрешающего столбца выбирается наибольший по абсолютному значению ∆i это столбец второй. Единственный положительный элемент в этом столбце 2, он и станет разрешающим элементом.

Вектор A2 введем в базис вместо А5. Таким образом, новыми базисными переменными становятся A1, A2. Следовательно, вектор A5 исключаем из базиса. Этот вектор не имеет смысла вводить не в один из последующих базисов, поэтому в дальнейшем столбец этого вектора не заполняем и не показываем.

Для получения новой таблицы разрешающую строку делим на разрешающий элемент, разрешающий столбец заполняем нулями, за исключением разрешающего элемента (получаем единичный вектор). Остальные элементы новой таблицы получаем методом Жордана-Гаусса, т. е. по правилу прямоугольника. Получаем таблицу:

i	Баз.	С баз.	А0	2	0	1	2
A1	A2	A3	A4
1	А1	2	1	1	0	-1/2	1/2
2	А2	0	3	0	1	1/2	1/2

Таким образом, начальная угловая точка X=(1,3,0,0) найдена методом искусственного базиса.

В) Продолжим решение. Найдем оптимальный план, продолжив вычисления в симплекс-таблице:

i	Баз.	С баз.	А0	2	0	1	2
A1	A2	A3	A4
1	А1	2	1	1	0	-1/2	1/2
2	А2	0	3	0	1	1/2	1/2
3			L0=2	∆1=0	∆2=0	∆3=-2	∆4=-1

Вычислив оценки ∆i, получаем, что среди оценок есть отрицательные, значит, план X1=(1; 3;0;0) не является оптимальным для задачи на максимум. Наибольшая по абсолютному значению отрицательная оценка это ∆3, значит, столбец А3 разрешающий. В столбце А3 единственный положительный элемент ½ во второй строке, значит, вторая строка разрешающая. Вводим в базис А3 вместо А2. Для получения новой таблицы разрешающую строку делим на разрешающий элемент, разрешающий столбец заполняем нулями, за исключением разрешающего элемента (получаем единичный вектор). Остальные элементы новой таблицы получаем методом Жордана-Гаусса, т. е. по правилу прямоугольника. Получаем таблицу:

i	Баз.	С баз.	А0	2	0	1	2
A1	A2	A3	A4
1	А1	2	4	1	1	0	1
2	А3	1	6	0	2	1	1
3			L0=14	∆1=0	∆2=4	∆3=0	∆4=1

Получили базисные вектора А1, А3. Среди оценок нет отрицательных, значит найдено оптимальное решение на максимум. X2=(4; 0;6;0) и Lmax(4;0;6;0)=14. Т. е.решение найденное графически и симплекс-методом совпадает.