Logo GenDocs.ru

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

Загрузка...

Контрольная работа - файл 3 Транспортная задача.doc


Загрузка...
Контрольная работа
скачать (1273 kb.)

Доступные файлы (5):

1 Графический метод решения задач линейного программирования.doc488kb.27.09.2008 16:04скачать
2 Линейное программирование.doc1049kb.28.09.2008 18:29скачать
3 Транспортная задача.doc770kb.28.09.2008 18:31скачать
4 Динамическое программирование и сетевое планирование.doc299kb.28.09.2008 18:31скачать
Прочитай.txt1kb.28.11.2008 14:06скачать

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

  1   2   3
Реклама MarketGid:
Загрузка...
3. Транспортная задача
Задание:

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

Предприятия-изготовители А1, А2, А3 могут поставлять ежедневно по а1, а2, а3 контейнера соответственно. Предприятиям-потребителям В1, В2, В3 и В4 требуется соответственно по b1, b2, b3 и b4 контейнеров комплектующих деталей. Затраты на перевозку одного контейнера (в тыс.руб) завода-поставщика А1, к заводам потребителям В1, В2, В3 и В4 равны С11, С12, С13, С14 соответственно; для А2 – С21, С22, С23, С24; для А3 - С31, С32, С33, С34.

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

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

  2. Минимального элемента;

  3. Аппроксимации Фогеля;

  4. Доказать оптимальность методом потенциалов.

Дано:

а1

а2

а3

b1

b2

b3

b4

100

70

30

10

40

80

70

Запас продукции для ежедневной поставки у предприятий-изготовителей А1, А2, А3

Ежедневная потребность предприятий-потребителей В1, В2, В3 и В4






















С11

С12

С13

С14

С21

С22

С23

С24

С31

С32

С33

С34

2

1

1

3

4

2

3

1

1

4

2

1

Затраты на перевозку для предприятия А1

Затраты на перевозку для предприятия А2

Затраты на перевозку для предприятия А3






































Решение:



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

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

Цель – минимизация суммарной стоимости всех перевозок.

Т.к. общий запас продукции (200 контейнеров) = общей потребности потребителей (200 контейнеров), то наша транспортная задача считается закрытой.

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

х11, х12, х13, х14 – кол-во контейнеров поставленных производителем А1 каждому из 4-х потребителей;

х21, х22, х23, х24 – кол-во контейнеров поставленных производителем А2 каждому из 4-х потребителей;

х31, х32, х33, х34 – кол-во контейнеров поставленных производителем А3 каждому из 4-х потребителей;

Выражаем через введенные неизвестные суммарную стоимость перевозок в виде линейной функции (целевая функция).



где - кол-во контейнеров от поставщика i к потребителю j или .

Матрица стоимостей:

Ограничения функции:

  • вывоз продукции от поставщика = запас продукции у поставщика:

- для поставщика А1;

- для поставщика А2;

- для поставщика А3;


  • привоз продукции к потребителю = потребности потребителя:

- для потребителя В1;

- для потребителя В2;

- для потребителя В3;

- для потребителя В4;


  • условие неотрицательности:


Математическая постановка:

- целевая функция;
Ограничения функции:

;



Построение начального плана:







n - столбцов










Цены перевозок




запасы у поставщиков

100

2

1

1

3

m - строк

70

4

2

3

1

30

1

4

2

1







10

40

80

70










потребности потребителей







  1. ^ Метод Северо-Западного угла (СЗУ):




    1. Выбираем северо-западную клетку (1,1)

      1

      100

      2



      1

      1

      3

      2

      70

      4

      2

      3

      1

      3

      30

      1

      4

      2

      1







      10

      40

      80

      70







      1

      2

      3

      4

    2. Назначаем перевозку:

      1

      100

      10










      2

      70













      3

      30



















      10

      40

      80

      70







      1

      2

      3

      4

    3. Уменьшаем запасы поставщика

и потребности потребителя

1

90

10










2

70













3

