42064

Двухиндексные задачи ЛП. Транспортная задача

Лабораторная работа

Информатика, кибернетика и программирование

Решение такой задачи рассмотрим на примере оптимальной организации транспортных перевозок штучного товара из пунктов отправления складов в пункты назначения магазины. Требуется определить план перевозок количество единиц груза из пунктов i в пункты Bj так чтобы Вывезти весь груз от отправителей i Удовлетворить потребность каждого потребителя Bj Транспортные расходы были минимальными Математическая модель транспортной задачи имеет вид: требуется определить неотрицательную матрицу X удовлетворяющую условиям и доставляющую...

Русский

2013-10-27

2.11 MB

43 чел.

Лабораторная работа 2_2. Двухиндексные задачи ЛП. Транспортная задача.

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

Краткие теоретические сведения

Двухиндексные задачи ЛП вводятся и решаются в Excel аналогично одноиндексным задачам. Специфика ввода условия двухиндексной задачи ЛП состоит лишь в удобстве матричного задания переменных задачи и коэффициентов ЦФ. Решение такой задачи рассмотрим на примере оптимальной организации транспортных перевозок штучного товара из пунктов отправления (складов) в пункты назначения (магазины).

  1.  Имеются m пунктов отправления однородного груза A1, A2, Am  и n пунктов назначения  того же груза B1, B2, … Bn. Известно:

- запас груза в пункте Ai;

- потребности в пункте Bj;

   -  стоимость перевозки единицы груза из Ai в Bj .

Требуется определить план перевозок (количество единиц ) груза из пунктов Ai в пункты Bj так, чтобы

  •  Вывезти весь груз от отправителей Ai
  •  Удовлетворить потребность каждого потребителя Bj
  •  Транспортные расходы были минимальными
  1.  Математическая модель транспортной задачи имеет вид: требуется определить неотрицательную матрицу X, удовлетворяющую условиям

и доставляющую минимум целевой функции

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

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

  1.  Решение задачи начинается с определения начального опорного плана одним из методов
  •  Метод северо-западного угла;
  •  Метод минимального элемента;
  •  Метод Фогеля

Если в полученном опорном плане  имеется ровно m+n-1 ненулевой компонент, он является невырожденным.

  1.  После получения начального плана определяют стоимость его реализации и проверяют на оптимальность методом потенциалов

Пример. Фирма, обслуживающая туристов прибывающих на отдых, должна разместить их в 4 отелях: “Морской”, “Солнечный”, “Слава” и “Уютный”, в которых забронировано соответственно 5, 15, 15 и 10 мест. Пятнадцать туристов прибывают по железной дороге, двадцать пять прилетают в аэропорт, а пять человек прибудут на теплоходе на морской вокзал. Транспортные расходы при перевозке из пунктов прибытия в отели приведены в таблице 1.


Таблица 1

Исходный пункт, i

Пункт назначения (отели), j

Морской

Солнечный

Слава

Уютный

1

2

3

4

Ж/д вокзал

1

10

0

20

11

Аэропорт

2

12

7

9

20

Морской вокзал

3

0

14

16

18

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

I. Математическая модель задачи

1) Переменные задачи. Обозначим количество туристов, которые будут перевозиться из пункта i в отель j как Xij (i=1,2,3; j=1,2,3,4). Количество переменных, значения которых должны быть определены, составляет 12 переменных.

2) Ограничения на переменные задачи. Очевидно, что все переменные задачи

   Xij  0, i=1, 2, 3; j=1, 2, 3, 4. (1)

Кроме этого, должны быть удовлетворяться следующие условия.

 X11 + X12 + X13 + X14 = = 15   (2)

 X21 + X22 + X23 + X24 = = 25   (3)

 X31 + X32 + X33 + X34 = = 5   (4)

По условию задачи в отеле “Морской” (пункт 1) забронировано 5 мест, поэтому:

  X11 + X21 + X31 = = 5   (5)

Аналогично, для пункта 2:

  X12 + X22 + X32 = = 15   (6)

Для пункта 3:

  X13 + X23 + X33 = = 15   (7)

Для пункта 4:

  X14 + X24 + X34 = = 10   (8)

Представим ТЗ в виде таблицы, где в ячейках помещаются переменные задачи (Xij), а в правом верхнем углу ячейки - стоимости перевозки из пункта i в пункт j ( Cij ). В крайнем правом столбце и нижней строке таблицы записываются числа определяющие ограничения задачи (в данном примере – это число туристов в исходных пунктах и число мест в пунктах назначения – отелях).


Таблица 2

Исходный пункт,i

Пункт назначения (отели),j

Число туристов в исходном пункте

1

2

3

4

10

0

20

11

1

X11

X12

X13

X14

15

12

7

9

20

2

X21

X22

X23

X24

25

0

14

16

18

3

X31

X32

X33

X34

5

Число мест в отеле

5

15

15

10

             å = 45 

å = 45                   

Суммы чисел в последнем столбце и нижней строке равны, т.е. задача  сбалансирована: 15 + 25 + 5 = 45, 5 + 15 + 15 + 10 = 45.

3) Целевая функция. Транспортные расходы на перевозку туристов в отели:

Z = CijXij = 10X11 + 0X12 + 20X13 + ... +18X34 -> min  (10)

II. Решение транспортной задачи в процедуре EXCEL “Поиск решения”

1) Ввод данных. Вводим данные таблицы 1 и 2 в ячейки EXCEL (рис.1).

В ячейках B3:E5 введены стоимости перевозок (табл. 1).

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

В ячейках B6:E6 находится число мест в отелях.

Ячейки B8:E10 – рабочие ячейки, в которых будут вычисляться значения переменных задачи Xij.

В ячейках F8:F10 вводятся формулы для вычисления левых частей ограничений (3)¸(5):

 F8 - сумма  B8:E8;

 F9 - сумма  B9:E9;

 F10 - сумма B10:E10.

Формулы для вычисления левых частей ограничений (6)¸(9) введем в ячейки B11:E11:

в B11 должна быть сумма ячеек B8:B10;

в C11 должна быть сумма ячеек C8:C10;

в D11 должна быть сумма ячеек D8:D10;

в E11 должна быть сумма ячеек E8:E10;

Целевую функцию поместим в ячейку G3: СУММПРОИЗВ (B3:E5; B8:E10).

Таблица исходных данных имеет вид (Рис.1):

Рис.1

2) Заполнение окна процедуры «Поиск решения». 

целевая функция : G3;

значение целевой функции : min;

изменяемые ячейки : B8 : E10;

ограничения задачи :

 F8 : F10 = F3 : F5  (формулы (3)¸(5))

 B11 : E11 = B6 : E6  (формулы (6)¸(9))

 B8 : E10 0   (формула 1)

В окне «Параметры» установить «Линейная модель», что соответствует решению задачи симплекс-методом. Результаты заполнения окна показаны на рис.2:

Рис.2

  1.  Выполнив процедуру «Поиск решения», получим результаты (рис.3):

Рис.3

Суммарная стоимость транспортных расходов составит 315 рублей (ячейка G3).

I. Контрольные упражнения. Варианты.

  1.  Решить транспортные задачи методом потенциалов

Пункты

отправления

Пункты назначения

Запасы

B1

B2

B3

B4

A1

7

4

15

9

120

A2

11

2

7

3

80

A3

4

5

12

8

100

Потребности

85

62

93

60

?

  1.  

Пункты

отправления

Пункты назначения

Запасы

B1

B2

B3

B4

A1

2

10

15

14

130

A2

3

7

12

3

170

A3

21

18

6

13

200

Потребности

100

90

160

150

?

  1.  

Пункты

отправления

Пункты назначения

Запасы

B1

B2

B3

B4

A1

14

8

17

5

90

A2

21

10

7

11

180

A3

3

5

8

4

130

Потребности

70

120

105

105

?

  1.  

Пункты

отправления

Пункты назначения

Запасы

B1

B2

B3

B4

A1

12

9

7

11

105

A2

4

3

12

2

165

A3

5

17

9

4

180

Потребности

90

120

110

130

?

  1.  

Пункты

отправления

Пункты назначения

Запасы

B1

B2

B3

B4

A1

9

8

7

11

160

A2

14

3

1

8

400

A3

9

5

16

7

240

Потребности

180

200

190

230

?

  1.  

Пункты

отправления

Пункты назначения

Запасы

B1

B2

B3

B4

A1

2

4

11

5

250

A2

8

7

13

7

180

A3

14

10

5

8

270

Потребности

120

230

190

160

?

  1.  

Пункты

отправления

Пункты назначения

Запасы

B1

B2

B3

B4

A1

9

5

3

10

25

A2

6

3

3

2

55

A3

3

8

4

8

30

Потребности

45

15

30

20

?

  1.  

Пункты

отправления

Пункты назначения

Запасы

B1

B2

B3

B4

A1

3

10

11

15

560

A2

22

11

4

2

420

A3

8

1

7

15

520

Потребности

300

380

450

370

?

  1.  

Пункты

отправления

Пункты назначения

Запасы

B1

B2

B3

B4

A1

11

4

15

7

250

A2

20

9

7

14

350

A3

18

9

3

8

300

Потребности

180

220

230

270

?

  1.  

Пункты

отправления

Пункты назначения

Запасы

B1

B2

B3

B4

A1

1

4

5

11

300

A2

12

8

3

14

320

A3

10

15

7

9

380

Потребности

250

200

290

260

?

  1.  

Пункты

отправления

