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

Отчет

Программа

BUF STORAGE 1000000

VK STORAGE 3

*Описание двух памятей: BUF с неограниченным количеством мест и VK на *3 места, в которой каждое место имитирует один процессор.

*Режим недоступности для памяти имеет меньше возможностей по *сравнению с устройствами. В нем нельзя указать изменение режимов для *транзактов, связанных с объектом, на который накладывается режим *недоступности. А режим отказов для вновь поступающих транзактов можно *наложить блоком GATE.

GENERATE 8,4

GATE SV BUF,OTKAZ

*Транзакты, вошедшие в блок GATE, проверяют доступность памяти с *именем BUF. Если она доступна, то они поступают к следующему блоку и *занимают память. В случае недоступности транзакт переходит на метку *OTKAZ

ENTER BUF

ENTER VK

LEAVE BUF

ADVANCE 20,7

LEAVE VK

TERMINATE

OTKAZ TERMINATE 1

*Так как первый блок TERMINATE с пустым операндом А, а второй с А=1, *то на счетчик команды START будет влиять только второй блок *TERMINATE и после удаления через него 50 транзактов произойдет *останов.

*Сегмент отказа

GENERATE 5000,300

SUNAVAIL BUF

SUNAVAIL VK

*Установление режима недоступности на памяти с именем BUF и VK

ADVANCE 100,20

SAVAIL VK

SAVAIL BUF

*Возвращение памятям режима доступности.

TERMINATE

START 50

GPSS World Simulation Report - 7.15.1

Thursday, November 01, 2007 10:07:39

START TIME END TIME BLOCKS FACILITIES STORAGES

0.000 20536.822 16 0 2

NAME VALUE

BUF 10000.000

OTKAZ 9.000

VK 10001.000

LABEL LOC BLOCK TYPE ENTRY COUNT CURRENT COUNT RETRY

1 GENERATE 2561 0 0

2 GATE 2561 0 0

3 ENTER 2511 0 0

4 ENTER 2511 0 0

5 LEAVE 2511 0 0

6 ADVANCE 2511 0 0

7 LEAVE 2511 0 0

8 TERMINATE 2511 0 0

OTKAZ 9 TERMINATE 50 0 0

10 GENERATE 4 0 0

11 SUNAVAIL 4 0 0

12 SUNAVAIL 4 0 0

13 ADVANCE 4 1 0

14 SAVAIL 3 0 0

15 SAVAIL 3 0 0

16 TERMINATE 3 0 0

STORAGE CAP. REM. MIN. MAX. ENTRIES AVL. AVE.C. UTIL. RETRY DELAY

BUF 1000000 1000000 0 3 2511 0 0.132 0.000 0 0

VK 3 3 0 3 2511 0 2.439 0.813 0 0

FEC XN PRI BDT ASSEM CURRENT NEXT PARAMETER VALUE

2567 0 20541.978 2567 0 1

1929 0 20582.179 1929 13 14

2559 0 25551.467 2559 0 10

По содержимому отчёта отметим сравнительно небольшое среднее содержимое очереди – 0.132; загрузка вычислительного комплекса сравнительно высокая с коэффициентом использования – 0.813; произошло четыре события по наложению режима недоступности на очередь и вычислительный комплекс. Произошло 50 отказов в обслуживании транзактов, когда очередь находилась в режиме недоступности, это в какой то мере объясняет сравнительно небольшое среднее содержимое очереди.

Рассмотрим постановку одной из специфических задач линейной оптимизации, получившей название транспортной задачи.

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

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

Задача ставится следующим образом:

Найти объемы перевозок для каждой пары «поставщик-потребитель» так, чтобы:

1) мощности всех поставщиков были реализованы;

2) спросы всех потребителей были удовлетворены;

3) суммарные затраты на перевозку были бы минимальны.

Рассмотрим математическую модель транспортной задачи.

Необходимо доставить от поставщиков некоторый однородный товар (груз) в объеме , единиц потребителям с минимальными транспортными издержками. (Здесь m и n - конечные числа.) Потребность в данном товаре каждого j -го потребителя известна и составляет , единиц. Известны также - величины стоимости перевозки единицы груза от i -го поставщика к j -му потребителю.

Обозначим количество единиц поставляемого груза от i -го поставщики к j -му потребителю через и занесем все данные в таблицу транспортной задачи (табл.1)

Таблица 1

Поставщики	Потребители	Запасы поставщи-ков
		…	j	…	n
			...		...
			...		...
…	…	…	...	…	...	…	…
i			...		...
…	…	…	…	…	...	…	…
т			...		...
Спрос потребите-лей			…		...		Z

Математическое отражение цели задачи — минимизация суммарных затрат перевозку груза — имеет вид

(1)

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

- груз от каждого поставщика должен быть вывезен полностью

(2)

- спрос каждого потребителя в продукции должен быть удовлетворен

(3)

- объемы перевозок должны быть неотрицательными

(4)

Транспортная задача имеет решение, если суммарный запас груза в пунктах отправления равен суммарному спросу в пунктах назначения, т.е. если выполняется равенство

(5)

Транспортная задача, для которой выполняется условие (5) называется закрытой, в противном случае – открытой.

Для решения открытой транспортной задачи сведем ее к закрытой:

а)

б)

Модели транспортной задачи с введенным фиктивным поставщикам и фиктивным потребителем приведены в табл. 2 и 3 соответственно.

Таблица 2

Поставщики	Потребители	Запасы
			…	п	п +1
			…
…			…
т			…
Спрос			…

Таблица 3

Поставщики	Потребители	Запасы
			…	п
			…
…			…
т			…
m+ 1			…
Спрос			…

Элементы матрицы с_ij, связывающие фиктивные пункты с реальными, имеют значения, равные затратам на хранение невывезенных грузов (в случае ввода фиктивного потребителя) или штрафам за недопоставку продукции (в случае ввода фиктивного поставщика). Если указанные затраты неизвестны (не указаны) соответствующие значения с_ij полагают равными нулю.

Транспортным задачам присущи следующие особенности:

1) распределению подлежат однородные ресурсы;

2) система ограничений есть система уравнений (т.е. транспортная задача задана в канонической форме);

3) все переменные выражаются в одинаковых единицах измерения;

4) коэффициенты при неизвестных системы ограничений равны единице (или 0);

5) каждая переменная входит в систему ограничений 2 раза: один раз – в систему (2) и один раз – в систему (3).

Дата добавления: 2014-01-11