Задача о назначениях как частный случай транспортной задачи

Задача о назначениях как частный случай транспортной задачи Лекция 3 2 Математическая модель m n L  cijxij  min i1 j 1 Ограничения по поставщикам: n  xij  ai , i  1,...,m j1 Ограничения по потребителям: m x ij  b j , j  1,...,n i1 3 xij  0,i  1,...,m, j  1,...,n. Поставщики В1 В2 ... Вn А1 x11 x12 … x1n А2 x21 x22 … x2n … … … … … Аm xm1 xm2 … xmn Пункты отправления Потребители Пункты назначения Запас ы В1 В2 ... Вn А1 с11 с12 … с1n а1 А2 с21 с22 … с2n а2 … … … … … … Аm сm1 с12 … cmn аm Потребн. b1 b2 … bn Пример 1. Ремонт с/х техники Мастер должен назначить 7 слесарей (А, В, … , Н) для ремонта сельскохозяйственной техники (К-701, Т-150М и т.д.), имеющий разного рода неисправности после окончания уборочной. Время (ч), которое каждый слесарь тратит на выполнение определенного вида ремонта, приведено в таблице: К-701 3 Т-150М Т-155М МТЗ-80 МТЗ-40 Т-100 Дон-1500 А 12 14 14 10 9 15 21 В 15 13 12 10 8 21 23 С D - 16 11 10 11 21 - 16 - - 8 9 - 21 E 13 11 13 9 8 15 21 F 13 13 11 11 9 22 28 H 12 13 13 9 10 22 27 Пример 1. Ремонт с/х техники Необходимо определить оптимальную расстановку слесарей по участкам работы, при которой суммарное время на выполнение работ будет минимальным. К-701 4 Т-150М Т-155М МТЗ-80 МТЗ-40 Т-100 Дон-1500 А 12 14 14 10 9 15 21 В 15 13 12 10 8 21 23 С D - 16 11 10 11 21 - 16 - - 8 9 - 21 E 13 11 13 9 8 15 21 F 13 13 11 11 9 22 28 H 12 13 13 9 10 22 27 Задача о назначениях – частный случай транспортной задачи.  Число поставщиков (рабочих, поставщиков рабочей силы) n совпадает с числом потребителей (работ, различных технологических операций) n.  Все запасы и заказы равны 1.  Так же как и в ТЗ – не требуется условие целочисленности (при соблюдении структуры ТЗ). 5 Пример 1. Ремонт с/х техники. Математическая модель. 99 99 99 99 99 Сбалансированная задача: 7 единиц техники, 7 слесарей. 𝑥 𝑖𝑗 – число слесарей 𝑖, назначенных на ремонт машины 𝑗, 𝑖 = 1, … , 7, 𝑗 = 1, … , 7. Целевая функция: суммарное время ремонта С  12x11 14x12 14x13  ...  99x31 16x32  ...10x75  22x76  27x77  min 6 Пример 1. Ремонт с/х техники. Математическая модель. 99 99 99 Ограничения по слесарям: x11  x12  x13  x14  x15  x16  x17  1 x21  x22  x23  x24  x25  x26  x27 1 x31  x32  x33  x34  x35  x36  x37 1 x41  x42  x43  x44  x45  x46  x47 1 x51  x52  x53  x54  x55  x56  x57 1 x61  x62  x63  x64  x65  x66  x67 1 99 99 Ограничения по машинам: x11  x21  x31  x41  x51  x61  x71 1 x12  x22  x32  x42  x52  x62  x72  1 x13  x23  x33  x43  x53  x63  x73  1 x14  x24  x34  x44  x54  x64  x74 1 x15  x25  x35  x45  x55  x65  x75  1 x16  x26  x36  x46  x56  x66  x76 1 x17  x27  x37  x47  x57  x67  x77 1 x71  x72  x73  x74  x75  x76  x77 1 8 xij  0,i  1,...,7; j  1,...,7 Пример 2 (начальное решение) 8 Пример 1 (оптимальное решение) 9 Тема 3. Двоичное программирование как частный случай целочисленного программирования 10 Метод ветвей и границ. Пример. max L  max( 7x1  3x 2) x2 8 7 5x1  2x 2 20 8x1  4x 2 38 xi  0, целые, i  1,2. x1 O 1) maxL  max(7x1  3x2 ) Решение непрерывной задачи: 5x1 2x2  20 8x1 4x2  38 x2  7 5x1  2x2 20 x1  0, x2  0 8x1  4x2  38 2) max L  max(7x1  3x2 ) x2  8 x1  0, x2 0 11 x1* 1 x2*  7, 5 L1* 29,5 12 Метод ветвей и границ. Пример. Задача 2 x1*=1,2; x2*=7; L2 = 29,4 х 1 1 Задача 4 x1*=1; x2*=7; L4 = 28 13 х2  8 Задача 1 x1*=1; x2*=7,5; L1 = 29,5 х2 7 Задача 3 x1*=0,75; x2*=8; L3 = 29,25 х 1 0 х1 2 Задача 5 x1*=2; x2*=5; L5 = 29 х2 9 х1  1 Задача 6 x1*=0; x2*=9,5; L6 = 28,5 Задача 8 x1*=0; x2*=9; L8 = 27 Задача 7 х2 10 несовместна Задача 9 несовместна Метод ветвей и границ. Пример. Выбор оптимального решения № задачи 1 14 х1 х2 L Решение 1 7,5 29,5 непрерывное 4 1 7 28 допустимое 5 2 5 29 8 9 27 оптимальное допустимое Задачи двоичного программирования целые неотрицательные 𝑥𝑗: принимают значения 0 или 1 𝒙𝒋 - двоичные (бинарные) переменные – в задачах типа «брать – не брать». 15 Пример «Финансирование проектов» Управляющему банком были представлены предложения о четырех проектах, претендующих на кредиты банка. Проект А должен принести компании прибыль $21 000, проект В - $18 000, проект С - $16 000 и проект D $17 500. При взвешивании этих предложений следует принять во внимание потребность проектов в наличности и массу доступной наличности для соответствующих периодов: 16 Пример «Финансирование проектов» Доступная наличность банка составляет $22 000 в течение периода 1, $25 000 – в течение периода 2, $ 38 000 – в течение периода 3 и $30 000 – в течение периода 4. Какие проекты следует финансировать и какое количество наличности необходимо в течение каждого периода, если цель состоит в том, чтобы максимизировать прибыль? 17 Финансирование проектов. Математическая модель. Переменные: 𝑥 = 1, проект 𝑖 поддержан 𝑖 = 1, … , 4. 0, проект 𝑖 не поддержан Целевая функция: суммарная прибыль 21000x1 18000x2 16000x3 17500x4  max Ограничения: доступная наличность по периодам 8000x1  7000x2  5000x3  9000x4 22000 8000x1  9000x2  7000x3  8000x4  25000 10000x1  9000x2  9000x3  7000x4  38000 10000x1 11000x2 11000x3  6000x4  30000 19 xi  бинарные,i  1,...,4 Финансирование проектов. Решение 19 Финансирование проектов. Дополнительные условия 20 Проект 1 и 3 не могут быть выбраны одновременно. x1  x3 1 Кейс. Станции скорой помощи Округ Вашингтон определил шесть городов, которые нуждаются в службе скорой помощи. Станции скорой помощи могут быть расположены в некоторых или во всех городах. Однако, в силу территориальной близости некоторых городов одна станция может обслуживать более одного населенного пункта. Единственным условием является время поездки: оно не должно превышать 15 минут. Приведенная ниже таблица содержит время поездки в минутах между шестью городами. 21 Станции скорой помощи Единственным условием является время поездки: оно не должно превышать 15 минут. Города 1 2 3 4 5 6 22 1 23 14 18 10 32 2 23 24 13 22 11 3 14 24 60 19 20 4 18 13 60 55 17 5 10 22 19 55 12 6 32 11 20 17 12 Города 1 2 3 4 5 6 1 1 1 1 2 1 1 1 3 1 1 4 1 1 5 1 1 1 6 1 1 1 Станции скорой помощи. Математическая модель. 1, если в городе i устанавливается станция xi   , i  1,...,6, 0, если в городе i не устанавливается станция Целевая функция – суммарное количество станций: 6 C   xi  min i1 Ограничения: каждый город должен быть обслужен по крайней мере одной станцией 1, е сли из города i можно обслужить город j k ij    0, е сли из города i нельзя обслужить город j i  1,...,6, j  1,...,6 6 k ij 23 i1 xi 1, j  1,...,6 Станции скорой помощи. Начальное решение 6 C   xi  min i1 6 k ij 24 i1 xi 1, j  1,...,6 Станции скорой помощи. Оптимальное решение 26