РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ




 

Рассмотрим следующую задачу. Пусть имеется пунктов отправления с запасами товара соответственно и пунктов назначения , в каждый из которых следует доставить имеющийся товар в количестве соответственно. Известны затраты на перевозку единицы товара из i -го пункта отправления в j -й пункт назначения для , . Необходимо найти такой план перевозки товара, при котором транспортные расходы были бы минимальными, т. е. найти значения – количества товара, перевозимого из пункта отправления в пункт назначения , , для которых

.

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

РЕШЕНИЕ ТИПОВЫХ ЗАДАЧ

Потребности пяти райпо Гомельского облпотребсоюза в безалкогольных напитках, согласно их заявкам, составляют 12 тыс. бутылок, 14 тыс. бутылок, 12 тыс бутылок, 13 тыс. бутылок и 17 тыс. бутылок соответственно.

Поставку безалкогольных напитков осуществляют три производственных комбината, мощности которых позволяют выпускать 24 тыс. бутылок, 18 тыс. бутылок и 26 тыс. бутылок соответственно. Стоимость перевозки 1 тыс. бутылок (в условных единицах) с i -го промкомбината на склад (оптовую базу) j -го райпо равна элементу следующей матрицы:

.

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

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

Таблица 3.1

  Запасы
                     
         
                     
         
                     
         
Потребности            

 

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

1) вначале заполняется левая верхняя клетка таблицы (12 тыс. бутылок);

2) заполняются другие клетки первой строки слева направо до тех пор, пока не будут исчерпаны запасы груза в первом пункте отправления;

3) заполняются клетки второй строки таблицы, продолжая с первого слева столбца, соответствующего пункту назначения, потребности которого еще не удовлетворены;

4) аналогично заполняются и другие строки, пока не будет заполнена правая нижняя клетка таблицы.

Используя данный метод, получаем табл.3.2.

 

Таблица 3.2

  Запасы
                     
         
                     
         
                     
         
Потребности            

 

Затраты на перевозку составят

2*12+5*12+1*2+1*12+4*4+6*9+7*17=287 (у. е).

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

Опорный план, более близкий к оптимальному, как правило, можно получить, если воспользоваться методом минимального элемента. Суть метода заключается в том, что в первую очередь производится заполнение клеток таблицы с наименьшим тарифом (в нашей задаче – клеток с тарифом 1), где указывается максимально возможный объем перевозок. Далее выбираем клетки с минимальным тарифом из оставшихся. Их заполнение производится с учетом того, что в таблице уже имеются заполненные клетки. продолжая этот процесс, получаем табл. 3.3.

Таблица 3.3

Запасы
                     
         
                     
         
                     
         
Потребности            

 

Затраты на перевозку в данном случае составят

2*12+2*12+1*14+1*4+3*8+6*1+7*17=215 (у. е).

Таким образом, предлагаемый опорный план уменьшает стоимость перевозок на 287-215=72 (у. е) по сравнению с планом, полученным методом северо-западного угла.

Следующим этапом решения транспортной задачи является оптимизация найденного опорного плана. Рассмотрим оптимизацию плана методом потенциалов. При использовании этого метода важно, чтобы количество заполненных клеток таблицы было равно (в нашем случае 3+5-1=7 клеток). Если количество заполненных клеток оказалось меньшим, в свободные клетки таблицы следует дописать нули и считать эти клетки заполненными. При этом следует выбирать только те свободные клетки, для которых нельзя построить цикл. Под циклом для данной клетки понимают замкнутую ломаную, стороны которой получаются при соединении клеток таблицы, находящихся в одной строке или в одном столбце, причем вершины этой ломаной могут находиться только в данной клетке или в заполненных клетках таблицы.

Для построения нового улучшенного плана методом потенциалов обозначим потенциал i- й строки , а потенциал j- го столбца – . Далее, для всех заполненных клеток таблицы запишем уравнения вида

,

где – стоимость перевозки единицы груза из i -го пункта отправления в j -й пункт назначения. В результате получаем систему уравнений: Полагая , находим решения данной системы:

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

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

Таблица3.4

  Запасы
                     
         
         
-

4

     
+

 
         
         
+

     
-

 
         
Потребности            

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

Таблица 3.5

  Запасы
                     
         
                     
         
                     
         
Потребности            

 

