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

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

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


 

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

55954. ЛЕКСИКОЛОГІЯ, ЛЕКСИКОГРАФІЯ ТА ФРАЗЕОЛОГІЯ У ПРОФЕСІЙНОМУ СПІЛКУВАННІ 108 KB
  Усі слова наявні у мові становлять лексику. Тобто майже всі слова можна поділити за їх значенням в однорідні групи з єдиним тематичним направленням. До активної лексики належать слова які широко й повсякденно вживаються. Це звичайні слова без яких не можливо висловити жодної розгорнутої думки.
55955. СТИЛІСТИЧНІ ОСОБЛИВОСТІ ВИРАЖАЛЬНИХ ЗАСОБІВ МОВИ. ТИПОВІ ПОМИЛКИ У ТЕКСТІ ДОКУМЕНТА 50 KB
  Важливу роль у піднесенні мовної культури тексту документа відіграє стилістика як розділ лінгвістики що допомагає використовувати виражальні засоби мови у різних умовах спілкування відповідно до мети і змісту. Наприклад: українська мова в ході розслідування...
55956. ДОДЕРЖАННЯ НОРМ СУЧАСНОЇ УКРАЇНСЬКОЇ ЛІТЕРАТУРНОЇ МОВИ - УМОВА УСПІШНОГО СПІЛКУВАННЯ 114.5 KB
  Мовну підготовку слід розглядати як обовязковий елемент професійної підготовки правознавця - практичного працівника. Тому нашим завданням і є звернутися до грамотності, й, насамперед, до норм орфографії, граматики, морфології тощо.
55957. ГРАМАТИЧНА ПРАВИЛЬНІСТЬ ЯК ОЗНАКА КУЛЬТУРИ УСНОГО ТА ПИСЕМНОГО СПІЛКУВАННЯ 71 KB
  Відмінювання іменників Іменники це слова які називають предмети істоти опредмечені назви процесів дій ознак і відповідають на питання хто що закон право юрист арбітраж суддя слідчий офіцер правнича фундація документ ділова мова...
55958. КУЛЬТУРА УСНОГО ДІЛОВОГО СПІЛКУВАННЯ 186 KB
  Інтерв’ю Візитна картка та її використання Орфоепія і культура усного мовлення Участь у дебатах Мистецтво публічного виступу Без спілкування люди не могли б жити в суспільстві працювати й передавати свій досвід і знання іншим.
55959. Сенсорне виховання дітей раннього віку «Ігровий майданчик» 76.5 KB
  Хід гризаняття Вихователь ставить на стіл будиночок теремок за яким розташовується 23 мотрійки і говорить малюкам що в будиночку живуть мотрійки. У третій частині заняття діти розглядають предмети витягнуті з іграшок наприклад серветки. Гразаняття Дві мотрійки Складання мотрійки з одним вкладишем Мета: розвивати навички виконувати прості дії з предметами відкривати та закривати мотрійки вкладати і виймати предмети; збагачувати сенсорний досвід під час знайомства з розміром.
55960. Його величність - серце 51 KB
  Мета: Продовжити знайомство учнів з серцевосудинною системою людини. Вивчивши серцевий цикл встановити причину інтенсивної роботи серця. На уроці ми переглянемо біологічний журнал Його величність серце.
55961. Органи кровообігу. Серце, його будова 140 KB
  Застосовувати знання для: кровоносні судини; органи кровообігу на малюнках; особливості будови серцевого м’яза; профілактики серцево-судинних хвороб. Кожна хребетна тварина яка має кров має серце. Прислухайся у грудях серце стука Вистукує один і той же ритм...
55962. The Ecological Problems of our Settlement 34 KB
  Good afternoon, everybody! I am glad to see you at our ecological party which is called "A Boomerang". I am sure that everybody who has come here is indifferent to everything that is around us, and understands that the Earth is our home. Today we will discuss and try to solve the environmental problems of our settlement.