Так же решение контрольных, написание курсовых и рефератов по другим предметам.

logo

Решение контрольных по математике!!!

Связаться с нами

E-mail: matica@narod.ru

ICQ 229036787, ICQ 320619

 

Home

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

PDF Печать E-mail

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

9. Симплекс-метод. Компания производит полки для ванных комнат двух размеров – А и В. Агенты по продаже считают, что в неделю на рынке может быть реализовано до 550 полок. Для каждой полки типа А требуется 2 м2 материала, а для полки типа В – 3 м2 материала. Компания может получить до 1200 м2 материала в неделю. Для изготовления одной полки типа А требуется 12 мин машинного времени, а для изготовления одной полки типа В – 30 мин; машину можно использовать 160 час в неделю. Если прибыль от продажи полок типа А составляет 3 денежных единицы, а от полок типа В – 4 денежных единицы, то сколько полок каждого типа следует выпускать в неделю, чтобы получить максимальную прибыль?

Решение

Составим математическую модель задачи.

Пусть x1 – количество полок вида А, x2- количество полок вида В, которые производятся в неделю. Прибыль от продажи такого количества полок составит 3x1+4x2, прибыль требуется максимизировать. Выпишем ограничения задачи x1+x2≤550 - в неделю на рынке может быть реализовано до 550 полок.

Затраты материала: 2x1+3x2≤1200

Затраты машинного времени:12x1+30x2≤9600

Таким образом, приходим к задаче линейного программирования.

F=3x1+4x2→max,

X1+x2≤550,

2x1+3x2≤1200,

12x1+30x2≤9600,

X1≥0,x2≥0.

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

F=3x1+4x2→max,

X1+x2+x3=550,

2x1+3x2+x4=1200,

12x1+30x2+x5=9600,

Xi≥0,i=1,2,3,4,5

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

Базисные переменные

Коэф. переменных

Свободные члены

Отношения

X1

X2

X3

X4

X5

0

1

1

1

0

0

550

550

0

2

3

0

1

0

1200

400

0

12

30

0

0

1

9600

320

F

-3

-4

0

0

0

0

0

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

Базисные переменные

Коэф. переменных

Свободные члены

Отношения

X1

X2

X3

X4

X5

0

0,6

0

1

0

-0,033

230

383,3

0

0,8

0

0

1

-0,1

240

300

X2

0,4

1

0

0

0,033

320

800

F

-1,4

0

0

0

0,13

1280

Базисные переменные

Коэф. переменных

Свободные члены

Отношения

X1

X2

X3

X4

X5

0

0

0

1

-0,75

0,042

50

1190

X1

1

0

0

1,25

-0,125

300

2400

X2

0

1

0

-0,5

0,083

200

2409

F

0

0

0

1,75

-0,042

1700

Базисные переменные

Коэф. переменных

Свободные члены

Отношения

X1

X2

X3

X4

X5

X5

0

0

24

-18

1

1200

X1

1

0

3

-1

0

450

X2

0

1

-2

1

0

100

F

0

0

1

1

0

1750

В последнем плане строка F не содержит отрицательных значений, план x1=450,x2=100 оптимален, целевая функция принимает значение 1750.

Таким образом, чтобы получить максимальную прибыль предприятию необходимо производить 450 полок вида A и 100 полок вида В, при этом прибыль составит 1750 ден. ед., а останется неиспользованными 1200 минут машинного времени.

Ответ: Чтобы получить максимальную прибыль предприятию необходимо производить 450 полок вида A и 100 полок вида В, при этом прибыль составит 1750 ден. ед., а останется неиспользованными 1200 минут машинного времени.

10. Задача коммивояжера. Коммивояжер должен объездить 6 городов. Для того чтобы сократить расходы, он хочет построить такой маршрут, чтобы объездить все города точно по одному разу и вернуться в исходный с минимумом затрат. Исходный город A. Затраты на перемещение между городами заданы следующей матрицей:

A

B

C

D

E

F

A

26

42

15

29

25

B

7

16

1

30

25

C

20

13

35

5

0

D

21

16

25

18

18

E

12

46

27

48

5

F

23

5

5

9

5

Решение

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

X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)

Тогда F(X0) = 26 + 16 + 35 + 18 + 5 + 23 = 123

Для определения нижней границы множества воспользуемся Операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент. di = min(j) dij

I J

A

B

C

D

E

F

Di

A

M

26

42

15

29

25

15

B

7

M

16

1

30

25

1

C

20

13

M

35

5

0

0

D

21

16

25

M

18

18

16

E

12

46

27

48

M

5

5

F

23

5

5

9

5

M

5

Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент: dj = min(i) dij

I j

A

B

C

D

E

F

A

M

11

27

0

14

10

B

6

M

15

0

29

24

C

20

13

M

35

5

0

D

5

0

9

M

2

2

E

7

41

22

43

M

0

F

18

0

0

4

0

M

Dj

5

0

0

0

0

0

После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются Константами приведения.

I j

A

B

C

D

E

F

A

M

11

27

0

14

10

B

1

M

15

0

29

24

C

15

13

M

35

5

0

D

0

0

9

M

2

2

E

2

41

22

43

M

0

F

13

0

0

4

0

M

Шаг №1.

Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i, j) и (i*,j*).

I j

A

B

C

D

E

F

Di

A

M

11

27

0(10)

14

10

10

B

1

M

15

0(1)

29

24

1

C

15

13

M

35

5

0(5)

5

D

0(1)

0(0)

9

M

2

2

0

E

2

41

22

43

M

0(2)

2

F

13

0(0)

0(9)

4

0(2)

M

0

Dj

1

0

9

0

2

0

0

Наибольшая сумма констант приведения равна (10 + 0) = 10 для ребра (1,4), следовательно, множество разбивается на два подмножества (1,4) и (1*,4*).

Нижняя граница гамильтоновых циклов этого подмножества:

I j

A

B

C

D

E

F

Di

A

M

11

27

M

14

10

10

B

1

M

15

0

29

24

0

C

15

13

M

35

5

0

0

D

0

0

9

M

2

2

0

E

2

41

22

43

M

0

0

F

13

0

0

4

0

M

0

Dj

0

0

0

0

0

0

10

В результате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения.

После операции приведения сокращенная матрица будет иметь вид:

I j

A

B

C

E

F

Di

B

1

M

15

29

24

1

C

15

13

M

5

0

0

D

M

0

9

2

2

0

E

2

41

22

M

0

0

F

13

0

0

0

M

0

Dj

1

0

0

0

0

2

Поскольку нижняя граница этого подмножества (1,4) меньше, чем подмножества (1*,4*), то ребро (1,4) включаем в маршрут с новой границей H = 49

Шаг №2.

Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i, j) и (i*,j*).

I j

A

B

C

E

F

Di

B

0(16)

M

15

29

24

15

C

14

13

M

5

0(5)

5

D

M

0(2)

9

2

2

2

E

1

41

22

M

0(1)

1

F

12

0(0)

0(9)

0(2)

M

0

Dj

1

0

9

2

0

0

Наибольшая сумма констант приведения равна (15 + 1) = 16 для ребра (2,1), следовательно, множество разбивается на два подмножества (2,1) и (2*,1*).

Нижняя граница гамильтоновых циклов этого подмножества:

I j

A

B

C

E

F

Di

B

M

M

15

29

24

15

C

14

13

M

5

0

0

D

M

0

9

2

2

0

E

1

41

22

M

0

0

F

12

0

0

0

M

0

Dj

1

0

0

0

0

16

В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.

После операции приведения сокращенная матрица будет иметь вид:

I j

B

C

E

F

Di

C

13

M

5

0

0

D

0

9

2

2

0

E

41

22

M

0

0

F

0

0

0

M

0

Dj

0

0

0

0

0

Чтобы исключить подциклы, запретим следующие переходы: (4,2),

Поскольку нижняя граница этого подмножества (2,1) меньше, чем подмножества (2*,1*), то ребро (2,1) включаем в маршрут с новой границей H = 49

Шаг №3.

Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i, j) и (i*,j*).

I j

B

C

E

F

Di

C

13

M

5

0(5)

5

D

M

7

0(0)

0(0)

0

E

41

22

M

0(22)

22

F

0(13)

0(7)

0(0)

M

0

Dj

13

7

0

0

0

Наибольшая сумма констант приведения равна (22 + 0) = 22 для ребра (5,6), следовательно, множество разбивается на два подмножества (5,6) и (5*,6*).

Нижняя граница гамильтоновых циклов этого подмножества:

I j

B

C

E

F

Di

C

13

M

5

0

0

D

M

7

0

0

0

E

41

22

M

M

22

F

0

0

0

M

0

Dj

0

0

0

0

22

В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.

После операции приведения сокращенная матрица будет иметь вид:

I j

B

C

E

Di

C

13

M

5

5

D

M

7

0

0

F

0

0

M

0

Dj

0

0

0

5

Чтобы исключить подциклы, запретим следующие переходы: (4,2),

Поскольку нижняя граница этого подмножества (5,6) меньше, чем подмножества (5*,6*), то ребро (5,6) включаем в маршрут с новой границей H = 54

Шаг №4.

Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i, j) и (i*,j*).

I j

B

C

E

Di

C

8

M

0(8)

8

D

M

7

0(7)

7

F

0(8)

0(7)

M

0

Dj

8

7

0

0

Наибольшая сумма констант приведения равна (8 + 0) = 8 для ребра (3,5), следовательно, множество разбивается на два подмножества (3,5) и (3*,5*).

Нижняя граница гамильтоновых циклов этого подмножества:

I j

B

C

E

Di

C

8

M

M

8

D

M

7

0

0

F

0

0

M

0

Dj

0

0

0

8

В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.

После операции приведения сокращенная матрица будет иметь вид:

I j

B

C

Di

D

M

7

7

F

0

0

0

Dj

0

0

7

Поскольку нижняя граница этого подмножества (3,5) меньше, чем подмножества (3*,5*), то ребро (3,5) включаем в маршрут с новой границей H = 61

В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (4,3) и (6,2).

В результате по дереву ветвлений гамильтонов цикл образуют ребра:

(1,4), (4,3), (3,5), (5,6), (6,2), (2,1),

Длина маршрута равна F(Mk) = 62

11. Транспортная задача. Из трех холодильников Ai (i =1,3), вмещающих мороженную рыбу в количествах ai (тонн), необходимо последнюю доставить в пять магазинов Bj (j =1,5) в количествах bj (тонн). Стоимости перевозки 1 тонны рыбы из холодильника Ai в магазин Bj заданы в виде матрицы C=((cij)) (3x5). Написать математическую модель задачи и спланировать перевозки так, чтобы их общая стоимость была минимальной.

А1 = 320, а2 = 280, а3 = 250,

B1 = 150, b2 = 140, b3 = 110, b4 = 230, b5 = 220,

Решение

Примем некоторые обозначения: I - индекс строки, J - индекс столбца, M - количество поставщиков, N - количество потребителей, Xi, j - перевозка между поставщиком Ai и потребителем Bj.

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

B5

A1

20

0

23

0

20

0

15

0

24

0

320

A2

29

0

15

0

16

0

19

0

29

0

280

A3

6

0

11

0

10

0

9

0

8

0

250

Потребность

150

140

110

230

220

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

Находим опорный план по правилу северо-западного угла:
Введем некоторые обозначения:
Ai* - излишек нераспределенного груза от поставщика Ai
Bj* - недостача в поставке груза потребителю Bj

Помещаем в клетку (1,1) меньшее из чисел A1*=320 и B1*=150
Так как спрос потребителя B1 удовлетворен, то столбец 1 в дальнейшем в расчет не принимается

Помещаем в клетку (1,2) меньшее из чисел A1*=170 и B2*=140
Так как спрос потребителя B2 удовлетворен, то столбец 2 в дальнейшем в расчет не принимается

Помещаем в клетку (1,3) меньшее из чисел A1*=30 и B3*=110
Так как запасы поставщика A1 исчерпаны, то строка 1 в дальнейшем в расчет не принимается

Помещаем в клетку (2,3) меньшее из чисел A2*=280 и B3*=80
Так как спрос потребителя B3 удовлетворен, то столбец 3 в дальнейшем в расчет не принимается

Помещаем в клетку (2,4) меньшее из чисел A2*=200 и B4*=230
Так как запасы поставщика A2 исчерпаны, то строка 2 в дальнейшем в расчет не принимается

Помещаем в клетку (3,4) меньшее из чисел A3*=250 и B4*=30
Так как спрос потребителя B4 удовлетворен, то столбец 4 в дальнейшем в расчет не принимается

Помещаем в клетку (3,5) меньшее из чисел A3*=220 и B5*=220

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

B5

A1

20

150

23

140

20

30

15

24

320

A2

29

15

16

80

19

200

29

280

A3

6

11

10

9

30

8

220

250

Потребность

150

140

110

230

220

Целевая функция F=13930

Решаем задачу методом потенциалов:

Этап 1

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci, j(i=1..m, j=1..n), просматривая все занятые клетки. Потенциалы Ui, Vj:

U1=0
V1=C1,1-U1= 20
V2=C1,2-U1= 23
V3=C1,3-U1= 20
U2=C3,2-V3= -4
V4=C2,4-U2= 23
U3=C4,3-V4= -14
V5=C3,5-U3= 22

Определяем значения оценок Si, j=Ci, j-(Ui+Vj) для всех свободных клеток (Неоптимальные выделены красным цветом)

S1,4 = c1,4 - (u1 + v4) = -8.
S1,5 = c1,5 - (u1 + v5) = 2.
S2,1 = c2,1 - (u2 + v1) = 13.
S2,2 = c2,2 - (u2 + v2) = -4.
S2,5 = c2,5 - (u2 + v5) = 11.
S3,1 = c3,1 - (u3 + v1) = 0.
S3,2 = c3,2 - (u3 + v2) = 2.
S3,3 = c3,3 - (u3 + v3) = 4.

Так как имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (1,4). Для нее оценка равна -8.
Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

B5

A1

20

150

23

140

-

20

30

+

15

24

320

A2

29

15

+

16

80

-

19

200

29

280

A3

6

11

10

9

30

8

220

250

Потребность

150

140

110

230

220

Перемещаем по циклу груз величиной в 30 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус".
В результате перемещения по циклу получим новый план:

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

B5

A1

20

150

23

140

20

15

30

24

320

A2

29

15

16

110

19

170

29

280

A3

6

11

10

9

30

8

220

250

Потребность

150

140

110

230

220

Целевая функция F= 13690

Значение целевой функции изменилось на 240 единиц по сравнению с предыдущим этапом.

Этап 2

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci, j(i=1..m, j=1..n), просматривая все занятые клетки. Потенциалы Ui, Vj:

U1=0
V1=C1,1-U1= 20
V2=C1,2-U1= 23
V4=C1,4-U1= 15
U2=C4,2-V4= 4
U3=C4,3-V4= -6
V3=C2,3-U2= 12
V5=C3,5-U3= 14

Определяем значения оценок Si, j=Ci, j-(Ui+Vj) для всех свободных клеток (Неоптимальные выделены красным цветом)

S1,3 = c1,3 - (u1 + v3) = 8.
S1,5 = c1,5 - (u1 + v5) = 10.
S2,1 = c2,1 - (u2 + v1) = 5.
S2,2 = c2,2 - (u2 + v2) = -12.
S2,5 = c2,5 - (u2 + v5) = 11.
S3,1 = c3,1 - (u3 + v1) = -8.
S3,2 = c3,2 - (u3 + v2) = -6.
S3,3 = c3,3 - (u3 + v3) = 4.

