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

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

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

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

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

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

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

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

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

Решение

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

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

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

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

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

Шаг №1.

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

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

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

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

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

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

Шаг №2.

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

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

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

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

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

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

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

Шаг №3.

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

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

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

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

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

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

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

Шаг №4.

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

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

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

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

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

Поскольку нижняя граница этого подмножества (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.

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

Находим опорный план по правилу северо-западного угла:
Введем некоторые обозначения:
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

Целевая функция 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) для всех свободных клеток (Неоптимальные выделены красным цветом)