30



















X

40

80

70







1

2

3

4




    1. Т.к. потребность 1-го потребителя исчерпана, то перевозки ему запрещаем (исключаем 1-й столбец):

1

90

10










2

70

-










3

30

-
















Х

40

80

70







1

2

3

4




    1. Далее повторяем шаги 1-4 до тех пор, пока не исключатся все столбцы-строки:

      • Выбираем северо-западную клетку (1,2)

      • Назначаем перевозку:

      • Уменьшаем запасы поставщика

      • и потребности потребителя

      • Т.к. потребность 2-го потребителя исчерпана, то перевозки ему запрещаем (исключаем 2-й столбец):

1

50

10

40







2

70

-

-







3

30

-

-













Х

Х

80

70







1

2

3

4




      • Выбираем северо-западную клетку (1,3)

      • Назначаем перевозку:

      • Уменьшаем запасы поставщика

      • и потребности потребителя

      • Т.к. запасы 1-го поставщика исчерпана, то перевозки ему запрещаем (исключаем 1-ю строку):

        1

        Х

        10

        40

        50

        -

        2

        70

        -

        -







        3

        30

        -

        -













        Х

        Х

        30

        70







        1

        2

        3

        4

      • Выбираем северо-западную клетку (2,3)

      • Назначаем перевозку:

      • Уменьшаем запасы поставщика

      • и потребности потребителя

      • Т.к. потребность 3-го потребителя исчерпана, то перевозки ему запрещаем (исключаем 3-й столбец):

        1

        Х

        10

        40

        50

        -

        2

        40

        -

        -

        30




        3

        30

        -

        -

        -










        Х

        Х

        Х

        70







        1

        2

        3

        4

      • Выбираем северо-западную клетку (2,4)

      • Назначаем перевозку:

      • Уменьшаем запасы поставщика

      • и потребности потребителя

      • Т.к. запасы 2-го поставщика исчерпана, то перевозки ему запрещаем (исключаем 2-ю строку):

        1

        Х

        10

        40

        50

        -

        2

        Х

        -

        -

        30

        40

        3

        30

        -

        -

        -










        Х

        Х

        Х

        30







        1

        2

        3

        4

      • Выбираем северо-западную клетку (3,4)

      • Назначаем перевозку:

      • Уменьшаем запасы поставщика

      • и потребности потребителя

      • Таблица полностью исчерпана:

1

Х

10

40

50

-

2

Х

-

-

30

40

3

Х

-

-

-

30







Х

Х

Х

Х







1

2

3

4




    1. Считаем стоимость полученного плана. Для этого умножаем объем перевозок в заполненных клетках на стоимость перевозок в этих же клетках.

1

Х

10

2

40

1

50

1

-

3

2

Х

-

4

-

2

30

3

40

1

3

Х

-

1

-

4

-

2

30

1







Х

Х

Х

Х







1

2

3

4


(тыс.руб)

^ Проверка оптимальности:

Признаком оптимальности по методу потенциалов является условие:

(Y1) которое выполняется для всех клеток таблицы,

потенциалы и определяются из условий:

(Y2) , для заполненных клеток (i , j) таблицы.

Пусть :



0

10

2

40

1

50

1

-

3






-

4

-

2

30

3

40

1






-

1

-

4

-

2

30

1

































Из условия (Y2) запишем:



,

По таблице считаем:



; ;
Аналогично:












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

(Y1)


Незаполненная клетка

Выполнение условия




(1,4)



условие соблюдается

(2,1)



условие выполняется

(2,2)



условие не выполняется

(3,1)



условие не выполняется

(3,2)



условие выполняется

(3,3)



условие не выполняется

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



  1. ^ Метод минимального элемента:




    1. Выбираем клетку с минимальной ценой (1,3):




1

100


2


1



1


3

2

70


4


2


3


1

3

30


1


4


2


1







10

40

80

70







1

2

3

4
  1   2   3



Скачать файл (1273 kb.)

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

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru