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

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

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


 

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

58109. Market and Command Economies 37 KB
  In a command economy, a central planning office makes decisions on what, how, and for whom to produce. Economy cannot rely entirely on command, but there was extensive planning in many Soviet bloc countries.
58110. Роль финансов в процессе расширенного воспроизводства 24.75 KB
  Государство регулируем с помощью финансово-кредитной системы величину каждой ветви финансового потока вновь созданной стоимости и, тем самым, регулирует функционирование рынка, направление его развития и т.д.
58111. Инструктаж по техники безопасности. Электромонтажные материалы. Оказание первой помощи пострадавшему под воздействием электрического тока 65.5 KB
  Оказание первой помощи пострадавшему под воздействием электрического тока. Воздействие электрического тока на организм человека: При прохождении электрического тока через тело человека он оказывает следующие виды воздействия: механическое электролитическое термическое биологическое электрическое психологическое. Общее воздействие характеризуется воздействием различных величин электрического тока на организм человека. 1520мА сильные судороги по пути прохождения электрического тока в организме человека.
58112. Из истории появления компьютерных коммуникаций 26 KB
  Устный пересказ которым пользовались для передачи информации в дописьменный период опирался на такое ненадежное устройство хранения информации как человеческая память Второй информационной революцией по праву считают изобретение книгопечатания.
58113. История развития слесарного дела 23 KB
  Качество выполнения слесарных работ во многом зависит от слесарного инструмента и умения его правильно применять. Слесарномонтажный инструмент должен быть качественным и надежным а начинающему слесарю нужно прежде всего изучить инструмент которым ему придется пользоваться. При холодной ручной обработке металлов слесарь наиболее часто использует такой слесарномонтажный инструмент как молотки зубила ножовки напильники и др.
58114. Общество и общественные отношения 226 KB
  ОБЩЕСТВО - обособившееся от природы, но тесно с ней связанная часть мира, которая включает в себя способы взаимодействия людей и формы их объединений.
58115. Значение здоровья для человека 41 KB
  Цель: ознакомить с задачами и содержанием курса Основы здоровья; формировать представление о значении здоровья для обучения труда общения с родными; развивать память мотивацию основ сохранения и укрепления здоровья; воспитывать любовь к жизни к людям.
58116. Військові звання і знаки розрізнення. Начальники та підлеглі, старші та молодші, їх права і обовязки 182.5 KB
  Мета: Вивчити поняття щодо суті і значення військової дисципліни; Назвати статути Збройних сил України основні їх вимоги. Статути Збройних Сил України це зведення законів військової служби на основі яких проходять повсякденне життя виховання навчання бойова діяльність військ...