Пункты назначения

Запасы

B1

B2

B3

B4

B5

A1

4

8

10

14

15

250

A2

7

11

9

12

13

150

A3

6

3

2

1

4

100

A4

1

4

7

9

3

290

Потребности

90

100

150

200

250

?

  1.  

Пункты

отправления

Пункты назначения

Запасы

B1

B2

B3

B4

B5

A1

4

6

3

4

1

30

A2

3

5

2

5

3

30

A3

2

4

1

6

2

40

A4

3

2

1

4

3

50

Потребности

25

25

25

15

30

?

  1.  

Пункты

отправления

Пункты назначения

Запасы

B1

B2

B3

B4

B5

A1

3

3

4

2

3

25

A2

4

2

2

1

4

35

A3

1

4

1

3

2

40

A4

1

2

3

1

5

50

Потребности

20

20

20

35

15

?

  1.  

Пункты

отправления

Пункты назначения

Запасы

B1

B2

B3

B4

B5

A1

3

1

2

4

3

50

A2

5

1

3

2

6

90

A3

2

3

4

1

1

65

A4

6

2

5

3

2

75

Потребности

100

30

70

30

50

?

  1.  

Пункты

отправления

Пункты назначения

Запасы

B1

B2

B3

B4

B5

A1

2

1

4

3

5

140

A2

8

7

5

1

3

160

A3

4

6

2

7

1

100

A4

1

5

3

4

6

80

Потребности

40

100

120

150

70

?


II. Найти решение ТЗ, исходные данные которой приведены в табл.1, при дополнительных условиях: из A1 в B2  и из  из A2 в B5  перевозки не могут быть осуществлены,  а из A2 в B1 будет завезено 60 ед. груза.

Табл.1

Пункты отправления

Пункты назначения

Запасы

B1

B2

B3

B4

B5

A1

1

2

3

1

4

180

A2

6

3

4

5

2

220

A3

8

2

1

9

3

100

Потребности

120

80

160

90

50

III. . Найти решение ТЗ, исходные данные которой приведены в табл.2

Табл.2

Пункты отправления

Пункты назначения

Запасы

B1

B2

B3

B4

B5

A1

5

8

7

2

1

220

A2

6

3

5

4

6

140

A3

7

4

2

3

2

160

Потребности

80

140

90

130

80

Ограничения на переменные представлены матрицей

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


 

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

14192. Стратегический анализ внутренней и внешней среды. ОАО Ростех - оргтехника 681.5 KB
  Ремонтируя и обслуживая оргтехнику и электротехнику, гарантируем качество выполняемых нами услуг. При работе используем только качественные материалы и запасные части
14194. Управление банковскими рисками в АКБ ОАО «Банк Москвы» 302 KB
  Оглавление [1] Список используемых источников Введение Актуальность темы настоящего исследования определяется следующими теоретическими положениями. Концепция риска как его сосуществование стара как мир. Риск всепроникаю
14195. Управление конфликтами в трудовом коллективе (на примере частного охранного предприятия «Полад») 896 KB
  Цель данной выпускной квалификационной работы – изучить природу возникновения и разработать пути разрешения конфликтной ситуации в трудовом коллективе
14196. Управление конфликтами и стрессами на предприятии 437.5 KB
  Дипломный проект На тему Управление конфликтами и стрессами на предприятии Содержание: Введение. Глава 1. Теоретические подходы к исследованию конфликтов и стрессов на предприятии. Сущность и содержание конфликтов и стрессов на предприятии. Причины их возни
14197. Управление конфликтами на предприятии 401 KB
  Каждому из нас приходилось сталкиваться с конфликтными ситуациями. Конфликты проявляются в деятельности всех социальных институтов социальных групп во взаимоотношениях между людьми и играют ключевую роль в жизни отдельного человека семьи...
14198. УПРАВЛЕНИЕ БАНКОВСКИМИ РИСКАМИ на ЗАО «Ростовская валютно-фондовая биржа» 173.66 KB
  Содержание Введение Глава 1. Классификация банковских рисков методы их оценки и управления 1.1.Классификация рисков возникающих при проведении операций на биржевом рынке 1.2.Банковские риски при проведении операций с иностранной валютой 1.3.Банковск
14199. Использование подходов веб-аналитики для построения модели пользователя 304.5 KB
  Рассматриваются системы электронной отчетности как специфический вид веб-ресурса. Ставится цель повышения эффективности ресурса. Разрабатывается методика построения модели веб-пользователя с применением подходов веб-аналитики. Строится модель и её графическое представление.
14200. Характеристика получения взятки и взяточничества в целом 342 KB
  ВВЕДЕНИЕ В настоящее время в России в период построения цивилизованной экономики и становления демократического правового государства важная роль принадлежит органам государственной власти и исполнения а также органам местного самоупр