Задачи линейного программирования

Титульный лист 
Оглавление

 

 

Задание № 1. Задачи линейного программирования

ЗАДАЧА 3.4Определите интервалы изменения значений целевой функции в следующих задачах ЛП,

1. Минимизировать z=5х1+2х2

при ограничениях

x1-x2≥ 3 ,

2x1 + Зх2 ≥ 5,

х1, х2 ≥0.

Решение.

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве вводим базисную переменную x3 со знаком минус. В 2-м неравенстве вводим базисную переменную x4 со знаком минус. Умножим все строки на (-1) и будем искать первоначальный опорный план.

xi ³ 0, i=1,2,3,4

z=5х1+2х2® min

Составляем симплекс-таблицу

Базис	C	B	5	2	0	0
			x1	x2	x3	x4
x3	0	-3	-1	1	1	0
x4	0	-5	-2	-3	0	1
z(x0)		0	5	2	0	0
q			5: (-2)=-2,5	2:(-3)=-2/3

Первый опорный план X1=(0;0;-3;-5)

В базисном столбце элементы есть отрицательные элементы

Среди отрицательных значений базисных переменных выбираем наибольший по модулю. Минимальное значение θ соответствует 2-му столбцу, т.е. переменную x2 необходимо ввести в базис. Ведущей будет 2-ая строка, а переменную x4 следует вывести из базиса.

На пересечении ведущих строки и столбца находится разрешающий элемент, равный (-3).

Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис	C	B	5	2	0	0
			x1	x2	x3	x4
