Методические указания к практическим работам по дисциплине “Логистика и математические модели на транспорте”




НазваниеМетодические указания к практическим работам по дисциплине “Логистика и математические модели на транспорте”
страница6/11
Дата11.11.2012
Размер1.18 Mb.
ТипМетодические указания
1   2   3   4   5   6   7   8   9   10   11

Задача 2

Решить многоресурсную задачу оптимизации перевозок невзаимозаменяемых товаров с ограничением по пропускной возможности маршрутов


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

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

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


Таблица 1 - Параметры перевозок товара 1 вида




Потр-ль А

Потр-ль Б

Потр-ль В

Потр-ль Г

Потр-ль Д

Запас

Вариант

Вариант

Вариант

Вариант

Вариант

0

1

0

1

0

1

0

1

0

1

Поставщик1

В а р и а н т

1

15

18

12

12

11

14

10

16

20

14

300

2

12

20

32

28

14

25

22

19

36

40

540

3

20

12

15

10

28

20

30

22

17

11

720

4

20

35

32

25

36

18

20

34

25

15

620

5

14

20

25

14

18

22

15

30

21

14

560

6

22

14

20

10

25

32

30

35

24

18

780

Поставщик 2

В а р и а н т

1

20

10

14

16

25

30

24

32

15

24

420

2

16

15

20

11

31

18

20

40

17

30

380

3

21

28

12

20

24

35

15

21

24

45

460

4

16

16

27

14

20

20

21

25

28

38

350

5

15

31

34

20

14

15

18

30

20

22

410

6

14

30

10

26

18

16

24

36

34

25

450

Поставщик 3

В а р и а н т

1

12

20

36

18

20

27

16

18

36

35

730

2

16

12

26

10

32

42

34

14

10

16

690

3

20

15

20

16

36

28

30

20

18

10

620

4

18

28

15

26

28

31

18

40

20

27

580

5

15

24

35

35

40

34

10

35

35

40

740

6

22

32

28

14

25

20

35

24

20

35

610

Спрос на товар

600

480

550

750

420

360

780

200

400

180





Таблица 2 - Параметры перевозок товара 2 вида





Потр-ль А

Потр-ль Б

Потр-ль В

Потр-ль Г

Потр-ль Д

Произ-во

Вариант

Вариант

Вариант

Вариант

Вариант

0

1

0

1

0

1

0

1

0

1

Поставщик 1

В а р и а н т

1

10

2

2

12

1

14

10

6

20

14

510

2

26

37

12

45

10

24

39

14

35

42

200

3

11

28

6

10

18

20

22

34

16

14

550

4

25

8

12

17

5

40

25

32

38

30

720

5

24

14

27

40

48

35

21

30

12

40

200

6

16

24

14

30

42

50

35

22

30

52

420

Поставщик 2

В а р и а н т

1

24

8

18

30

20

35

14

40

26

30

400

2

10

12

50

58

8

58

20

58

48

26

800

3

32

16

45

34

10

16

32

8

25

16

250

4

26

35

42

52

35

30

30

22

38

20

480

5

16

20

30

38

26

48

50

50

48

52

900

6

20

12

48

44

30

22

25

18

15

20

420

Поставщик 3

В а р и а н т

1

32

28

54

40

16

28

28

24

10

20

460

2

10

30

60

30

20

35

38

50

44

28

650

3

8

24

25

21

52

42

50

48

48

22

800

4

15

40

38

28

25

10

20

15

12

10

160

5

18

37

16

32

40

35

9

10

25

16

360

6

26

34

20

46

45

30

14

26

24

10

480

Спрос на товар

600

480

550

750

420

360

780

200

400

180





Таблица 3 – Ограничения по пропускной возможности маршрутов




Потр-ль А

Потр-ль Б

Потр-ль В

Потр-ль Г

Потр-ль Д

Поставщик 1

1200

900

1000

850

770

Поставщик 2

1200

1000

1100

900

1440

Поставщик 3

950

1300

1000

870

660


Практическая работа №4

ДВОЙСТВЕННОСТЬ В ЗАДАЧАХ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. АНАЛИЗ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


Цель работы:

  1. Ознакомиться с теорией двойственности в задачах линейного программирования.

  2. Научиться строить пары двойственных задач.

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


1.Общие сведения


Двойственность в задачах линейного программирования

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

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

Хорошо разработанный математический аппарат линейного программирования позволяет не только получать с помощью эффективных вычислительных процедур оптимальный план, но и делать ряд экономически содержательных выводов, основанных на свойствах задачи, двойственной к исходной ЗЛП. Переменные двойственной задачи уi называют объективно обусловленными оценками, или двойственными оценками, или «ценами» ресурсов, или теневыми ценами.

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

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

1. Целевая функция исходной задачи формулируется на максимум, а целевая функция двойственной задачи - на минимум, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид ≤, в задаче на минимум - вид ≥.

2. Матрица А, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица АТ в двойственной задаче получаются друг из друга транспонированием.

