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

 

                                 СОДЕРЖАНИЕ 

Введение 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) 

       

        ед.