6267

Управленческие решения в задачах распределительного типа

Реферат

Менеджмент, консалтинг и предпринимательство

Управленческие решения в задачах распределительного типа Содержание Примеры распределительных задач: транспортная и задача о назначениях. Постановка транспортной задачи и ее математическая модель. Методы построения плана перевозок Метод ...

Русский

2012-12-31

233.5 KB

12 чел.

Управленческие решения в задачах распределительного типа

Содержание

1. Примеры распределительных задач: транспортная и задача о назначениях.

2. Постановка транспортной задачи и ее математическая модель.

3. Методы построения плана перевозок

4. Метод потенциалов нахождения оптимального решения.

5. Множественность управленческих решений.

6. Управленческие решения в открытых задачах распределительного типа.

1. Примеры распределительных задач: транспортная и задача о назначениях

Пример №1

Условие: Студенческие отряды СО-1, СО-2 и СО-3 численностью 70, 99 и 80 человек принимают участие в сельскохозяйственных работах.

Для уборки картофеля на полях П1, П2, П3 и П4 необходимо выделить соответственно 47, 59, 49 и 43 человека. Производительность труда студентов зависит от урожайности картофеля, от численности отряда, характеризуется для указанных отрядов и полей в центнерах на человека за рабочий день и представлена в матрице:

                      Сумма = 198

Bj

Ai

П1

П2

П3

П4

47

59

49

43

СО-1

70

3

7

2

5

СО-2

99

2

3

4

6

СО-3

80

6

4

3

5

                Сумма = 249

Требуется:

  1.  Распределить студентов по полям так, чтобы за рабочий день было собрано максимально возможное количество картофеля;
  2.  Определить, сколько центнеров картофеля будет убрано с четырех полей при оптимальном распределении студентов.

Пример № 2

В пунктах отправления  находится однородный груз в количествах 400, 300, 500, который должен быть отправлен потребителям  в количествах 350, 250, 150, 250. Известны транспортные расходы (тарифы)  на перевозку единицы продукции из каждого пункта и себестоимость продукции в пунктах перевозки.

Найти план перевозок, при котором общая стоимость всего перевезенного груза (сумма затрат на доставку единицы продукции из соответствующего пункта и себестоимость продукции в этом пункте) будет наименьшей.

Поставщики 

Потребители  

Запасы аi

Себестоимость

В1

В2

В3

В4

350

250

150

250

А1

400

2

2

6

4

7

А2

300

3

6

2

7

1

А3

500

1

6

10

7

5

2. Постановка транспортной задачи и ее математическая модель

Экономическая постановка транспортной задачи

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

Известны транспортные расходы (тарифы)  на перевозку единицы продукции из каждого пункта   в пункт  , образующие матрицу транспортных расходов .

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

Математическая модель транспортной задачи

Обозначим через  количество груза, перевозимого из пункта  в пункт . План перевозок можно записать в виде матрицы .

По смыслу, переменные  неотрицательны:       .    (1)

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

 .          (2)

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

1) Если запас груза равен потребностям , то система ограничений примет вид:

, (условия вывоза имеющегося груза)  (3)

. (условия доставки требуемого груза)   (4)

2) Если запас груза больше потребностей , то все потребности будут удовлетворены, но не все запасы будут вывезены, и условие вывоза примет вид

.      (3*)

3) Если же запас груза меньше потребностей , то все запасы будут вывезены, но не все потребности будут удовлетворены, и условие доставки груза примет вид

.        (4*)

Математическая постановка транспортной задачи:

среди множества неотрицательных решений системы  линейных уравнений (3) и (4) найти такое решение , при котором линейная функция (2) принимает минимальное значение.

  •  План перевозок  называется допустимым, если он удовлетворяет ограничениям (1), (3), (4).
  •  Допустимый план перевозок, доставляющий минимум целевой функции , называется оптимальным.

Обычно данные транспортной задачи записывают в виде распределительной таблицы (таблица 1).

Таблица 1

Запасы груза

Потребности в грузе

b1

b2

...

bn

a1

c11

x11

c12

x12

...

c1n

x1n

a2

c21

x21

c22

x22

...

c2n

x2n

...

...

...

...

...

am1

cm1

xm1

cm2

xm2

...

cmn

xmn

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

                               (5)

В этом случае транспортная задача называется сбалансированной, а модель - закрытой. Если же это равенство не выполняется, то задача называется несбалансированной (с неправильным балансом), а её модель – открытой.