Наиболее потенциальной является клетка (2,2). Для нее оценка равна -12.
Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

B5

A1

20

150

-

23

140

20

+

15

30

24

320

A2

29

+

15

16

110

-

19

170

29

280

A3

6

11

10

9

30

8

220

250

Потребность

150

140

110

230

220

Перемещаем по циклу груз величиной в 140 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус".
В результате перемещения по циклу получим новый план:

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

B5

A1

20

150

23

20

15

170

24

320

A2

29

15

140

16

110

19

30

29

280

A3

6

11

10

9

30

8

220

250

Потребность

150

140

110

230

220

Целевая функция F= 12010

Значение целевой функции изменилось на 1680 единиц по сравнению с предыдущим этапом.

Этап 3

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci, j(i=1..m, j=1..n), просматривая все занятые клетки. Потенциалы Ui, Vj:

U1=0
V1=C1,1-U1= 20
V4=C1,4-U1= 15
U2=C4,2-V4= 4
U3=C4,3-V4= -6
V2=C2,2-U2= 11
V3=C2,3-U2= 12
V5=C3,5-U3= 14

Определяем значения оценок Si, j=Ci, j-(Ui+Vj) для всех свободных клеток (Неоптимальные выделены красным цветом)

S1,2 = c1,2 - (u1 + v2) = 12.
S1,3 = c1,3 - (u1 + v3) = 8.
S1,5 = c1,5 - (u1 + v5) = 10.
S2,1 = c2,1 - (u2 + v1) = 5.
S2,5 = c2,5 - (u2 + v5) = 11.
S3,1 = c3,1 - (u3 + v1) = -8.
S3,2 = c3,2 - (u3 + v2) = 6.
S3,3 = c3,3 - (u3 + v3) = 4.

Наиболее потенциальной является клетка (3,1). Для нее оценка равна -8.
Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

B5

A1

-

20

150

23

20

+

15

170

24

320

A2

29

15

140

16

110

19

30

29

280

A3

+

6

11

10

-

9

30

8

220

250

Потребность

150

140

110

230

220

Перемещаем по циклу груз величиной в 30 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус".
В результате перемещения по циклу получим новый план:

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

B5

A1

20

120

23

20

15

200

24

320

A2

29

15

140

16

110

19

30

29

280

A3

6

30

11

10

9

8

220

250

Потребность

150

140

110

230

220

Целевая функция F= 11770

Значение целевой функции изменилось на 240 единиц по сравнению с предыдущим этапом.

Этап 4

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci, j(i=1..m, j=1..n), просматривая все занятые клетки. Потенциалы Ui, Vj:

U1=0
V1=C1,1-U1= 20
V4=C1,4-U1= 15
U3=C1,3-V1= -14
U2=C4,2-V4= 4
V2=C2,2-U2= 11
V3=C2,3-U2= 12
V5=C3,5-U3= 22

Определяем значения оценок Si, j=Ci, j-(Ui+Vj) для всех свободных клеток.

S1,2 = c1,2 - (u1 + v2) = 12.
S1,3 = c1,3 - (u1 + v3) = 8.
S1,5 = c1,5 - (u1 + v5) = 2.
S2,1 = c2,1 - (u2 + v1) = 5.
S2,5 = c2,5 - (u2 + v5) = 3.
S3,2 = c3,2 - (u3 + v2) = 14.
S3,3 = c3,3 - (u3 + v3) = 12.
S3,4 = c3,4 - (u3 + v4) = 8.

Так как все оценки Si, j>=0, то полученный план является оптимальным.
Транспортная задача решена.

Поставщик

Потребитель

Запасы
груза

B1

B2

B3

B4

B5

A1

20

120

23

20

15

200

24

320

A2

29

15

140

16

110

19

30

29

280

A3

6

30

11

10

9

8

220

250

Потребность

150

140

110

230

220

Целевая функция F= 11770

Ответ: F= 11770

 
Яндекс.Метрика
Наверх