Транспортная задача. 3

                                 СОДЕРЖАНИЕ 

Введение 3

1. Реальная постановка  задачи 4

2. Математическая  модель задачи  5

3. Определение  опорных планов 6 

4.Определение  оптимальных планов 13

5.Охрана труда 30

Список литературы 32

Приложение 33  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

ВВЕДЕНИЕ

   Линейные транспортные задачи  составляют особый класс  задач   линейного

программирования. Задача заключается  в  отыскании  такого  плана  перевозок

продукции  с  “m “ складов  в  пункт  назначения   “n”  который,  потребовал  бы

минимальных затрат. Если  потребитель “ j”   получает  единицу  продукции  (по

прямой  дороге) со склада “i”, то возникают  издержки Сij.  Предполагается,  что

транспортные  расходы  пропорциональны  перевозимому  количеству  продукции,

т.е. перевозка  “k” единиц продукции вызывает расходы  “k” С i j.

      Замечание.

      1. Если сумма  запасов   в   пунктах   отправления   превышает   сумму

поданных  заявок то количество  продукции, остается  на складах.  В  этом  случае  мы  введем  "фиктивного"  потребителя  (n  +1) с потребностью [pic] и положим транспортные расходы “pi”, (n+1) равными 0 для  всех “i”.

      2. Если сумма  поданных  заявок  превышает  наличные   запасы  [pic]то

потребность не может  быть  покрыта.  Эту  задачу  можно  свести  к  обычной

транспортной задаче с правильным  балансом,  если  ввести   фиктивный  пункт

отправления (m + 1) с  запасом  [pic] и  стоимость  перевозок  из   фиктивного

пункта  отправления  во  все  пункты  назначения  принять  равным  нулю. 
 
 
 
 
 
 
 
 
 
 
 
 

1 РЕАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ

         На строительство двухэтажного  особняка было выделено пять  групп лиц приехавших из нескольких  стран СНГ (15 человек из Молдовы, 47 человек из Украины, 71 человек  из Азербайджана, 28 человек из  Таджикистана, 33 человека из Узбекистана), которые выполняют четыре категории работ (укладка плитки, покраска стен, земельные работы, оштукатуривание стен, отделочные работы). Необходимо определить, сколько лиц, из какой группы, и на какую категорию работ назначить, чтобы суммарная производительность была максимальной. Известна производительность лиц стран СНГ при выполнении своей категории работ.

Матрица производительности: 

  C_ij=      

       i – группа лиц

       j – категория работ

         C_ij – производительность человека 
 
 
 
 
 
 
 
 
 
 
 

2 МАТЕМАТИЧЕСКАЯ МОДЕЛЬ

       Составим  математическую модель. Обозначим x₁₁ – количество строителей назначенных на первую категорию работ из первой группы, x_ij – количество строителей назначенных на j разновидности работ из i группы лиц.

       Запишем целевую функцию:

  (1)

          При ограничениях: 

                          (2)                                         

    X_ij ≥ 0                                                                         (3)                                                                                                                                                               

         Формулировка задачи.

       Найдем  max функции F(1) при выполнении условий(2) и (3). Для того, чтобы решить задачу как транспортную введем функцию (y) равную (– F)

       Найдем  минимум функции (у) при выполнении условий (2) и (3). 
 
 

3 ОПРЕДЕЛЕНИЕ ОПОРНОГО  ПЛАНА

       По  теореме разрешимости задача имеет  решение, если задача закрытая. Для  поверки задачи на разрешимость нужно найти сумму потребностей и сравнить её с суммой запасов, они должны быть равны друг другу.

       Так как ∑a_ij < ∑b_ij задача является открытой. Для того чтобы перейти к закрытой задаче нужно добавить фиктивный пункт назначения  B₅ с потребностями . Матрица планирования, содержащая фиктивную строку B₅, представлена в таблице 1.

       Найдем  опорный план транспортной задачи методом  Севера – Западного угла.

       На  каждом шаге заполняем одну клетку и считаем её занятой. Заполнение начинаем с клетки А₁В₁, при этом сравниваем величину запасов пункта отправления А₁ и величину потребностей  пункта назначения В₁ Наименьшее из них считаем перевозкой х₁₁= min (а₁, b₁) и записывают в клетку. Затем переходят к соседней клетки вправо или вниз, это зависит от того, полностью удовлетворены потребности или вывезены запасы, если полностью удовлетворены потребности и запасы, то переходим по диагонали, и так далее пока не дойдём до правой нижней клетки, при этом  остатки должны будут равны.

         На первом шаге мы сравниваем  потребности (В₁) и запасы (А₁) и присваиваем минимальное значение клетке х₁₁={18,15}=15,остались потребности (B₁) равные 3 переходим на нижнюю клетку, так как запасы (A₁) равны 0,  значения клеток х₁₂, х₁₃, х₁₄, х₁₅ равны нулю. На втором шаге сравниваем потребности (В₁) и запасы (А₂), присваиваем минимальное значение клетке х₂₁={3,47}=3, остались запасы (A₂) равные 44 переходим вправо, так как потребностей в пункте B₁ равны 0, то значения клеток х₁₃,х₁₄,х₁₅ равны нулю. На третьем шаге сравниваем потребности В₂ и запасы А₂ присваиваем минимальное значение клетке х₂₂={29,44}=29, остались запасы в пункте А₂ равные 15 переходим вправо, так как потребности в пункте В₂ равны 0, то значения  клеток х₃₂,х₄₂,х₅₂ равны нулю. На четвертом шаге сравниваем потребности В₃ и запасы А₂ присваиваем минимальное значение клетке х₂₃={34,15}=15, остались потребности в пункте В₃ равные 19 переходим к нижней клетке, так как запасы в пункте А₂ равны 0, то значения клеток х₂₄,х₂₅ равны нулю. На пятом шаге сравниваем потребности В₃ и запасы А₃ присваиваем минимальное значение клетке х₃₃={19,71}=19, остались запасы в пункте A₃ равные 52, переходим вправо, так как потребности в пункте B₃ равны 0, то значения клеток х₄₃,х₅₃ равны нулю. На шестом шаге сравниваем потребности В₄ и запасы А₃ присваиваем минимальное значение клетке х₃₄={51,52}=51, остались запасы в пункте А₃ равные 1, переходим вправо, так как потребности в пункте В₄  равны 0, то значение клеток x₄₄, х₅₄ равно нулю. На седьмом шаге сравниваем потребности В₅ и запасы А₃ присваиваем минимальное значение клетке х₃₅={62,1}=1, остались потребности В₅ равные 61,  переходим вниз, так как запасы в пункте А₃ равны 0. На восьмом шаге сравниваем потребности В₅ и запасы А_4, присваиваем минимальное значение клетке х₄₅={61,28}=28, остались потребности B₅ равны 33 переходим вниз. На девятом шаге сравниваем потребности В₅ и запасы А₅ присваиваем минимальное значение клетке х₅₅={33,33}=33, мы дошли до правой нижней клетки, запасы и потребности закончились.

         Постоим матрицу перевозок x_ij  (4)  и посчитаем целевую функцию.

         (4) 

        ед.

                                                                                                                    Таблица 1

       Найдём  опорный план данной задачи методом  Минимального Элемента.

