42064

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

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

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

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

Русский

2013-10-27

2.11 MB

42 чел.

Лабораторная работа 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

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

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


 

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

5033. Разработка эффективного технологического процесса ремонта автомобильных компрессоров 993 KB
  Авторемонтное производство в нашей стране переводится на индустриальную основу. Наряду с действующими авторемонтными предприятиями создаются предприятия по фирменному обслуживанию и ремонту автомобилей (при КамАЗе, АвтоВАЗе, ЯМЗ). Особую з...
5034. Виробничо-технічний рівень їдальні ПГХ Енергетик. Використання виробничої потужності, економічний стан досліджуваного підприємства 1.13 MB
  Громадське харчування сформувалося як підгалузь торгівлі, воно охоплює підприємства громадського харчування державної та приватної торгівлі. Головна мета цих підприємств - надання платних послуг населенню в формі громадсько організованого харч...
5035. Изучение магнитного поля соленоида и его закономерности 652.19 KB
  Изучение магнитного поля соленоида Методические указания выполнены в соответствии с профессиональной образовательной программой. Цель указаний помочь студенту в выполнении лабораторной работы по курсу Электродинамика. Рассматриваются основные зако...
5036. Передача информации 67 KB
  Передача информации Информатизация – это производное от слова информация. Информатизация – это процесс получения, использования, хранения, передачи информации. На протяжении ХХ века сменялось множество способов обмена информацией. Если в X...
5037. Предмет, методы и функции региональной экономики 387 KB
  Предмет, методы и функции региональной экономики. Регионоведение — область научных знаний, изучающая территориальную организацию хозяйства. Предметом регионоведения являются экономические районы всех уровней — экономические зоны, укрупнен...
5038. Исследование линейных резистивных цепей 75.5 KB
  Исследование линейных резистивных цепей Цель работы: экспериментальное исследование линейных разветвлённых резистивных цепей с использованием методов наложения, эквивалентного источника и принципа взаимности. В работе исследуется резистивная цепь с...
5039. Проектирование металлорежущих инструментов. Проектирование круглого радиального фасонного резца 618.5 KB
  Проектирование круглого радиального фасонного резца Назначение фасонных резцов Фасонный резец - инструмент, предназначенный главным образом для использования в условиях серийного и массового производств, где все больший удельный вес приобрет...
5040. Измерение длины волны излучения лазера интерференционным методом 138 KB
  Измерение длины волны излучения лазера интерференционным методом Цель работы: ознакомиться с принципами работы лазеров измерить длину волны излучения лазера и сравнить спектры его индуцированного и спонтанного излучений. Приборы и принадлежности: г...
5041. Определение длин волн излучения источников дискретного и непрерывного спектров 187 KB
  Определение длин волн излучения источников дискретного и непрерывного спектров Цель работы: градуировка спектроскопа по известному спектру неона, определение длин волн в спектре паров ртути и границ видимого спектра лампы накаливания. Приборы и прин...