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

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

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

< Предыдущая		Следующая >