x3	0	-42/3	-12/3	0	1	1/3
x2	2	5/3	2/3	1	0	-1/3
z(x1`)		-31/3	32/3	0	0	2/3
q			32/ (-12/3)=-2,2

В базисном столбце элементы есть отрицательные элементы

Минимальное значение θ соответствует 1-му столбцу, т.е. переменную x1 необходимо ввести в базис. На пересечении ведущих строки и столбца находится разрешающий элемент, равный (-12/3)

Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис	C	B	5	2	0	0
			x1	x2	x3	x4
X1	5	24/5	1	1	1	1/3
x2	2	-1/5	2/3	1	0	-1/3
z(x2)		-133/5	32/3	0	0	2/3

 

В базисном столбце элементы есть отрицательные элементы

Среди отрицательных значений базисных переменных выбираем наибольший по модулю. Ведущей будет 2-ая строка, а переменную x2 следует вывести из базиса.

Минимальное значение θ соответствует 4-му столбцу, т.е. переменную x4 необходимо ввести в базис.

На пересечении ведущих строки и столбца находится разрешающий элемент, равный (-1/5).

 

Базис	C	B	5	2	0	0
			x1	x2	x3	x4
X1	5	3	1	-1	-1	0
X4	0	1	0	-5	-2	1
z(x2)		-15	0	7	5	0

В базисном столбце все элементы положительные.

Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.

x1=3; x2=0

zmin=15

b) Максимизировать z=х1+5х2+3х3 
при ограничениях

x1+2x2+x3=3,

2x1 -х2 = 4,

x1,х2,x3 ≥0.

Решение

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

Введем искусственные переменные x: в 1-м равенстве вводим переменную x4;в 2-м равенстве вводим переменную x5; 

x1 + 2x2 + x3 + x4 + 0x5 = 3

x1-x2 + 0x3 + 0x4 + x5 = 4

Для постановки задачи на максимум целевую функцию запишем так: 
F(X) = - Mx4 - Mx5 → max

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

Из уравнений выражаем искусственные переменные:

x4 = 3-x1-2x2-x3

x5 = 4-x1+x2

которые подставим в целевую функцию:

F(X) = - M(3-x1-2x2-x3) - M(4-x1+x2) → max

или 
F(X) = (2M)x1+(M)x2+(M)x3+(-7M) → max

Введем новую переменную x0 = 2x1 + x2 + x3.

Выразим базисные переменные <4,5> через небазисные.

x0 = -7+2x1+x2+x3

     x4 = 3-x1-2x2-x3

x5 = 4-x1+x2

Переходим к основному алгоритму симплекс-метода.

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

В выражении для x0 присутствуют отрицательные элементы. Следовательно, текущий план неоптимален

Определение новой базисной переменной.

max(2,1,1,0,0) = 2

x0 = -7+2x1+x2+x3

x4 = 3-x1-2x2-x3

x5 = 4-x1+x2

В качестве новой переменной выбираем x1.

Определение новой свободной переменной.Вычислим значения Di по всем уравнениям для этой переменной: bi / ai1 и из них выберем наименьшее:

min (3 : 1 , 4 : 1 ) = 3

Вместо переменной x4 в план войдет переменная x1.

Выразим переменную x1 через x4

x1 = 3-2x2-x3-x4

и подставим во все выражения.

x0 = -7+2(3-2x2-x3-x4)+x2+x3

x5 = 4-(3-2x2-x3-x4)+x2

После приведения всех подобных, получаем новую систему, эквивалентную прежней: 
x0 = -1-3x2-x3-2x4

x1 = 3-2x2-x3-x4

x5 = 1+3x2+x3+x4

Полагая небазисные переменные x = (1, 5) равными нулю, получим новый допустимый вектор и значение целевой функции:

x = (0, 3, 1, 2, 0), x0 = -1

Выражение для x0 не содержит положительных элементов. Найден оптимальный план.

x0 = -1-3x2-x3-2x4

x1 = 3-2x2-x3-x4

x5 = 1+3x2+x3+x4

На этом первый этап симплекс-метода завершен. Переходим ко второму этапу. Удаляем переменные с искусственными переменными.

x1 = 3-2x2-x3

x5 = 1+3x2+x3

Выразим базисные переменные:

x1 = 3-2x2-x3

которые подставим в целевую функцию:

F(X) = (3-2x2-x3) + 5x2 + 3x3

или 
F(X) = 3+3x2+2x3

Получаем новую систему переменных.

x0 = 3+3x2+2x3

x1 = 3-2x2-x3

x5 = 1+3x2+x3

В выражении для x0 присутствуют отрицательные элементы. Следовательно, текущий план неоптимален

Определение новой базисной переменной.

max(0,3,2) = 3

x0 = 3+3x2+2x3

x1 = 3-2x2-x3

x5 = 1+3x2+x3

В качестве новой переменной выбираем x2.

Определение новой свободной переменной.Вычислим значения Di по всем уравнениям для этой переменной: bi / ai2и из них выберем наименьшее:

min (3 : 2 , - ) = 11/2

Вместо переменной x1 в план войдет переменная x2.

Выразим переменную x2 через x1

x2 = 3/2-1/2x1-1/2x3 
и подставим во все выражения.

x0 = 3+3(3/2-1/2x1-1/2x3)+2x3

x5 = 1+3(3/2-1/2x1-1/2x3)+x3

После приведения всех подобных, получаем новую систему, эквивалентную прежней:

x0 = 15/2-3/2x1+1/2x3 
x2 = 3/2-1/2x1-1/2x3 
x5 = 11/2-3/2x1-1/2x3 
Полагая небазисные переменные x = (2, 5) равными нулю, получим новый допустимый вектор и значение целевой функции:

x = (3/2, 0, -1/2), x0 = 15/2

В выражении для x0 присутствуют отрицательные элементы. Следовательно, текущий план неоптимален

Определение новой базисной переменной.

max(-3/2,0,1/2) = ½

x0 = 15/2-3/2x1+1/2x3

x2 = 3/2-1/2x1-1/2x3

x5 = 11/2-3/2x1-1/2x3 
В качестве новой переменной выбираем x3.

Определение новой свободной переменной.Вычислим значения Di по всем уравнениям для этой переменной: bi / ai3 и из них выберем наименьшее:

min (11/2 : 1/2 , 51/2 : 1/2 ) = 3

Вместо переменной x2 в план войдет переменная x3.

Выразим переменную x3 через x2

x3 = 3-x1-2x2

и подставим во все выражения.

x0 = 71/2-11/2x1+1/2(3-x1-2x2)

x5 = 51/2-11/2x1-1/2(3-x1-2x2)

После приведения всех подобных, получаем новую систему, эквивалентную прежней:

x0 = 9-2x1-x2

x3 = 3-x1-2x2

x5 = 4-x1+x2

Полагая небазисные переменные x = (3, 5) равными нулю, получим новый допустимый вектор и значение целевой функции:

x = (2, 1, 0), x0 = 9

Выражение для x0 не содержит положительных элементов. Найден оптимальный план.

Окончательный вариант системы уравнений:

x0 = 9-2x1-x2

x3 = 3-x1-2x2

x5 = 4-x1+x2

Так как в оптимальном решении присутствуют искусственные переменные (x5 > 0), то задача не имеет допустимого решения.

c) Максимизировать z = 2х1 + х2

при ограничениях

х1 -х2≤ 10,

2х1 ≤ 40,

х1, х2   ≥0.

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

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (≤) вводим базисную переменную x3.

 В 2-м неравенстве  смысла (≤) вводим базисную переменную x4. 

x1-x2 + x3 + 0x4 = 10

2x1 + 0x2 + 0x3 + x4 = 40

Введем новую переменную x0 = 2x1 + x2.

Выразим базисные переменные <3, 4> через небазисные.

x0 = 0+2x1+x2

x3 = 10-x1+x2

x4 = 40-2x1

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

В выражении для x0 присутствуют отрицательные элементы. Следовательно, текущий план неоптимален

Определение новой базисной переменной. 
max(2,1,0,0) = 2

x0 = 0+2x1+x2

x3 = 10-x1+x2

x4 = 40-2x1

В качестве новой переменной выбираем x1.

Определение новой свободной переменной. Вычислим значения Di по всем уравнениям для этой переменной: bi /ai1 и из них выберем наименьшее:

min (10 : 1 , 40 : 2 ) = 10

Вместо переменной x3 в план войдет переменная x1.

Выразим переменную x1 через x3

x1 = 10+x2-x3

и подставим во все выражения.

x0 = 0+2(10+x2-x3)+x2

x4 = 40-2(10+x2-x3)

После приведения всех подобных, получаем новую систему, эквивалентную прежней:

x0 = 20+3x2-2x3

x1 = 10+x2-x3

x4 = 20-2x2+2x3

Полагая небазисные переменные x = (1, 4) равными нулю, получим новый допустимый вектор и значение целевой функции:

x = (0, -3, 2, 0), x0 = 20

В выражении для x0 присутствуют отрицательные элементы. Следовательно, текущий план неоптимален

 Определение новой базисной переменной.

max(0,3,-2,0) = 3

x0 = 20+3x2-2x3

x1 = 10+x2-x3

x4 = 20-2x2+2x3

В качестве новой переменной выбираем x2.

Определение новой свободной переменной. Вычислим значения Di по всем уравнениям для этой переменной:bi /ai2 и из них выберем наименьшее: 
min (- , 20 : 2 ) = 10

Вместо переменной x4 в план войдет переменная x2.

Выразим переменную x2 через x4

x2 = 10+x3-1/2x4

и подставим во все выражения.

x0 = 20+3(10+x3-1/2x4)-2x3

x1 = 10+(10+x3-1/2x4)-x3

После приведения всех подобных, получаем новую систему, эквивалентную прежней:

x0 = 50+x3-3/2x4

x1 = 20-1/2x4

x2 = 10+x3-1/2x4

Полагая небазисные переменные x = (1, 2) равными нулю, получим новый допустимый вектор и значение целевой функции:

x = (0, 0, -1, 3/2), x0 = 50

Окончательный вариант системы уравнений:

x0 = 50+x3-3/2x4

x1 = 20-1/2x4

x2 = 10+x3-1/2x4

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

d) Максимизировать z = Зх1 + 2х2 при ограничениях

2хх+х2<3,

Зx1+4x2>12,

x1,x2 ≥ 0.

Вешение. Решим прямую задачу линейного программирования симплекс-методом. Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве вводим базисную переменную x3. В 2-м неравенстве вводим базисную переменную x4 со знаком минус. 

2x1 + 1x2 + 1x3 + 0x4 = 3

3x1 + 4x2 + 0x3-1x4 = 12

Введем искусственные переменные x: в 2-м равенстве вводим переменную x5; 

2x1 + 1x2 + 1x3 + 0x4 + 0x5 = 3

3x1 + 4x2 + 0x3-1x4 + 1x5 = 12

Для постановки задачи на максимум целевую функцию запишем так: 
F(X) = - Mx5 → max

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

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

x5 = 12-3x1-4x2+x4

которые подставим в целевую функцию:

F(X) = - M(12-3x1-4x2+x4) → max

Или

F(X) = (3M)x1+(4M)x2+(-M)x4+(-12M) → max

Введем новую переменную x0 = 3x1 + 4x2.

Выразим базисные переменные <3, 5> через небазисные.

x0 = -12+3x1+4x2-x4

x3 = 3-2x1-x2

x5 = 12-3x1-4x2+x4

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

В выражении для x0 присутствуют отрицательные элементы. Следовательно, текущий план неоптимален