3. Число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи, а число ограничений в системе двойственной задачи - числу переменных в исходной задаче.

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

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

Модель исходной (прямой) задачи в общем виде может быть записана следующим образом:



Модель двойственной задачи имеет вид:



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

Сформулируем экономико-математическую модель двойственной задачи к следующей задаче

Фабрика имеет в своем распоряжении определенное количество ресурсов: рабочую силу, деньги, сырье, оборудование, производственные площади и т.п. Допустим, например, ресурсы трех видов: рабочая сила, сырье и оборудование - имеются в количестве соответственно 80 (чел./дней), 480 (кг) и 130 (станко/ч). Фабрика может выпускать ковры четырех видов. Информация о количестве единиц каждого ресурса, необходимых для производства одного ковра каждого вида, и доходах, получаемых предприятием от единицы каждого вида товаров, приведена в таблице.

Ресурсы

Нормы расхода ресурсов

на единицу изделия


Наличие

ресурсов


ковер «Лужайка»


ковер «Силуэт»


ковер «Детский»


ковер «Дымка»


Труд

7

2

2

6

80

Сырьё

5

8

4

3

480

Оборудование

2

4

1

8

130

Цена (тыс.руб.)


3


4


3


1





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

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

Y1 - двойственная оценка ресурса труд, или «цена» труда;

Y2 - двойственная оценка ресурса сырье, или «цена» сырья;

Y3 - двойственная оценка ресурса оборудование, или «цена» оборудования.

Целевая функция двойственной задачи формулируется на минимум. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи.



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

Ограничения. Число ограничений в системе двойственной задачи равно числу переменных в исходной задаче. В исходной задаче четыре переменных, следовательно, в двойственной задаче четыре ограничения. Правыми частями в ограничениях двойственной задачи являются коэффициенты при неизвестных в целевой функции исходной задачи. Левая часть ограничения определяет стоимость ресурсов, затраченных на производство единицы продукции. Каждое ограничение соответствует определенному виду продукции.



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

1. Анализ использования ресурсов в оптимальном плане выполняется с помощью соотношений 2-й теоремы двойственности:



Ресурсы труд и оборудование имеют отличные от нуля оценки 4/3 и 1/3 - эти ресурсы полностью используются в оптимальном плане, являются дефицитными, сдерживающими рост целевой функции. Правые части этих ограничений равны левым частям:



Ресурс «сырье» используется не полностью (280 < 480), поэтому имеет нулевую двойственную оценку (Y2 = 0).



Этот ресурс не влияет на план выпуска продукции.

Общая стоимость используемых ресурсов при выпуске 30 ковров второго вида и 10 ковров третьего вида составит 150 тыс. руб.



Экономическое истолкование оценок есть интерпретация их общих экономико-математических свойств, применительно к конкретному содержанию задачи. Не использованный полностью в оптимальном плане ресурс получает нулевую оценку. Нулевая оценка ресурса свидетельствует о его недефицитности. Ресурс недефицитен не из-за его неограниченных запасов (они ограничены величиной bi), а из-за невозможности его полного использования в оптимальном плане. Так как суммарный расход недефицитного ресурса меньше его общего количества, то план производства им не лимитируется. Данный ресурс не препятствует и дальше максимизировать целевую функцию .

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

Анализ эффективности отдельных вариантов плана

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

Если стоимость ресурсов, затраченных на производство одного изделия, больше его цены, то это изделие не войдет в оптимальный план из-за его убыточности. В нашей задаче в план выпуска не вошли ковры первого и четвертого видов, потому что затраты по ним превышают цену на 7(10 - 3) тыс. руб. и 9.666(10.666 - 1) тыс. руб. соответственно. Это можно подтвердить, подставив в ограничения двойственной задачи оп­тимальные значения вектора Y.



Разницу между правыми и левыми частями ограничений двойственной задачи можно найти в Отчете по устойчивости в столбце «Нормируемая стоимость».

Анализ влияния изменения правых частей ограничений на значения целевой функции (чувствительность решения к изменению запасов сырья)

Предположим, что запас сырья ресурса «труд» изменился на 12 ед. т.е. теперь он составляет 80+12=92 ед. Известно, что колебание величины bi, приводит к увеличению или уменьшению f(X). Оно определяется величиной уi в случае, когда при изменении величин bi значения переменных уi в оптимальном плане соответствующей двойственной задачи остаются неизменными. В нашей задаче увеличение запасов ресурса «труд» приведет к увеличению значения целевой функции на 16 тыс. руб. Для двойственных оценок оптимального плана весьма существенное значение имеет их предельный характер. Точной мерой влияния ограничений на функционал оценки являются лишь при малом приращении ограничения. Известно, что оценки не меняют своей величины, если не меняется набор векторов, входящих в базис оптимального плана, тогда как интенсивности этих векторов (значения неизвестных) в плане могут меняться.

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

Ограничение

правая часть

Допустимое

увеличение

Допустимое

уменьшение

80

150

15

480

1Е+30

200

130

30

90

