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

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

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


 

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

5556. Анализ производительности труда механо-сборочного цеха №3 (цех 184) ФГУП ПО Уралвагонзавод и определение резервов ее повышения 349.5 KB
  Введение Одним из самых наглядных и объективных показателей, определяющих рациональность использования имеющихся на предприятии кадровых ресурсов, является производительность труда. Производительность труда измеряется количеством продукции, произвед...
5557. Спроектировать одноступенчатый горизонтальный цилиндрический косозубый редуктор и клиноременную передачу для привода к ленточному конвейеру 1.14 MB
  Задание на проектирование Спроектировать одноступенчатый горизонтальный цилиндрический косозубый редуктор и клиноременную передачу для привода к ленточному конвейеру. Мощность на ведомом валу: P=12кВт Частота вращения ведомого вала: n2=400м...
5558. Организационная структура ОАО ЭМСС. Товарооборот и технические характеристики предприятия 479.5 KB
  Данный отчет освещает следующие темы: организационная структура ОАО ЭМСС, а также основные виды товаров и услуг, которые предоставляются предприятием организационная структура и задачи отдела главного технолога использо...
5559. Расчет фундаментов мелкого заложения и свайных фундаментов по I и II группе предельных состояний 742.58 KB
  Аннотация Приведены примеры расчета фундаментов мелкого заложения и свайных фундаментов по I и II группе предельных состояний. Рассмотрены примеры конструирования свайных ростверков, ленточных и столбчатых фундаментов. Методические указания предназн...
5560. Неопределенность измерения и ее отражение в описании результатов 218 KB
  Неопределенность измерения и ее отражение в описании результатов История вопроса В 1978 г. наивысший мировой авторитет в метрологии - Международный комитет мер и весов (МКМВ) обратился к Международному бюро мер и весов (МБМВ) с просьбой рассмот...
5561. Проектирование основных узлов тележки мостового крана 309.5 KB
  Исходные данные: Грузоподъемность G=50 кН Скорость подъема груза VG=20 м/мин Высота подъема груза Н=5 м Скорость перемещения тележки v=25 м/мин ПВ=15% Режим работы - М2; Кратность полиспаста - 4...
5562. Понятие и значение контроля исполнения документов 96.5 KB
  Понятие и значение контроля исполнения документов. Контроль играет важную роль в системе документооборота. Контроль исполнения документов обеспечивает своевременное и качественное решение содержащихся в документе вопросов, охват всех контролируемых ...
5563. Бертольт Брехт. Жизнь и творчество 48.5 KB
  Бертольт Брехт После смерти Бертольта Брехта прошло немало лет. Предсказания недоброжелателей не оправдались: драматургия и поэзия Брехта не только не ушли в прошлое, но с каждым годом приобретают все большее число друзей. Идеи Брехта по-прежнему со...
5564. Архитектура Древней Греции 116.5 KB
  Введение. Архитектура античной Греции, охватывающая в своём развитии в основном VIII-I века до н.э., делится на три периода: архаический, классический и эллинистический. Им предшествовали периоды крито-микенской культуры на территории южной Гр...