Заполнение  клеток начинается с клетки с минимальным  тарифом, сравнивают запасы и потребности  на пересечение которых находится  клетка и переходят к клетке со следующем по величине тарифом.

       Для нахождения клетки с минимальным  тарифом создаём цикл прохождения  по клеткам таблицы 2. Первая клетка с минимальным тарифом это  клетка X₂₃  сравниваем запасы и потребности на пересечение этой клетки X₂₃={34,47}=34, остались запасы A₂ равные 13, так как потребности B₃ равны 0, то значения клеток X₁₃, X₃₃, X₄₃, X₅₃ равны нулю. Вторая клетка  с минимальным тарифом это клетка X₂₂,  сравниваем запасы и потребности на пересечение этой клетки X₂₂={29,13}=13, остались потребности B₃ равные 16, так как запасы A₂ равны 0, то значения клеток X₂₁, X₂₄, X₂₅ равны нулю. Третья клетка с минимальным тарифом это клетка X₄₂,  сравниваем запасы и потребности на пересечение этой клетки X₃₂={16,71}=55, остались запасы A₃ равные 55, так как потребности B₂ равны 0, то значения клеток X₁₂, X₄₂, X₅₂ равны нулю. Четвёртая клетка с минимальным тарифом это клетка X₄₄,  сравниваем запасы и потребности на пересечение этой клетки X₄₄={51,28}=28, остались потребности B₄ равные 23, так как запасы A₄ равны 0, то значения клеток X₄₁, X₄₂, X₄₃, X₄₅ равны нулю. Пятая клетка с минимальным тарифом это клетка X₃₁,  сравниваем запасы и потребности на пересечение этой клетки X₃₁={18,55}=18, остались запасы A₃ равные 37, так как потребности B₁ равны 0, то значения клеток X₁₁, X₁₅ равны нулю.  Шестая клетка с минимальным тарифом это клетка X₃₄,  сравниваем запасы и потребности на пересечение этой клетки X₃₄={23,37}=23, остались запасы A₃ равные 14, так как потребности B₄ равны 0, то значения клеток X₁₄, X₅₄ равны нулю. Оставшиеся запасы и потребности разлаживаем по оставшимся клеткам так, чтобы сумма тарифов не превышала количество запасов и потребностей: значение клетки  X₁₅ равна 15,  значение клетки  X₃₅ равна 14, значение клетки  X₅₅  равна 33.

         Постоим матрицу перевозок x_ij  (5)  и посчитаем целевую функцию.

         (5) 

        ед. 
 
 
 
 
 
 

                                                                                                                 Таблица 2

       Найдём  опорный план данной задачи методом  Двойного Предпочтения.

 Рассматриваются отдельно столбцы и строки и отмечают клетку с минимальным тарифом по столбцу и по строке. В результате часть клеток имеет две отметки, часть одну отметку и часть не одной. При просмотре таблицы сначала заполняют клетки с двумя отметками, потом с одной отметкой и потом клетки без отметок.  

 В результате просмотра таблицы 3: клетки X₂₃, X₄₄ имеют по две отметки, клетки X_13, X_21, X_22, X_32, X₅₃ имеют по одной отметке, остальные клетки не имеют ни одной отметки.

       Сначала заполняем клетки с двумя отметками. Первая клетка с минимальным тарифом  и двумя отметками это клетка X₂₃  сравниваем запасы и потребности на пересечение этой клетки X₂₃={34,47}=34, остались запасы A₂ равные 13, так как потребности B₃ равны 0, то значения клеток X₁₃, X₃₃, X₄₃, X₅₃ равны нулю. Вторая клетка с минимальным тарифом и двумя отметками это клетка X₄₄  сравниваем запасы и потребности на пересечение этой клетки X₄₄={51,28}=28, остались потребности B₄ равные 23, так как запасы A₄ равны 0, то значения клеток X₄₁, X₄₂, X₄₃, X₄₅ равны нулю.  Клеток с двумя отметками больше не осталось. Первая клетка с минимальным тарифом и с одной отметкой это клетка X₂₂  сравниваем запасы и потребности на пересечение этой клетки X₂₂={29,13}=13, остались потребности B₂ равные 16, так как запасы A₂ равны 0, то значения клеток X₂₁, X₂₄, X₂₅ равны нулю. Вторая клетка с минимальным тарифом и с одной отметкой это клетка X₃₂, сравниваем запасы и потребности на пересечение этой клетки X₃₂={16,71}=16, остались запасы A₃ равные 55, так как потребности B₂ равны 0, то значения клеток X₁₂, X₄₂, X₅₂ равны нулю. Клеток с одной отметкой больше не осталось. Первая клетка с минимальным тарифом без отметок это клетка X₃₁  сравниваем запасы и потребности на пересечение этой клетки X₃₁={18,55}=18, остались запасы A₃ равные 37, так как потребности B₁ равны 0, то значения клеток X₁₁, X₅₁ равны нулю. Вторая клетка с минимальным тарифом и без отметок это клетка X₃₄  сравниваем запасы и потребности на пересечение этой клетки X₃₄={23,37}=23, остались запасы A₃ равные 14, так как потребности B₄ равны 0, то значения клеток X₁₄, X₁₅ равны нулю. Оставшиеся запасы и потребности разлаживаем по оставшимся клеткам так, чтобы сумма тарифов не превышала количество запасов и потребностей: значение клетки  X₁₅ равна 15,  значение клетки  X₃₅ равна 14, значение клетки  X₅₅  равна 33.

         Постоим матрицу перевозок x_ij  (6)  и посчитаем целевую функцию.

         (6) 

        ед. 

       Таблица 3 

       Опорный план данной задачи решённый методом Северо-Западного угла является наиболее эффективным чем методом Двойного Предпочтения и метод Минимального Элемента. 
 
 
 
 
 
 
 
 
 
 
 

         ОПРЕДЕЛЕНИЕ ОПТИМАЛЬНОГО  ПЛАНА

       Метод потенциалов позволяет найти  оптимальный план транспортной задачи. Поиск оптимального плана начинают с нахождения какого-либо опорного плана,  затем его улучшают количество планов max (m+n-1). 

       Теорема оптимальности.

       Если  для некоторого опорного плана х^* существуют такие числа , , что при х_ij > 0,  при x_ij = 0, то план х^* является оптимальным, а числа и называются потенциалами (разность потенциалов равна тарифу для занятых клеток) (разность потенциалов меньше тарифов для целых клеток).  

       Алгоритм  методов потенциалов.

1. Находим опорный план любым методом (число занятых клеток должно быть  m+n-1).
2. Находим потенциалы
3. Для каждой свободной клетки определяют величину
4. Если среди чисел _j нет положительных, то план оптимален, если положительные числа есть, то план нужно улучшить, для этого среди чисел _j выбирают max.Для клетки, в которой стоит максимальное, строят цикл пересчета.

       Цикл  пересчета называется ломаная линия  вершины, которых расположены в  занятых клетках, а звенья вдоль  строк и столбцов.

         Производят сдвиг по построенному  циклу пересчета. 

       Правило сдвига- в каждой клетки, которая  находится в вершине цикла, приписывают знак «+» или « - » причем свободной «+», а остальным поочередно. Определяют минимальную перевозку отмеченную « - »  для получения нового опорного плана найденную перевозку прибавляем к числам в клетках «+» и вычитают из чисел в клетках « - ». Полученный план проверяют на оптимальность. 

       Возьмем опорный план найденный методом  Севера – Западного угла и определим, является ли данный опорный план оптимальным, и улучшим опорный план, если он не является оптимальным. Опорный план, рассчитанный методом Севера – Западного угла представлен в таблице 4.