После увеличения запаса ресурса «труд» до 92 чел./ч было получено новое решение задачи. Изменение запасов ресурсов в пределах интервалов устойчивости двойственных оценок привело не только к изменению значения целевой функции на 16 тыс. руб., но и к изменению плана выпуска. При этом структура плана не изменилась - изделия, которые были убыточны, не вошли и в новый план выпуска, так как цены на ресурсы не изменились. Новый план выпуска составляет 28 ковров второго вида и 18 ковров третьего вида. Изменение общей стоимости продукции на 16 тыс. руб. (24 - 8 = 16) получено за счет уменьшения на 2 ед. ковров второго вида по цене 4 тыс. руб.

(4 тыс. руб. х (28 - 30) = -8 тыс. руб.) и увеличения на 8 ед. ковров третьего вида по цене

3 тыс. руб. (3 тыс. руб. х (18-10) = 24 тыс. руб.).




Чувствительность решения к изменению коэффициентов целевой функции исходной задачи.

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

Целевой

коэффициент

Допустимое

увеличение

Допустимое

Уменьшение

3

7

1Е+30

4

8

1

3

1

1.75

1

9.6667

1Е+30

3 Порядок выполнения работы

1. В задании 1 построить пару двойственных задач и показать преподавателю.

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


4 Варианты для самостоятельного решения

Задание 1

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

1.


2.

3.


4.


5.


6.


7.


8.


9.

10.


11.


12.


13.


14.


Задание 2

Необходимо выполнить следующие задания и письменно оформить результаты:

  • Построить математическую модель.

  • Определить и выписать оптимальный план.

  • Определить, можно ли поднять цену на выпускаемую продукцию без изменения плана выпуска? Если можно, то на сколько?

  • Выявить дефицитные ресурсы. На сколько можно увеличить запас дефицитных ресурсов для улучшения оптимального значения целевой функции?

  • Выявить недефицитные ресурсы. На сколько можно уменьшить их запас при сохранении оптимального значения целевой функции?

  • Выявить изменение общей стоимости выпускаемой продукции определяемой оптимальным планом ее производства при уменьшении количества первого ресурса на 7 ед. и увеличении второго и третьего ресурсов соответственно на 5 и 10 ед. Провести анализ возможного изменения общей стоимости продукции как при изменении объемов каждого из ресурсов по отдельности, так и при их одновременном изменении в указанных размерах.
1   2   3   4   5   6   7   8   9   10   11

Похожие:

Методические указания к практическим работам по дисциплине “Логистика и математические модели на транспорте” iconМетодические указания по практическим работам По дисциплине
Методические указания по практическим занятиям по дисциплине «Моделирование систем» включает тематику вопросов, выносимых для самостоятельной...
Методические указания к практическим работам по дисциплине “Логистика и математические модели на транспорте” iconМетодические указания по практическим работам
Методические указания по практическим занятиям по дисциплине «Организация и планирование производства» включают тематику вопросов,...
Методические указания к практическим работам по дисциплине “Логистика и математические модели на транспорте” iconМетодические указания по практическим работам
«Экономика лесного комплекса», «Экономика предприятия», «Экономика на транспорте»
Методические указания к практическим работам по дисциплине “Логистика и математические модели на транспорте” iconМетодические указания по контрольным работам
Методические указания по практическим занятиям по дисциплине «Теория экономических информационных систем» включают тематику вопросов,...
Методические указания к практическим работам по дисциплине “Логистика и математические модели на транспорте” iconМетодические указания к практическим и лабораторным работам по дисциплине «Моделирование систем»
Автономное муниципальное образовательное учреждение высшего профессионального образования
Методические указания к практическим работам по дисциплине “Логистика и математические модели на транспорте” iconМетодические указания к практическим работам по дисциплине «Архитектоника объёмных форм»
«структура», «средства гармонизации», «архитектоничный строй объекта», «тектоника» и т д., и использовать их в дальнейшем, непосредственно...
Методические указания к практическим работам по дисциплине “Логистика и математические модели на транспорте” iconМетодические указания к практическим занятиям по дисциплине «Шрифт»
Методические указания к практическим занятиям по дисциплине «Шрифт» для студентов специальностей Шымкент: юкгу им. М. Ауезова. 2010...
Методические указания к практическим работам по дисциплине “Логистика и математические модели на транспорте” iconМетодические указания к лабораторно-практическим работам по дисциплине "Проектирование пользовательского интерфейса"
Практическое занятие по созданию в среде Delphi строки меню и выпадающего меню. 9
Методические указания к практическим работам по дисциплине “Логистика и математические модели на транспорте” iconМетодические указания к лабораторным работам по дисциплине «Управление проектами»
Методические указания к лабораторным работам по дисциплине «Управление проектами» для студентов и слушателей факультета «Инженерный...
Методические указания к практическим работам по дисциплине “Логистика и математические модели на транспорте” iconМетодические указания к практическим занятиям по курсу «Методы и модели в экономике»
Типовые задачи статического моделирования линейной многоотраслевой экономики [Текст] : метод указания к практическим занятиям по...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница