prepod

Путь к Файлу: /индустриально-экономический колледж / Транспортная задача - постановка и оптимизация.doc

Ознакомиться или скачать весь учебный материал данного пользователя
Скачиваний:   0
Пользователь:   prepod
Добавлен:   16.04.2015
Размер:   252.5 КБ
СКАЧАТЬ

Министерство сельского хозяйства Российской Федерации

 

ФГОУ ВПО «Приморская государственная сельскохозяйственная академия»

 

Институт лесного хозяйства

 

 

 

 

 

 

 

 

Транспортная задача: постановка и оптимизация

 

Методические указания для выполнения практической работы по курсу «Организация, планирование и управление в лесном хозяйстве» для студентов  Института лесного хозяйства ПГСХА (специальность 250201).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Уссурийск  2007

 

 

 

 

Составитель: Усов В. Н. доцент каф. лесоводства.

УДК 630*6

 

 

 

 

 

 

 

 

 

Транспортная задача: постановка и оптимизация

  Методические указания для выполнения практической         работы по курсу «Организация, планирование и управление в лесном хозяйстве» для студентов  Института лесного хозяйства ПГСХА (специальность 250201)./Сост. В. Н. Усов.- Уссурийск: ПГСХА,2007.- 25 с.

 

 

 

 

 

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

 

 

 

 

Табл.10, Библиогр.5 назв.

 

 

 

 

 

.

 

 

Введение

 

Современная практика  управления предприятиями в различных отраслях народного хозяйства Российской Федерации  показывает, что одним из эффективных способов повышения эффективности  управления является применение экономико-математических методов планирования.

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

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

            Цель  самостоятельной работы:

· Ознакомление  студентов с постановкой транспортной задачи;

· Составление исходного варианта опорного плана транспортной задачи различными способами;

· Изучение  особенностей и порядка оптимизации транспортной задачи распределительным методом;

· Изучение  особенностей и порядка оптимизации транспортной задачи распределительным методом.

 

 

 

 

 

 

 

 

3

 

 

1.Постановка транспортной задачи

 

Общая постановка  транспортной задачи формулируется следующим образом. При заданных количествах некоторого однородного груза (а1, а2, …,аm) в пунктах отправления А1, А2, …Аm и заданных потребностях в этом грузе (в1, в2, …вп) в пунктах потребления В1, В2, …, Вп требуется определить объемы перевозок (х11, х12, …, хmn) из каждого пункта отправления в каждый пункт потребления таким образом, чтобы получить минимальное значение выбранной целевой функции: минимум  затрат на перевозку, минимальный пробег автотранспорта  и т. д.

            Формой решения транспортной задачи является матрица, с помощью которой определяются:

· Величина спроса и предложения на материалы, местонахождения производителей и потребителей;

· Издержки или прибыль, связанные с перемещением единицы груза от производителя к потребителю;

· Схемы маршрутов перевозки материалов.

Если соблюдается условие:   а1 + а2 + …+ аm  = в1 + в2 + …+ вп, задача относится  к закрытому типу. Если данное условие не выдерживается, задача является открытой. Для преобразования её в закрытую  вводятся фиктивные столбцы или строчки,  таким образом, чтобы условие равенства спроса и предложения выдерживалось. Если имеет место избыточное предложение продукции в матрицу вводится показатель фиктивного спроса. Объем фиктивного спроса равен разности между объемом наличного предложения и объемом требующегося предложения. Расходы по перевозке продукции от любого производителя фиктивному потребителю равны нулю. После оптимизации матрицы фиктивная продукция рассматривается как оставшаяся у производителя.  Количество поставщиков и потребителей, включаемых в матрицу, не ограничивается.

4

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

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

 

Таблица 1.1.

Матрица транспортной задачи

Грузоот-

правители

Грузополучатели

Запасы в пунктах отправления

 

 

Х11

 

С11

 
В1

 

 

С12

 
В2

 

 

С1n

 
Вn

A1

            Транспортная задача - постановка и оптимизацияТранспортная задача - постановка и оптимизация           

 

Х12

 

 
            Транспортная задача - постановка и оптимизацияТранспортная задача - постановка и оптимизацияТранспортная задача - постановка и оптимизацияТранспортная задача - постановка и оптимизация           

      …

 

 

     …

 

     …

 

 

   …            

 

 

   Х1n

 

 
Транспортная задача - постановка и оптимизацияТранспортная задача - постановка и оптимизация

Транспортная задача - постановка и оптимизацияТранспортная задача - постановка и оптимизацияТранспортная задача - постановка и оптимизацияТранспортная задача - постановка и оптимизация   

 

а1

A2

Транспортная задача - постановка и оптимизацияТранспортная задача - постановка и оптимизация          С21

Транспортная задача - постановка и оптимизацияТранспортная задача - постановка и оптимизация           С22

Транспортная задача - постановка и оптимизацияТранспортная задача - постановка и оптимизация

Транспортная задача - постановка и оптимизацияТранспортная задача - постановка и оптимизация          С2n

 

а2

 

 

Xm1

 
Транспортная задача - постановка и оптимизацияТранспортная задача - постановка и оптимизация      … 

Транспортная задача - постановка и оптимизацияТранспортная задача - постановка и оптимизация      …

Транспортная задача - постановка и оптимизацияТранспортная задача - постановка и оптимизация

Транспортная задача - постановка и оптимизацияТранспортная задача - постановка и оптимизация      …

        …

 

Аm

Транспортная задача - постановка и оптимизацияТранспортная задача - постановка и оптимизация           Cm1

 

Xm2

 
Транспортная задача - постановка и оптимизацияТранспортная задача - постановка и оптимизация         Cm2  Транспортная задача - постановка и оптимизацияТранспортная задача - постановка и оптимизация      

Транспортная задача - постановка и оптимизацияТранспортная задача - постановка и оптимизация

Xmn

 
Транспортная задача - постановка и оптимизацияТранспортная задача - постановка и оптимизация           Cmn

аm

Потребность в пунктах назначения

 

в1

 

в2

 

 

вn

 

 

            А1, А2, …, Аm – наименование отправителей грузов;

            а1, а2, ….аm – запасы грузов в пунктах отправления;

            В1, В2, … Вn – наименование получателей грузов;

            в1, в2, …вn – запасы грузов в пунктах назначения;

           

5

С11, С12, … Сmn – стоимость перевозки единицы груза из пунктов отправления в пункты назначения;

            Х11, Х12, …, Хmn – объем перевозимого груза из пунктов отправления в пункты назначения.

Целевая функция задачи равна

Транспортная задача - постановка и оптимизация            С11Х11 + С12Х12 + …. + СmnХmn                min.

В тех случаях когда транспортная задача имеет целевую функцию на максимум, например, максимум прибыли, целесообразно преобразовать её в задачу, имеющую минимальную целевую функцию. Для этого вводится величина относительных издержек. Относительные издержки рассчитываются как разность между значением прибыли по каждой клеточке матрицы и максимальным значением прибыли в данной матрице. Показателю максимальной прибыли соответствуют нулевые отрицательные расходы. Решение задачи сводится к минимизации относительных расходов. После нахождения оптимального решения относительные расходы пересчитываются в показатель прибыли.

 

 

2. Исходные данные для выполнения задания

 

В лесничестве имеется n непокрытых лесом участков, на которых предполагается создание лесных культур, плановая потребность в посадочном материале составляет в1, в2, …вn. Посадочный материал поставляется с временных  питомников А1, А2, …, Аm, где находится  а1, а2, ….аm посадочного материала соответственно. Из каждого питомника возможна доставка сеянцев на любую лесокультурную площадь, стоимость перевозки посадочного материала известна, она приведена в таблице 2.1.

 

 

 

6

Таблица 2.1.

Затраты на перевозку посадочного материала из временных питомников до лесокультурных площадей

Грузоотправители

Грузополучатели

В1

В2

В3

А1

2

6

4

А2

3

2

3

А3

1

4

2

А4

6

5

3

 

            а1 – 400 тыс. шт.,  а2 – 550 тыс. шт,  а3 – 700 тыс. шт,  а4 – 250 тыс. шт.

            в1 – 500 тыс. шт, в2 – 850 тыс. шт, в3 – 650 тыс. шт.

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

 

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

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

            Исходный план транспортной задачи может быть составлен несколькими методами:

1. Северо-западного угла;

2. Методом минимальных элементов;

3. Методом двойного предпочтения;

4. Методом аппроксимации.

3.1. Составление исходного плана методом северо-западного угла

            При составлении исходного плана по этому методу не обращая внимания на величину транспортных затрат (С11, С12,…, Сmn) производится :

7

· Распределение груза последовательно, начиная с грузоотправителя А1 затем А2 и т .д.;

· Обеспечивается грузом сначала первый потребитель В1, затем второй В2 и т. д.  (табл. 3.1.).

 

Таблица 3.1.

Исходная матрица для решения транспортной задачи, составленная методом северо-западного угла

 

Лесные

питомники

Лесокультурные площади

Итого в наличии

В1

В2

В3

А1

 

400

2

 

 

6

 

4

 

400

 

 

 

А2

 

100

3

 

450

2

 

3

 

550

 

 

 

А3

 

1

 

400

4

 

300

2

 

700

 

 

 

А4

 

6

 

5

 

350

3

 

350

 

 

 

Итого требуется

 

500

 

850

 

650

2000

 

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

 

8

 

но 4+3-1=6, что соответствует фактически полученному. Следовательно, матри

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

· Она достаточно велика для того чтобы считать клетку в которую она вписана занятой;

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

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

Целевая функция,  соответствующая затратам на перевозку грузов равна:

400·2 + 100·3 + 450·2 + 400·4 + 300·2 + 350·3 = 5350

 

3.2. Составление исходного плана методом минимальных элементов

            Сущность данного метода состоит в том, что на первой строке выбирается клеточка с наименьшими затратами на перевозку груза и в эту клеточку ставят наибольшую возможную поставку груза. Затем находят клеточку с минимальными затратами по второй строке и ставят в неё максимальную возможную поставку и так далее до последней строки. Оставшееся нераспределенным количество груза распределяют по оставшимся  клеткам логическим путем с учетом наименьших затрат. В результате такого распределения в нашем примере была построена матрица, показанная в табл. 3.2.

 

 

9

 

Таблица 3.2.

Исходная матрица для решения транспортной задачи, составленная методом минимальных элементов

 

Лесные

питомники

Лесокультурные площади

Итого в наличии

В1

В2

В3

А1

 

400

2

 

 

6

 

4

 

400

 

 

 

А2

 

 

3

 

550

2

 

3

 

550

 

 

 

А3

 

100

1

 

 

4

 

600

2

 

700

 

 

 

А4

 

6

 

300

5

 

50

3

 

350

 

 

 

Итого требуется

 

500

 

850

 

650

2000

 

План грузоперевозок, сформированный в данном случае, является не вырожденным. Целевая функция равна:

400·2 + 550·2 + 100·1 + 600·2 + 300·5 + 50·3 = 4850.

3.3. Составление исходного плана методом двойного предпочтения

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

 

 

 

10

Таблица 3.3.

Исходная матрица для решения транспортной задачи, составленная методом двойного предпочтения

 

Лесные

питомники

Лесокультурные площади

Итого в наличии

В1

В2

В3

А1

 

2

 

300

6

 

100

4

 

400

 

 

 

А2

 

 

3

 

550••

2

 

3

 

550

 

 

 

А3

 

500••

1

 

 

4

 

200••

2

 

700

 

 

 

А4

 

6

 

 

5

 

350•

3

 

350

 

 

 

Итого требуется

 

500

 

850

 

650

2000

 

Целевая функция по данной матрице равна:

300·6 + 100·4 + 550·2 + 500·1 + 200·2 + 350·3 = 5250.

3.4. Составление исходного плана методом аппроксимации

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

 

11

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

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

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

 

 

Таблица 3.4.

Исходная матрица для решения транспортной задачи, составленная методом аппроксимации

Лесные

питомники

Лесокультурные площади

Итого в наличии

Столбец разнос

тей

В1

В2

В3

А1

 

400

2

 

 

6

 

4

 

400

Транспортная задача - постановка и оптимизация

Транспортная задача - постановка и оптимизация 2, 0

 

 

 

А2

 

 

3

 

550

2

 

3

 

550

Транспортная задача - постановка и оптимизация

1, 0

 

 

 

А3

 

100

1

 

 

4

 

600

2

 

700

 

Транспортная задача - постановка и оптимизацияТранспортная задача - постановка и оптимизация 1, 2, 0

 

 

 

А4

 

6

 

300

5

 

50

3

 

350

 

Транспортная задача - постановка и оптимизация2, 0

 

 

 

Итого требуется

 

500

 

850

 

650

 

2000

 

Строка разностей

 

Транспортная задача - постановка и оптимизацияТранспортная задача - постановка и оптимизация 1, 2, 0

Транспортная задача - постановка и оптимизацияТранспортная задача - постановка и оптимизация

2, 1, 0

Транспортная задача - постановка и оптимизацияТранспортная задача - постановка и оптимизация

1,  1,0

 

 

 

            Целевая функция по данной матрице равна:

      400·2 + 550·2 + 100·1 + 300·4 + 300·2 + 350·3 = 4850.

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

 

4.Распределительный метод решения транспортной задачи

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

            Первоначально методом северо-западного угла составляется первый опорный план перевозок.

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

            Оптимизация или улучшение опорного плана грузоперевозок заключаются в возможности использовать свободные клетки вместо занятых, то есть в целесообразности перераспределения объемов перевозок между свободными и занятыми клетками. Эту возможность устанавливают при помощи проверки свободных клеток. Для этого строят замкнутые прямоугольные многоугольники (цепи), в которых в одном углу находится свободная клетка, а в

 

13

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

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

            Проверим возможность перераспределения грузов за счет пустых клеток. Проверка выполняется следующим образом. Через пустую клеточку   1.2 (первая строка второй столбец) строим цепочку (замкнутый контур) так, чтобы на одном углу была пустая клетка 1.2, а на других занятые клетки. Такой цепочкой будет ломаная линия, проходящая через клетки 1.2 – 2.2 – 2.1 – 1.1 – 1.2.  Фрагмент матрицы, включающий эти клетки, оказан в таблице  4.1.

Таблица 4.1.

Фрагмент матрицы, подлежащий улучшению

-

400

2

+

 

6

 

 

+

100

3

-

450

2

 

 

 

 

 

 

   

Производим численную оценку цепочки (замкнутого контура). Для этого всем угловым клеткам придаются алгебраические знаки «+» или «-». Свободной клетке всегда присваивается знак «+», далее знаки чередуются. Затем определяем сумму стоимостей перевозки по всем клеткам данной цепочки с учетом знака. Для клетки 1.2 она составит: Σ = +6-2+3-2 = +5.  Положительная сумма по

 

 

14

казывает, что перераспределение перевозок за счет свободной клетки 1.2 авто-

матически приведет к увеличению целевой функции на 5  единиц стоимости на каждую единицу перераспределенного груза. Следовательно, использование этой клетки для перераспределения грузоперевозок нецелесообразно.

            Рассмотрим возможность улучшения исходного плана за счет других клеток.

Цепочки для свободных клеток будут следующими:    

Клетка 1.3:          1.3 – 1.1 – 2.1 – 2.2 – 3.2 – 3.3 – 1.3

Клетка 2.3:          2.3 – 2.2 – 3.2 – 3.3 – 2.3

Клетка 3.1:          3.1 – 2.1 – 2.2 – 3.2 – 3.1

Клетка 4.1:        4.1 – 2.1 – 2.2 -3.2 – 3.3 – 4.3 – 4.1

Клетка 4.2:         4.2 – 3.2 – 3.3 – 4.3 – 4.2

Алгебраические суммы затрат на перевозку грузов с учетом знаков  составят:

Клетка 1.3:        +4 -2 +3 -2 +4 -2 = +5 

Клетка 2.3:        +3 -2 +4 -2          = +3 

Клетка 3.1:       +1 -3 +2 -4           = -4   

Клетка 4.1:       +6 -3 +2 -4 +2 -3 =  0  

Клетка 4.2:        +5 -4 +2 -3          = 0

Полученные результаты показывают, что улучшить план грузоперевозок можно только за счет клетки 3.1, при этом перераспределение единицы груза в клеточку 3.1  обеспечивает снижение целевой функции на 4 единицы стоимости. При перераспределении грузов в клетки 4.1 и 4.2 целевая функция останется на прежнем уровне, то есть мы получим альтернативные планы грузоперевозок.

            Для клетки 3.1, за счет которой можно оптимизировать план грузоперевозок, построим фрагмент матрицы (табл.4.2).

 

 

 

 

15

Таблица 4.2

Фрагмент матрицы до и после оптимизации

 

-

100

3

+

450

2

 

 

+

0

1

-

400

4

 

 

 

 

3

 

550

6

 

 

 

100

3

 

300

2

 

 

 

 

 

 

 

 

   Для перераспределения плана перевозок в клетках цепочки со знаком минус выбирают клетку с наименьшим объемом перевозки. В нашем примере это клетка 2.1 с объемом перевозок 100 тыс. шт.,  на эту величину уменьшаем все клетки цепочки, имеющие знак минус и увеличиваем все клетки, включая свободную, имеющие знак плюс. Общая сбалансированность плана при этом не изменится, а общая сумма затрат на перевозку уменьшится на 400 единиц.

            Для первоначального плана целевая функция по цепочке составляла:

         100·3 + 450·2 + 400·4  = 2800, а по новому плану: 100·1 + 550·2 + 300·4  = 2400.

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

 

 

 

 

 

 

 

 

 

16

Таблица 4.3.

Матрица транспортной задачи после первой итерации

 

 

Лесные

питомники

Лесокультурные площади

Итого в наличии

В1

В2

В3

А1

 

400

2

 

 

6

 

4

 

400

 

 

 

А2

 

 

3

 

550

2

 

3

 

550

 

 

 

А3

 

100

1

 

300

4

 

300

2

 

700

 

 

 

А4

 

6

 

5

 

350

3

 

350

 

 

 

Итого требуется

 

500

 

850

 

650

2000

 

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

            Данный метод сравнительно трудоемкий, он требует большого количества вычислений. В нашем примере в матрице 12 клеток из них 6 свободных, требующих проверки на оптимальность, если бы в матрице было 10 поставщиков и 10 потребителей, то количество занятых клеток было бы 19, а свободных 81. В матрице 20х20 занятых клеток 39, а свободных 361. Проверка такого количества клеток на оптимальность вручную является очень сложной.

 

5. Решение транспортной задачи методом потенциалов

 

17

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

            Потенциалы – произвольная система вспомогательных показателей, которые рассчитываются по следующему правилу:

Cij = Vi + Uj;

                                                     Vi  =  Cij - Uj;

                                                               Uj =  Cij - Vi.

   Условные обозначения:

                                                   I – номер строки;

                                                   J – номер столбца;

                                                  Vi – потенциал строки;

                                                   Uj– потенциал столбца;

                                                  Cij – затраты на перевозку груза по строке и столбцу.

Первоначально потенциалу любой строки или столбца придается нулевое значение. После этого  определяют потенциалы остальных строк и столбцов по занятым клеткам (табл. 5.1.).

 V1 = 0

 U1 = С11 - V1 = 2 - 0=2

 V2 = С21 -  U= 3 – 2 = 1

 U2 = С22 – V2 = 2 – 1 = 1

 V3 = С32 -  U= 4 – 1 = 3

 U3 = С33 – V3 = 2 – 3 = -1

 V3 = С43 -  U= 3 – (-1) = 4

18

При вырожденной матрице, когда число занятых клеток меньше, чем  m + n -1

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

 

Таблица 5.1.

Определение потенциалов строк и столбцов в исходной матрице

Лесные

питомники

Лесокультурные площади

Итого в наличии

Потенциал

Vi

В1

В2

В3

А1

 

400

2

 

 

6

 

4

 

400

Транспортная задача - постановка и оптимизация

0

 

 

 

А2

 

100

3

 

450

2

 

3

 

550

 

1

 

 

 

А3

 

 

1

 

400

4

 

300

2

 

700

 

3

 

 

 

А4

 

6

 

 

5

350

3

 

350

 

4

 

 

 

Итого требуется

 

500

 

850

 

650

 

2000

 

Потенциал

Uj

2

 

1

 

-1

 

 

 

 

            После нахождения потенциалов строк и столбцов проверяют свободные клетки на возможность перераспределения в них грузов. Для этого по всем свободным клеткам находится разница между показателем затрат на перевозку  Cij  и соответствующей ей суммой потенциалов строки Vi   и столбца  Uj.

Клетка 1.2:     6 – (0 + 1) = 5    

Клетка 1.3:     4 – (0 + (-1)) = 5;      

Клетка 2.3:     3 – (1 + (-1)) = 3;      

Клетка 3.1:     1- (2 + 3) = -4;  

19

Клетка 4.1:     6 – (2 + 4) = 0;

Клетка 4.2:     5 – (1 + 4) = 0.

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

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

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

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

1. Что такое опорный план, как он составляется.

2. Особенности составления исходного плана методом северо-западного угла.

3. Особенности составления исходного плана методом минимальных элементов.

20

4. Особенности составления исходного плана методом двойного предпочтения.

5. Особенности составления исходного плана методом аппроксимации.

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

7. Сущность распределительного метода решения транспортной задачи.

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

9. Алгоритм решения транспортной задачи методом потенциалов.

10. Порядок определения потенциалов.

11.  Порядок определения возможности оптимизации плана  грузоперевозок с помощью потенциалов.   

Глоссарий

1. Вырожденное решение – решение,  имеющее менее  m+n-1  распределений

2. Матрица (от нем. Matrize – основа, начало) – система элементов которые расположены в виде прямоугольной таблицы над которыми можно проводить различные алгебраические операции.

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

4. Оптимизация транспортной задачи – определение наиболее выгодных с очки зрения издержек маршрутов распределения грузов.

5. Объем  фиктивного спроса – разносить между объемом наличного предложения и объемом требующегося предложения.

6. Объем фиктивного предложения разность между объемом наличного спроса  и объемом требующегося спроса. 

 

 

 

 

21

Литература

 

1. Андреев В. Н., Герасимов Ю. Ю. Принятие оптимальных решений: теория и применение в лесном комплексе / В. Н. Андреев, Ю. Ю. Герасимов.- Йоэнсуу: изд-во университета Йоэнсуу, 1999.- 200 с.

2. Вентцель Е. С. Исследование операций. Задачи, принципы, методология / Е. С. Вентцель.- М.:Наука,1988.-206 с.

3. Глотов В. В. Экономико-математические методы планирования / В. В. Глотов. – М.: Лесная промышленность, 1980.- 160 с.

4. Новиков Г. И., Пермякова Э. И. Сборник задач по вычислительной технике и экономико-математическим методам / Г. И. Новиков, Э. И. Пермякова. – М.: Финансы и статистика, 1984.- 136 с.    

5. Перепелицкий  С. Н. Экономико-математические методы и модели в планировании и управлении на предприятиях лесной промышленности / С. Н. Перепелицкий.- М.: Лесная промышленность,1989.- 360 с.    

 

 

 

 

 

 

 

 

 

 

 

 

 

 

22

Содержание

 

Введение…………………………………………………………………………………………………………

1.Постановка транспортной задачи …………………………………………………………   4   

2. Исходные данные для выполнения задания………………………….6 

3. Методы составления исходного опорного плана…………………….7

3.1. Составление исходного плана методом северо-западного угла….7

3.2. Составление исходного плана методом минимальных элементов..9

3.3. Составление исходного плана методом двойного предпочтения..10

3.4. Составление исходного плана методом аппроксимации………….11

4.Распределительный метод решения транспортной задачи………….13

5. Решение транспортной задачи методом потенциалов………………17

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

Глоссарий………………………………………………………………...21    

Литература……………………………………………………………… 22 

Содержание………………………………………………………………23

 

 

 

 

 

 

 

 

 

 

 

 

 

23

 

 

 

 

Наверх страницы

Внимание! Не забудьте ознакомиться с остальными документами данного пользователя!

Соседние файлы в текущем каталоге:

На сайте уже 21970 файлов общим размером 9.9 ГБ.

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

Не нашли нужный документ? Воспользуйтесь поиском по содержимому всех файлов сайта:



Каждый день, проснувшись по утру, заходи на obmendoc.ru

Товарищ, не ленись - делись файлами и новому учись!

Яндекс.Метрика