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

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

 

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

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

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

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

 

Так как нет  отрицательных оценок W, значит выполняется признак оптимальности.

Xопт = (0, 0, 5, 0, 3, 9)

max F = 24

 

Ответ: Максимальное значение функции F = 24 достигается в точке с координатами Х = (0,0,5,0,3,9).

 

 

 

 

 

3 Транспортная  задача

 

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

В пунктах отправления  А_i находится соответственно а_i тонн груза (мощность поставщиков). В пункты В_j требуется доставить соответственно b_j тонн груза (спрос потребителей). Стоимость перевозки тонны груза из пункта А_i в пункт В_j представлена в таблице. Составить оптимальный план перевозки груза, чтобы сумма транспортных расходов была наименьшей.

        5 4 13 9

С=  2 7 9 8

9 7 11 7

1 6  1  1

А = (95; 35;55;75)

В = (15; 25; 8; 12)

 

Решение

 

1 Разрабатываем  опорный план

∑А=260;         ∑В=60

∑А>∑В→Вфикт = 200

Сфикт=3*maх cij = 3 * 13 = 39

	В1	В2	В3	В4	Вф	Рес.
А1	5	4 25	13	9	39 70	95
А2	2	7	9	8	39 35	35
А3	9	7	11	7	39 55	55
А4	1 15	6	1 8	1 12	39 40	75
Потр.	15	25	8	12	200

 

В процессе решения  задачи по загруженным клеткам проверяется  выполнение условия: количество загруженных  клеток должно быть равно числу N = m+n-1 = 4+5-1 =8

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

V = U+C

U=V-C

	В1	В2	В3	В4	Вф	Рес.	U
А1	5	4 25	13	9	39 70	95	0
А2	2	7	9	8	39 35	35	0
А3	9	7	11	7	39 55	55	0
А4	1 15	6	1 8	1 12	39 40	75	0
Потр.	15	25	8	12	200
V	1	4	1	1	39

 

3 Проверка плана на оптимальность исходит из принципа, что при любом его изменении цена в пунктах потребления не должна стать меньше, чем в принятом нам плане, т. е. для свободных клеток должно выполняться условие U+C≥V

Если условие  выполняется, то в свободную клетку ставится «+», если нет – «-». В нашем случае план оптимален:

 

	В1	В2	В3	В4	Вф	Рес.	U
А1	5 +	4 25	13 +	9 +	39 70	95	0
А2	2 +	7 +	9 +	8 +	39 35	35	0
А3	9 +	7 +	11 +	7 +	39 55	55	0
А4	1 15	6 +	1 8	1 12	39 40	75	0
Потр.	15	25	8	12	200
V	1	4	1	1	39

 

Затраты составляют:

25*4+70*39+35*39+39*55+15*1+8*1+12*1+40*39=7 935

 

Ответ: затраты составят 7 935

 

 

 

 

 

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

 

Найти условный экстремум функции f с помощью метода исключения:  

             f=3х2 + 2у2-3х+1       при         х2+у2=4

 

Решение

 

Уравнение x2+y2=4 представляет окружность с центром в начале координат радиуса 2.

Переменная x меняется в пределах от -2 до 2. Из этого уравнения  находим y2=4-x2 и подставляем в формулу  для функции

f=3x2+2(4-x2)-3x+1=x2-3x+9 (-2 Абсцисса вершины этой параболы x=3/2, значение функции в ней f=27/4. На концах отрезка [-2;2] функция принимает значения

f(x=-2)=4+6+9=19

f(x=2)=4-6+9=7

Среди трех полученных значений выбираем наименьшее и наибольшее:

f=27/4 - минимум

f=19 - максимум

 

Ответ: f=27/4 – минимум, f=19 - максимум