Исследование операций

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

Найти      F=2x₁+3x₂ ® max    при ограничениях

           

  .

Решение

 

1 Уравнение  х1+ 3х2 = 18

х1	0	6
х2	6	4

При х1 = 0, х2 = 0, тогда 0+3*0<18. Множество решений неравенства лежит ниже прямой (1).

2 Уравнение 2х1+х2=16

х1	8	4
х2	0	8

При (0;0), тогда 2*0+0<16. Множество решений лежит левее прямой (2).

3 Уравнение х2 = 5

4 Уравнение  3х1 = 21

х1 = 7

Т.к. хi≥0, то область решения находится в 1 квадранте

Решение задачи возможно в точках A, B, C, D, E. Найдем значение x1 и x2 в каждой из

точек.

1. А (0;5)

2. D (7;0)

3. Для нахождения координат  точки В решим систему уравнений  прямых (1) и (2) на пересечении которых  находится точка В.

х1 + 3х2 = 18

2х1 + х2 = 16

х1 = 18-3х2

2(18-3х2)+х2=16

х1=18-3х2

36-6х2+х2=16

х1=18-3х2

-5х2=16-36

х1=18-3х2

Х2=4

Х1=18-3*4=6

Точка В имеет координаты (6;4).

44 Аналогично найдем координаты точки С.

2х1+х2=16

3х1=31

Х1=7

Х2=16-2х1=16-14=2

Точка С имеет координаты (7;2).

5. Найдем координаты точки Е

Х1+3х2=18

Х2=5

Х1=18-3*5=3

Точка Е имеет координаты (3;5).

6. Функция, определяющая критерий оптимальности, имеет вид:

F = 2х1+3х2

Определим значение функции 

Fа = 2*0+3*5=15

Fв = 2*6+3*4=24 => max

Fc = 2*7 + 3 * 2 = 20

F_D = 2*7 + 3*0 = 14

F_Е = 2*3 + 3*5 = 21

Ответ: максимальное значение целевой функции 24 достигается в точке (6;4).

 

 

2 Решить  задачу симплексным методом:

Найти      F=3x₁+3x₂ ® max    при ограничениях           

  .

Решение

 

Приводим задачу к каноническому виду

Там, где стоит  знак неравенства "<=", то к левой  части добавляем еще одну новую  переменную xi со знаком "+", а если знак неравенства ">=", то xi со знаком "-"; если же у условия знак "=", то ничего не добавляем. (xi >= 0)

К примеру, в 1-ом условии добавляем переменную x3 со знаком "+".

Получаем:

x1 + x2 + x3 = 8

2*x1 - x2 - x4 = 1

x1 - 2*x2 + x5 = 2

Введем искусственные  переменные.

Т.к. в некоторых  уравнениях системы условий нету переменной, которая бы входила в свое уравнениение с коэфициентом 1, а в остальные уравнения с коэфициентом 0 (т.е. не входила бы в др.)

Для примера, в 2-ом уравнении 2*x1 - x2 - x4 = 1 все переменные или с коэф., отличным от 1, или  же содержатся и в других уравнениях. Поэтому в это уравнение вводим переменную z1.

Проделаем для  всех уравнений, в результате введем искусственные переменные z1 >= 0:

x1 + x2 + x3 = 8

2*x1 - x2 - x4 + z1 = 1

x1 - 2*x2 + x5 = 2

Т.к. нам пришлось вводить искуственные переменные, то требуется ввести еще одну функцию W, равную сумме искусственных переменных, умноженную на -1, Коэф. при переменных в W мы должны обратить в симплекс-таблице в ноль

Введем новую  функцию:

W = -z1

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

Выразим искусственные  переменные z1 через остальные:

z1 = -2*x1 + x2 + x4 + 1

Подставляем в W, получаем:

W = 2*x1 - x2 - x4 - 1

Находим базисные переменные:

Все переменные, которые входят один раз в систему уравнений и они с коэфициентом 1, называются базисными переменными.

Пройдясь глазами  по системе уравнений находим  эти переменные:

x3, z1, x5

Составляем  начальную таблицу.

Берем уравнения  из последнего действия и подставляем в таблицу.

Вдоль каждой строки в таблице проставлены коэфициенты  при неизвестных в соответствующих уравнениях.

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

Последний столбец  вспомогательный.

В предпоследней строке стоят коэффициенты при неизвестных из функции F

В последней  строке стоят коэф. при неизвестных  из функции W.

БП	х1	х2	х3	х4	х5	z1	Сб	Отношение
х3	1	1	1	0	0	0	8	-
х5	2	-1	0	-1	0	1	1	-
z1	1	-2	0	0	1	0	2	-
F	-3	-3	0	0	0	0	0	-
W	-2	1	0	1	0	0	-1	-

 

Чтобы найти  решение для данной задачи:

- сначала, в строке таблицы, связанной с функцией W мы будем стремиться сделать все коэфициенты при неискуственных переменных равными нулю;

- в строке таблицы, связанной с функцией F мы будем стремиться сделать коэфициенты все положительными.

Для этого, мы будем:

- находить столбец по наименьшему не равному нулю коэфициенту в строке W (такой столбец называется направляющим

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

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

Номер разрешающего столбца равен 1, т.к. минимальный элемент в строке W равен -2.

Номер разрешающей строки есть 2, т.к. минимальное отношение свободного члена к элементу столбца равно 1/2.

Направляющий  элемент равен 2, он стоит на пересечении:

БП	х1	х2	х3	х4	х5	z1	Сб	Отношение
х3	1	1	1	0	0	0	8	8
х5	2	-1	0	-1	0	1	1	1|2
z1	1	-2	0	0	1	0	2	2
F	-3	-3	0	0	0	0	0	0
W	-2	1	0	1	0	0	-1	0

 

Разделим элементы строки 2 на 2, получим:

БП	х1	х2	х3	х4	х5	z1	Сб	Отношение
х3	1	1	1	0	0	0	8	8
х5	1	-1/2	0	-1/2	0	1/2	1/2	1/2
z1	1	-2	0	0	1	0	2	2
F	-3	-3	0	0	0	0	0	0
W	-2	1	0	1	0	0	-1	0

 

Из строки 1 вычтем эту помеченную строку, умноженную на 1

Из строки 3 вычтем 2 строку, умноженную на 1

Из строки L вычтем 2 строку, умноженную на -3

Из строки W вычтем 2 строку, умноженную на -2

БП	х1	х2	х3	х4	х5	z1	Сб	Отношение
х3	0	3/2	1	1/2	0	-1/2	15/2	8
х5	1	-1/2	0	-1/2	0	1/2	1/2	1/2
z1	0	-3/2	0	1/2	1	-1/2	3/2	2
F	0	-9/2	0	-3/2	0	3/2	3/2	0
W	0	0	0	0	0	1	0	0

 

Т.к. все элементы в строке W при неискусственных  переменных равны 0, то переходим к изменению строки F.

Номер разрешающего столбца равен 2, т.к. минимальный элемент в строке F равен -9/2.

Номер разрешающей  строки есть 1, т.к. минимальное отношение свободного члена к элементу столбца равно 5.

Направляющий  элемент равен 3/2, он стоит на пересечении:

БП	х1	х2	х3	х4	х5	z1	Сб	Отношение
х3	0	3/2	1	1/2	0	-1/2	15/2	5
х5	1	-1/2	0	-1/2	0	1/2	1/2	0
z1	0	-3/2	0	1/2	1	-1/2	3/2	0
F	0	-9/2	0	-3/2	0	3/2	3/2	0
W	0	0	0	0	0	1	0	0

 

Разделим элементы строки 1 на 3/2, получим:

БП	х1	х2	х3	х4	х5	z1	Сб	Отношение
х3	0	1	2/3	1/3	0	-1/3	5	5
х5	1	-1/2	0	-1/2	0	1/2	1/2	0
z1	0	-3/2	0	1/2	1	-1/2	3/2	0
F	0	-9/2	0	-3/2	0	3/2	3/2	0
W	0	0	0	0	0	1	0	0