Если транспортная задача открытая, то необходимо добавить фиктивного поставщика (или потребителя) с недостающим объемом поставки и нулевой стоимостью перевозки. Распределение поставки фиктивному потребителю (поставщику), идет в последнюю очередь.

Транспортные задачи решаются с помощью общего приема последовательного улучшения плана перевозок. Он включает в себя следующие этапы:

  1.  Построение исходного плана перевозок.
  2.  Проверка плана перевозок на оптимальность.
  3.  Улучшение плана перевозок.

3. Методы построения плана перевозок

Рассмотрим два метода построения первоначального плана перевозок в распределительной таблице.

Метод "северо-западного угла".

  1.  Будем распределять груз, начиная с верхней левой клетки, условно называемой северо-западной: в клетку (1.1) заносят число, минимальное из чисел  и , т.е. .
  2.  Если , то  и потребности пункта  полностью удовлетворены. После этого заполняется клетка (1.2) числом .
  3.  Если же , то  и запас груза в  полностью исчерпан. После этого заполняется клетка (2.1) числом .
  4.  Процесс продолжается до тех пор, пока не исчерпаются все ресурсы  и полностью не будет удовлетворен спрос . Последней заполняется клетка .

Незаполненным клеткам таблицы соответствуют значения переменных  (свободные переменные), а заполненным - значения переменных  (базисные переменные).

Число заполненных кленок в опорном плане перевозок должно быть ровно . Если в процессе заполнения таблицы одновременно исчерпывается запас груза и полностью удовлетворен спрос (одновременно исключается строка и столбец), то в какую-либо свободную клетку надо условно считать занятой. Для этого в нее нужно вписать число 0, но чтобы эта клетка не образовала цикла с ранее занятыми клетками.

Метод "минимального элемента". 

  1.  Сбалансировать задачу (убедиться, что ТЗ закрытая).
  2.  Определить свободную клетку с наименьшей стоимостью перевозки. Если таких клеток несколько, то выбрать клетку с наибольшей потенциальной грузоперевозкой. Если и таких клеток несколько, то выбирается любая из этих клеток.
  3.  В выбранную клетк
  4.  у поставить максимально возможную грузоперевозку для потребителя от поставщика.
  5.  Из оставшихся клеток таблицы снова выбирают клетку с наименьшим тарифом. Процесс распределения груза заканчивается, когда все запасы поставщиков исчерпаны, а спрос потребителей полностью удовлетворен.
  6.  В результате получаем опорный план, который должен содержать  заполненных клеток.

Задача 1. Приведем в качестве примера два плана перевозок транспортной задачи: первый построен по методу "северо-западного угла" (табл.2), второй - методом "минимального элемента" (табл.3).

Таблица 2 - План перевозок по методу «северо-западного угла»

Запасы груза

Потребности в грузе

120

50

190

110

160

7

120

8

40

1

2

140

4

5

10

9

130

8

170

9

2

3

60

6

110

Клетки заполнялись в последовательности: (1.1), (1,2), (2,2), (2,3), (3,3), (3,4). План перевозок имеет вид .

Стоимость перевозок по плану "северо-западного угла" равна

ден. ед.

Таблица 3 - План перевозок по методу "минимального элемента".

Запасы груза

Потребности в грузе

120

50

190

110

160

7

8

1

160

2

140

4

120

5

9

8

20

170

9

2

50

3

30

6

90

Клетки заполнялись в последовательности: (1,3), (3,2), (3,3), (2,1), (3,4), (2,4). Стоимость перевозок по плану "минимального элемента"  равна

ден. ед.

Так как 1530 < 3220, то план перевозок, построенный по методу "минимального элемента", лучше, чем план, построенный по методу "северо-западного угла".

4. Метод потенциалов нахождения оптимального решения

1) Каждому поставщику ставится в соответствие число , потребителю - число , называемые потенциалами. Значения потенциалов подбираются так, чтобы для всех  заполненных клеток  выполнялись условия

.    (6)

Выбрать переменную  или , которой соответствует наибольшее количество занятых клеток, приравнять её к нулю, решить систему уравнений относительно  и  и найти эти значения.

2) Для всех свободных клеток составить и проверить выполнение условия оптимальности плана перевозок

    (7)

Если для всех свободных клеток выполняется это неравенство, то тогда найден оптимальный план.

Если хотя бы для одной клетки не выполняется это неравенство, то необходимо улучшить опорный план с помощью коэффициента перераспределения .

3) Находим клетку, где больше всего не выполняется неравенство. Если таких клеток несколько, то выбирается любая. В эту клетку ставим  со знаком «+».

4) Построить «цикл» (контур перераспределения груза), начиная с выбранной клетки, исходя из следующих правил:

  •  В строке и столбце должно быть четное количество ;
  •  Контур меняет направление только в базисных клетках (заполненных);
  •  Коэффициент  меняет свой знак с «+» на «-» поочередно в углах контура.
  1.  После построения контура (цикла) отметить, в каких заполненных клетках коэффициент  стоит с отрицательным знаком. Из этих клеток найти клетку с наименьшим значением перевозки, коэффициент  будет равен перевозке в выбранной клетке. Найти новый план, перераспределив найденное значение  по контуру с учетом знаков «+» и «-», прибавляя или уменьшая стоящую в клетке перевозку. Это число  прибавляем к поставкам в клетках со знаком "+" и вычитаем это же число  из поставок в клетках со знаком "–".
  2.  Проверить новый план на  оптимальность в соответствии в п.2. Если неравенства не выполняются, то повторяются действия, начиная с пункта 3.
  3.  Если неравенства для свободных клеток выполняются, значит найденный план оптимален. Вычисляется стоимость оптимального плана перевозок.

Замечания.

  •  Для любой свободной клетки можно построить только один цикл.
  •  Потенциалы, как и циклы, для каждого решения определяются заново.
  •  Если при перемещении по циклу числа  освободится сразу несколько клеток, то одну из освобождающихся клеток (которой соответствует наибольшая стоимость перевозок ) оставляют свободной, а другие заполняют нулями (получается так называемое вырожденное решение).
  •  При переходе от решения  к решению  значение целевой функции изменится на величину       (8), где  - число, перемещаемое по циклу, составленному для клетки  с отрицательной оценкой .

Задача 2. Решить транспортную задачу.

Таблица 4

Запасы груза

Потребности в грузе

300

500

100

200

100

3

6

5

1

400

1

4

3

2

600

4

3

1

2

Решение

1) Проверим условие разрешимости транспортной задачи:

;   .

Таким образом, ТЗ закрытая и, следовательно, имеет оптимальное решение.

2) Запишем математическую модель ТЗ.

Обозначим через  количество перевезенного груза из  () в  (), при этом . Составим систему ограничений:

условия вывоза груза

условия доставки груза

Суммарные затраты на перевозку груза равны

.

Требуется найти такое неотрицательное решение  системы ограничений, при котором функция  принимает наименьшее значение.

3) Построим исходное опорное решение  методом «минимального элемента». 

Последовательность заполнения клеток в распределительной таблице следующая: (2,1), (1,4), (3,3), (3,4), (3,2), (2,2).

    Таблица 5

Запасы груза

Потребности в грузе

300

500

100

200

100

3

6

5

1

100

400

1

4

3

2

300

100

600

4

3

1

2

400

100

100

В плане перевозок  число заполненных клеток равно m + n – 1 = 3 + 4 – 1 = 6. Транспортные расходы составляют .

4) Найдем потенциалы  и .

Найдем потенциалы  и  из системы уравнений, составленных для заполненных клеток.

В системе число уравнений  меньше числа неизвестных , поэтому система имеет бесконечное множество решений, при этом число свободных неизвестных равно 7 – 6 = 1.

Придадим неизвестной  (она чаще всего встречается в системе) произвольное значение. Тогда остальные потенциалы равны:

; ; ; ; ; ; .

5) Проверим решение  на оптимальность.

Вычислим оценки свободных переменных, соответствующих свободным клеткам:

11 = с11 + 1 1 = 3 + 1 – 0 = 4;

12 = с12 + 1 2 = 6 + 1 – 3 = 4;

13 = с13 + 1 3 = 5 + 1 – 1 = 5;

23 = с23 + 2 3 = 3 –1 – 1 = 1;

24 = с24 + 2 4 = 2 – 1 – 2 = – 1;

31 = с31 + 3 1 = 4 + 0 – 0 = 4.

Оценка , поэтому план перевозок  не оптимален и транспортные расходы не являются наименьшими.

6) Улучшим план перевозок.

Построим для клетки (2,4) в таблице 5 замкнутый цикл: (2,4), (2,2), (3,2), (3,4). Припишем знаки «+» и «–» вершинам цикла, начиная с клетки (2,4), последовательно чередуя их. Найдем число  и переместим его по циклу: вычтем 100 из значений отрицательных клеток и прибавим 100 к значениям положительных. В результате клетка (2,4) стала занятой, , а две клетки (2,2) и (3,4) освободились.

    Таблица 6

Запасы груза

Потребности в грузе

300

500

100

200

100

3

6

5

1

100

400

1

4

3

2

300

100

600

4

3

1

2

400

100

100

В новом плане перевозок заполненных клеток 5, а должно быть . Из двух освободившихся клеток (3,4) и (2,2) заполним базисным нулем клетку (3,4), так как ей соответствует меньшая стоимость перевозок  , а клетку (2,2) оставим свободной.

   Таблица 7

Запасы груза

Потребности в грузе

300

500

100

200

100

3

6

5

1

100

400

1

4

3

2

300

100

600

4

3

1

2

500

100

0

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

Проверим правильность расчетов, используя формулу (11.7):

.

7) Проверим решение  на оптимальность.

Найдем потенциалы  и  из новой системы уравнений, составленных для заполненных клеток таблицы 7:

При  получим одно из решений этой системы:

a1 = 1,  a2  = 0,  a3 = 0,  1 = 1,  2 = 3,  3 = 1,  4 = 2.

Все оценки свободных переменных положительны:

11 = с11 + 1 - 1 = 3 + 1 – 1 = 3;

12 = с12 + 1 - 2 = 6 + 1 – 3 = 4;

13 = с13 + 1 - 3 = 5 + 1 – 1 = 5;

23 = с23 + 2 - 3 = 3 + 0 – 1 = 2;

22 = с22 + 2 - 2 = 4 + 0 – 3 = 1;

31 = с31 + 3 - 1 = 4 + 0 –1 = 3.

Отсутствие отрицательных оценок является признаком оптимальности плана перевозок , при котором значение целевой функции минимально и равно .

8) Дадим экономическое истолкование оптимального решения. 

Для того, чтобы затраты на перевозку груза из пунктов , ,  были наименьшими и составляли 2200, нужно отправить: 1) 100 ед. груза из  в ; 2) 300 ед. груза из  в  и 100 ед. из  в ; 3) 500 ед. груза из  в  и 100 ед. груза из  в .

5. Множественность управленческих решений

Наличие нулевых оценок свободных переменных для оптимального плане перевозок является признаком того, что задача имеет альтернативный оптимум (множественность оптимальных решений).

В каком-либо оптимальном плане для каждой свободной клетки с нулевой оценкой строят цикл и перемещают по нему соответствующее число , в результате получают набор оптимальных решений .

Общее оптимальное решение есть линейная выпуклая комбинация оптимальных решений:

 где             (9)

6. Управленческие решения в открытых задачах распределительного типа

Транспортная задача называется открытой, если .

1) Пусть для ТЗ выполняется условие  (общие запасы груза  меньше суммарных потребностей).

Для решения ТЗ она приводится к закрытому виду: вводится фиктивный поставщик  с "запасом" груза  и нулевыми тарифами на перевозку груза от поставщика  ко всем потребителям : . В распределительную таблицу добавляется снизу ()-я строка, в которой запасы груза равны , а тарифы на перевозку .

В оптимальном плане перевозок данной открытой ТЗ загрузка любой клетки для фиктивного поставщика указывает на недопоставку груза соответствующему потребителю .

2) Пусть для ТЗ выполняется  (общие запасы груза  больше суммарных потребностей).

Для приведения ТЗ к закрытому виду вводится фиктивный потребитель  с "потребностью" в грузе  и нулевыми тарифами на перевозку груза от всех поставщиков  к потребителю , т.е. . В распределительную таблицу добавляется справа ()-й столбец, в котором потребность в грузе равна , а тарифы на перевозку к фиктивному потребителю .

В оптимальном плане перевозок такой ТЗ загрузка любой клетки для фиктивного потребителя указывает на остаток нераспределенного груза у соответствующего поставщика .


Контрольные вопросы

  1.  Дайте экономическую постановку транспортной задачи (ТЗ) по критерию стоимости.
  2.  Какая транспортная задача называется: 1) закрытой; 2) открытой?
  3.  Сколько переменных  содержит математическая модель закрытой ТЗ?
  4.  Запишите математическую модель закрытой ТЗ по критерию стоимости, дайте экономическое истолкование переменным, ограничениям и целевой функции.
  5.  Опишите правило преобразования открытой модели ТЗ в закрытую ТЗ, если 1) ; 2) .
  6.  Опишите построение в распределительной таблице исходного плана перевозок методом “северо-западного угла”. Сколько заполненных клеток должно быть в распределительной таблице и как этого достичь?
  7.  Опишите построение в распределительной таблице исходного опорного плана перевозок методом “минимального элемента”.
  8.  Опишите сущность метода потенциалов нахождения оптимального плана перевозок ТЗ.
  9.  Сформулируйте признак оптимальности плана перевозок ТЗ, решаемой методом потенциалов.
  10.  С какой целью и как строится цикл пересчета в распределительной таблице, если план перевозок не является оптимальным? Как определяется загрузка свободной клетки, с помощью которой происходит перемещение груза по циклу?
  11.  Запишите формулу для вычисления оценок свободных переменных в ТЗ.
  12.  Как вычислить изменение целевой функции  при улучшении плана перевозок?
  13.  Сформулируйте признак альтернативного оптимума в ТЗ. Как найти в этом случае общее оптимальное решение?
  14.  Каков экономический смысл неравенства ? Составьте математическую модель этой ТЗ. Опишите процесс решения данной открытой транспортной задачи.
  15.  Каков экономический смысл неравенства ? Составьте математическую модель этой ТЗ. Опишите процесс решения данной открытой транспортной задачи.
  16.   Каков экономический смысл дополнительных переменных в оптимальном плане перевозок открытых транспортных задач, если 1) , 2) ?


 

А также другие работы, которые могут Вас заинтересовать

11929. Измерение диэлектрической проницаемости и угла диэлектрических потерь твердых диэлектриков 475 KB
  ЛАБОРАТОРНАЯ РАБОТА № 2 Измерение диэлектрической проницаемости и угла диэлектрических потерь твердых диэлектриков Цель работы: изучить основные электрические свойства диэлектрических материалов и их характеристики. ПРОГРАММА РАБОТЫ 1. Ознакомиться с образ...
11930. Исследование зависимости тангенса угла диэлектрических потерь и диэлектрической проницаемости от температуры 420 KB
  ЛАБОРАТОРНАЯ РАБОТА № 3 Исследование зависимости тангенса угла диэлектрических потерь и диэлектрической проницаемости от температуры Цель работы: исследовать зависимость тангенса угла диэлектрических потерь и диэлектрической проницаемости от температуры. ...
11931. Определение удельного сопротивления проводников 120 KB
  ЛАБОРАТОРНАЯ РАБОТА № 4 Определение удельного сопротивления проводников Цель работы: изучить основные электрические свойства проводниковых материалов и их характеристики. ПРОГРАММА РАБОТЫ 1. Ознакомиться с образцами проводниковых материалов. 2. Изучить осн...
11932. Конституционное право. Конституция 49.34 KB
  Конституционное право как отрасль российского права берет свое начало от понятия «конституция». Конституции как основной закон государства появились в конце XVIII века. Первая конституция была принята в 1787 г. в США. В Европе первые конституции были приняты в 1791 г. во Франции и в Польше.
11933. Определение электрической прочности трансформаторного масла 153 KB
  ЛАБОРАТОРНАЯ РАБОТА № 2 Определение электрической прочности трансформаторного масла ПРОГРАММА РАБОТЫ Усвоить методику электрического испытания трансформаторного мала. Произвести стандартное испытание масла на электрическую прочность. Определить ...
11934. Исследование магнитных свойств ферромагнитных материалов 291.5 KB
  ЛАБОРАТОРНАЯ РАБОТА № 3 Исследование магнитных свойств ферромагнитных материалов ПРОГРАММА РАБОТЫ 1. Изучить основные магнитные характеристики ферромагнитных материалов. 2. Снять динамическую кривую намагничивания ферромагнетика по методу вольтметра и ампе
11935. Исследование электрических свойств проводниковых материалов 824 KB
  ЛАБОРАТОРНАЯ РАБОТА № 4 Исследование электрических свойств проводниковых материалов ПРОГРАММА РАБОТЫ 1. Познакомиться с основными проводниковыми материалами применяемыми в энергетике. 2. Изучить основные электрические свойства проводниковых материалов. 3...
11936. Измерение диэлектрической проницаемости и тангенса угла диэлектрических потерь твердых диэлектриков 85.5 KB
  ЛАБОРАТОРНАЯ РАБОТА № 5 Измерение диэлектрической проницаемости и тангенса угла диэлектрических потерь твердых диэлектриков Цель работы: проверить опытным путем значения диэлектрической проницаемости εr и тангенса угла диэлектрических потерь tg δ некоторых элект...
11937. Исследование свойств модели резисторного каскада с общим эмиттером в частотной и временной областях на ПК 479.12 KB
  Лабораторная работа №1. Исследование свойств модели резисторного каскада с общим эмиттером в частотной и временной областях на ПК. 1.Цель работы: Изучить свойства каскада ОЭ в режиме малого сигнала в частотной и временной областях. Исследовать влияние сопр