Транспортная задача как частный случай ЗЛП

Тема 2. Транспортная задача как частный случай ЗЛП Лекция 5 2 Пример 1. Песчаные карьеры Заводы Карьеры (, 0) (100, 0) A1 s (, 0) (, 0) (200, 0) B1 A2 (, 0) B2 3 (90, 0) (, 0) (, 0) B3 Транспортные издержки 𝑐𝑖𝑗 (80, 0) Завод В1 (130, 0) Завод В2 Завод В3 Карьер А1 4 6 3 Карьер А2 8 4 5 s Транспортная задача имеет целью минимизацию транспортных издержек при перевозках однотипных грузов от нескольких поставщиков (с различных складов), расположенных в разных местах, к разным потребителям. 4 Аналитическая постановка ТЗ Таблица издержек Пункты отправления (поставщики) Пункты назначения (потребители) Запасы В1 В2 ... Вn А1 с11 с12 … с1n а1 А2 с21 с22 … с2n а2 … … … … … … Аm сm1 сm2 … cmn аm Потребности b1 b2 … bn 𝒄𝒊𝒋 , 𝑖 = 1, … , 𝑚, 𝑗 = 1, … , 𝑛, – стоимость перевозки единицы груза от поставщика 𝑖 к потребителю 𝑗. 5 Таблица перевозок Поставщики Потребители В1 В2 ... Вn А1 x11 x12 … x1n А2 x21 x22 … x2n … … … … … Аm xm1 xm2 … xmn 𝒙𝒊𝒋, 𝑖 = 1, … , 𝑚, 𝑗 = 1, … , 𝑛, - количество единиц перевозимого груза от поставщика 𝑖 к потребителю 𝑗. 6 Математическая модель (аналит.) m n L    cij xij  min i 1 j 1 Ограничения по поставщикам: n  xij  ai , i  1,...,m j 1 Ограничения по потребителям: m x i 1 7 ij  b j , j  1,..., n 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 сm с12 … cm аm 1 Потребн. b1 n b2 … bn Двойственная задача к ТЗ Прямая задача m n L    cij xij  min i 1 j 1  yi : n  xij  ai , j 1 m pj : i  1,...,m x i 1 ij  b j , j  1,..., n xij  0, i  1,..., m, j  1,..., n. 8 Двойственная задача m n i 1 j 1 W   ai yi   b j p j  max xij : p j  yi  cij i  1,...,m; j  1,...,n Экономическая интерпретация двойственной задачи к ТЗ yi – цена на продукцию, производимую у 𝒊-го производителя (отпускная цена), 𝑖 = 1, … , 𝑚 pj – цена за единицу той же продукции, но у 𝒋-го потребителя, 𝑗 = 1, … , 𝑛 n b p j 1 j j – суммарная выручка у потребителей m a y i 1 9 i i – суммарная выручка у производителей. Экономическая интерпретация ДЗ к ТЗ ЦФ – прибыль от реализации перевезенной продукции: m n i 1 j 1 W   ai yi   b j p j  max Ограничения: разность в ценах у производителя и потребителя не должна превышать затраты на перевозки: p j  yi  cij 10 Экономическая интерпретация ДЗ к ТЗ Требуется назначить цены у производителя и у потребителя таким образом, чтобы прибыль от реализации продукции была максимальной, перевозки – не убыточными. m n i 1 j 1 W   ai yi   b j p j  max p j  yi  cij 11 i  1,...,m; j  1,...,n Условие сбалансированности ТЗ  ТЗ является сбалансированной (закрытой), если m n i 1 j 1  ai   b j  12 ТЗ является несбалансированной (открытой), если это условие нарушено Теорема (Критерий разрешимости ТЗ) Для того, чтобы ТЗ имела оптимальное решение, необходимо и достаточно, чтобы она была сбалансирована. 13 Пример «Песчаные карьеры» В районе имеется 2 песчаных карьера, с которых песок вывозится на 5-тонных грузовиках. Предприятия – поставщики, разрабатывающие карьеры, могут поставлять соответственно 100 и 200 грузовиков в день. В этом районе имеется 3 завода железобетонных конструкций – потребители песка, которым требуется соответственно 80, 90 и 130 грузовиков в день. 14 Таблица параметров (транспортные издержки) Bj B1 B2 B3 Запасы A1 4 6 3 100 A2 8 4 5 200 Заказы 80 90 130 300=300 Ai 15 Решение в Excel 16 Случаи открытой модели Перепроизводство: m n  a  b i 1 i j 1 j Дефицит: m n  a  b i 1 17 i j 1 j m n  a  b Перепроизводство i 1 i j 1 j  Вводят фиктивного потребителя Bn 1  «Заказ» (спрос) фиктивного потребителя – объем перепроизводства: m n i 1 j 1 bn1   ai   b j  Транспортные издержки 𝐶𝑖,𝑛+1 – штрафы за «невывоз» единицы продукта от производителя 𝑖 (затраты на хранение, контрактные обязательства и пр.).  Если штрафов нет, 𝐶𝑖,𝑛+1 = 0. ∗  𝒙𝒊,𝒏+𝟏 – объем продукта, который мы не вывозим от производителя 𝒊. 18 Дефицит m n  a  b i i 1 j 1 j  Вводят фиктивного поставщика Am1  «Запас» фиктивного поставщика – объем дефицита n m j 1 i 1 am1   b j   ai  Транспортные издержки 𝐶𝑚+1,𝑗 – штрафы за единицу неудовлетворенного спроса у потребителя 𝑗.  Если штрафов нет, 𝐶𝑚+1,𝑗 = 0. ∗  𝒙𝒎+𝟏,𝒋 – объем продукта, который не получит потребитель 𝒋 (неудовлетворенный спрос потребителя 𝑗). 19 Когда ТЗ необходимо балансировать?  В случае, если в задаче присутствуют штрафные затраты, связанные с «невывозом» или «недопоставками»;  В случае, когда имеются дополнительные ограничения, связанные с «неравноправностью» потребителей (или поставщиков) и т.п. 20 Преимущество сбалансированной модели «Поиск решения» автоматически выбирает специальные эффективные методы решения ТЗ и обеспечивает целочисленность решения (без специального требования целочисленности!) при условии, что заказы и запасы – целые. 21 Если ТЗ не балансировать 1. Меняется вид математической модели (часть равенств становится неравенствами). 2. ТЗ – задача целочисленного программирования. Необходимо добавлять условие целочисленности на переменные. 3. Для целочисленного программирования характерна проблема выбора начального решения. 22 Эвристические методы поиска допустимого решения ТЗ Понятие транспортной таблицы. с11 23 b1 с12 с13 c21 c22 c23 c24 c31 c32 c33 c34 b2 b3 с14 b4 a1 a2 a3 Эвристические методы поиска решения ТЗ  Метод северо-западного элемента.  Метод минимального элемента.  Приближенный метод Фогеля. 24 Метод северо-западного элемента Идея. В транспортной таблице всегда заполняется свободный северо-западный элемент.  Используется: только для нахождения начального допустимого решения. 25 Метод северо-западного элемента 7 5 8 6 2 26 9 1 1 3 0 9 1 11 6 9 11 8 2 8 7 3 5 5 8 6 3 4 3 5 7 7 0 30=30 Метод минимального элемента  Идея. В транспортной таблице всегда заполняется свободная клетка с минимальными затратами.  Используется: для нахождения начального допустимого решения и для оценки затрат. 27 Метод минимального элемента 7 8 3 1 2 28 9 1 8 3 0 9 11 4 3 0 9 11 6 2 8 3 5 5 6 3 7 4 6 5 5 1 0 7 0 30=30 Приближенный метод Фогеля  Идея. В строке (столбце) с максимальным штрафом заполняется клетка с минимальными затратами.  Используется: в основном, как оценочный метод. 29 Алгоритм метода Фогеля Вычислить штраф для каждой строки (столбца), вычитая наименьший элемент этой строки (столбца) из следующего за ним по величине элемента той же строки (столбца). 2. Отметить строку (столбец) с самым большим штрафом. В отмеченной строке или столбце выбрать переменную с самыми низкими затратами и придать ей наибольшее возможное значение. 3. Скорректировать объем производства и спрос. Вычислить новые штрафы. 4. Перейти к рассмотрению строки или столбца с максимальным штрафом. Если осталась одна строка (столбец), то заполнить ее в порядке возрастания затрат (по методу минимального элемента). 1. 30 Метод Фогеля 7 8 5 3 11 2 4 5 9 11 6 3 1 2 8 5 31 9 9 7 30=30 Метод Фогеля 7 8 3 2 5 5 0 6-2=4 32 1 4 6 6 5 9 3 0 4-3=1 8-4=4 7 5 3 3 9 1 8 9 1 0 5-1=4 5-5=0 2 7 0 3-2=1 9-3=6 11 4 11 6 8 30=30 5-3=2 4-2=2 5-4=1 2-1=1 Сравнение значений транспортных издержек № 33 Метод поиска решения Значение транспортной задачи 1 Северо-западного элемента 150 2 Минимального элемента 92 3 Фогеля 92 4 Оптимальное значение 89