Задачи линейного программирования |
Задачи линейного программирования 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.
Транспортная задача имеет закрытый тип, так как суммарный запас груза равен суммарным потребностям. Находим опорный план по правилу северо-западного угла: Помещаем в клетку (1,1) меньшее из чисел A1*=320 и B1*=150 Помещаем в клетку (1,2) меньшее из чисел A1*=170 и B2*=140 Помещаем в клетку (1,3) меньшее из чисел A1*=30 и B3*=110 Помещаем в клетку (2,3) меньшее из чисел A2*=280 и B3*=80 Помещаем в клетку (2,4) меньшее из чисел A2*=200 и B4*=230 Помещаем в клетку (3,4) меньшее из чисел A3*=250 и B4*=30 Помещаем в клетку (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 Определяем значения оценок Si, j=Ci, j-(Ui+Vj) для всех свободных клеток (Неоптимальные выделены красным цветом) S1,4 = c1,4 - (u1 + v4) = -8. Так как имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (1,4). Для нее оценка равна -8.
Перемещаем по циклу груз величиной в 30 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус".
Целевая функция F= 13690 Значение целевой функции изменилось на 240 единиц по сравнению с предыдущим этапом. Этап 2 Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci, j(i=1..m, j=1..n), просматривая все занятые клетки. Потенциалы Ui, Vj: U1=0 Определяем значения оценок Si, j=Ci, j-(Ui+Vj) для всех свободных клеток (Неоптимальные выделены красным цветом) S1,3 = c1,3 - (u1 + v3) = 8. Наиболее потенциальной является клетка (2,2). Для нее оценка равна -12.
Перемещаем по циклу груз величиной в 140 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус".
Целевая функция F= 12010 Значение целевой функции изменилось на 1680 единиц по сравнению с предыдущим этапом. Этап 3 Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci, j(i=1..m, j=1..n), просматривая все занятые клетки. Потенциалы Ui, Vj: U1=0 Определяем значения оценок Si, j=Ci, j-(Ui+Vj) для всех свободных клеток (Неоптимальные выделены красным цветом) S1,2 = c1,2 - (u1 + v2) = 12. Наиболее потенциальной является клетка (3,1). Для нее оценка равна -8.
Перемещаем по циклу груз величиной в 30 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус".
Целевая функция F= 11770 Значение целевой функции изменилось на 240 единиц по сравнению с предыдущим этапом. Этап 4 Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci, j(i=1..m, j=1..n), просматривая все занятые клетки. Потенциалы Ui, Vj: U1=0 Определяем значения оценок Si, j=Ci, j-(Ui+Vj) для всех свободных клеток. S1,2 = c1,2 - (u1 + v2) = 12. Так как все оценки Si, j>=0, то полученный план является оптимальным.
Целевая функция F= 11770 Ответ: F= 11770
|