Затраты на перевозку груза по этому составят

2*12+2*12+1*14+4*4+3*12+6*1+7*13=211 (у. е),

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

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

Полагая , решаем данную систему уравнений, откуда имеем:

, , , , , , , .

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

Таблица 3.6

  Запасы
                     
         
                     
         
                     
         
Потребности            

 

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

К ЭКЗАМЕНУ

ЗАДАНИЯ

 

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

4x1+x2 8 2x1+x2 6 x2 5 x1 0, x2 0 f =3x1+x2àmax   4x1+x2 8 2x1+x2 6 x2 5 x1 0, x2 0 f =x1+5x2àmax  
x1+x2 5 x1 4 x2 3 x1 0, x2 0 f =x1+3x2àmax x1+x2 5 x1 4 x2 3 x1 0, x2 0 f =x1-2x2àmax
  x1+x2 5 x1+3x2 12 2x1+3x2 8 x1 0, x2 0 f =x1+x2àmax   x1+x2 5 x1+3x2 12 2x1+3x2 8 x1 0, x2 0 f =3x1+x2àmax
  2x1+3x2 8 x1+3x2 18 x1 3 x1 0, x2 0 f =x1+x2àmax   2x1+3x2 8 x1+3x2 18 x1 3 x1 0, x2 0 f =2x1-x2àmax
  x1+x2 7 3x1+x2 15 x2 5 x1 0, x2 0 f =3x1+2x2àmax   x1+x2 7 3x1+x2 15 x2 5 x1 0, x2 0 f =3x1-x2àmax    

 

Решите транспортные задачи

  Запасы
                     
         
                     
         
                     
         
Потребности            

 

  Запасы
                     
         
                     
         
                     
         
Потребности            

 

Вопросы

 

1.Множество решений системы линейных неравенств с двумя переменными это-…?

2. Математическое программирование _

3. Целевая функция

3. Чем отличаются задачи линейного программирования и нелинейного?

4. Приведите пример задачи линейного программирования

5. Какой план называется оптимальным?

6. В каком случае используют графический метод решения задач линейного программирования?

7. В каком случае используют симплекс-метод?

8. В чем заключается симплекс-метод?

9.В чем заключается транспортная задача?

10.Какие методы решения транспортной задачи вы знаете и в чем они заключаются?

11.Решите задачи методом северо-западного угла

  Запасы
                 
       
                 
       
                 
       
Потребности          

 

  Запасы
                 
       
                 
       
                 
       
Потребности          

 

12.Решите задачи методом минимального элемента

  Запасы
                     
         
                     
         
                     
         
Потребности            

 

  Запасы
                     
         
                     
         
                     
         
Потребности            

 

9. В чем заключается оптимизация оптимального плана транспортной задачи?

10. Назовите условие необходимое при использовании метода потенциалов?

11. В каком случае говорят, что транспортная задача решена?

12. При каком условии план единственный?

 

 

ЛИТЕРАТУРА

 

1. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. - М.: Наука, 1965.

  1. Браверман Э.М. Математические модели планирования и управления в экономических системах. - М.: Наука, 1976.
  2. Вентцель Е.С. Исследование операций. - М.: Сов. Радио, 1972.
  3. Калихман И.Л., Войтенко М.А. Динамическое программирование в примерах и задачах. - М.: Высш. Шк., 1979.
  4. Капустин В.Ф. Практические занятия по курсу математического программирования. - Л.: Изд-во ЛГУ, 1976.
  5. Кузнецов А.В., Новикова Г.И., Холод Н.И. Сборник задач по математическому программированию. - Мн.: Высш. шк., 1985.
  6. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика: Математическое программирование. - Мн.: Высш. шк., 1994.
  7. Кузнецов А.В., Холод Н.И. Математическое программирование. - Мн.: Высш. шк., 1984.
  8. Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию - Мн.: Высш. шк., 1978.
  9. Сакович В.А. Исследование операций. - Мн.: Высш. шк., 1978.
  10. Сакович В. А. Модели управления запасами. - Мн.: Наука и техника, 1986.
  11. Сакович В. А. Оптимальные решения экономических задач. - Мн.: Высш. шк., 1982.
  12. СвамиМ., Тхуласираман К. Графы, сети и алгоритмы. - М.: Мир, 1984.

 

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-02 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: