VIII Международная студенческая научная конференция Студенческий научный форум - 2016

Цель: Рассмотреть решение несбалансированной транспортной задачи и решение несбалансированной задачи о назначениях и сравнить их.

Построим математические модели задач:

1. Несбалансированная транспортная задача:

Пусть имеется m источников финансирования А₁, А₂, ..., А_m и n периодов финансирования В₁, B₂, ..., Вn. Известны затраты, связанные с выделением единицы денежных ресурсов С_ij из i-го источника в j-ом периоде, а также объемы финансирования из каждого i-го источника в течение всего времени – а_i. Известны суммарные объемы финансирования из всех источников в каждый j-й период времени – b_j. Требуется определить объемы финансирования x_ij из i-го источника в j-ом периоде, чтобы:

1. Ресурсы всех источников были реализованы.

2. Обеспечить финансирование в полном объеме в каждом периоде.

3. Достигнуть экстремума выбранного критерия оптимизации.

Различают закрытую (сбалансированную) и открытую (несбалансированную) транспортную задачу. Транспортная задача, в которой суммарные запасы и потребности совпадают, т.е., называется закрытой; в противном случае − открытой. Для открытой транспортной задачи возможны два случая:

а) суммарные запасы превышают суммарные потребности ;

б) суммарные потребности превышают суммарные запасы.

Линейная целевая функция одинакова в обоих случаях, изменяется только вид системы ограничений, при этом открытая задача решается сведением к закрытой модели путем введения фиктивных пунктов доставки или источников ресурса.

В случае а), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель В_m+1 потребность которого составит

(1).

В случае б), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик Аn₊₁, запасы которого составляют

(2).

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

Прежде чем решать какую-нибудь транспортную задачу, необходимо сначала проверить, к какой модели она принадлежит, и только после этого составлять математическую модель для ее решения

Постановка задачи. Имеется три песчаных карьера, из которых песок доставляется на четыре стройки. Известны запасы сырья на каждом объекте и потребности строек в этом песке. Кроме того, известны затраты в рублях, связанные с перевозкой одного кубического метра песка с каждого карьера на каждую стройку. Исходные данные представлены для сбалансированной транспортной задачи, из которой мы получим два случая несбалансированной задачи, в таблице 1.

Таблица 1. Данные к сбалансированной транспортной задаче.

Стройка Карьер	Стройка 1	Стройка 2	Стройка 3	Стройка 4	Запасы песка ai
Карьер 1	20	35	20	40	350
Карьер 2	50	30	50	20	500
Карьер 3	20	30	35	45	450
Потребности в песке bj	400	400	200	300

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

Для решения задачи составим ее математическую модель.

Проверим задачу на сбалансированность:

Случай а: суммарные запасы превышают суммарные потребности;

Для того чтобы определить начальные условия и построить математическую модель данного типа изменим данные таблицы 1, увеличив запасы на первом и третьем карьере на 100 единиц.

1. Определим неизвестные и их количество.

Обозначим через x_ij количество песка (м³), перемещаемого из i-го карьера на j-ю стройку. Учтем несбалансированность задачи и введем фиктивного потребителя (Стройку 5) с нулевыми расходами на перевозку песка. Получаем потребность фиктивного потребителя по формуле (1). Таким образом, элементы x_ijобразуют матрицу перевозок X _4х5.

Таблица 2. Начальные условия для несбалансированной транспортной задаче (случай а)
карьер стройка		стройка 1	стройка 2	стройка 3	стройка 4	стройка 5	Вывезено
карьер 1		20	35	20	40	0	450
карьер 2		50	30	50	20	0	600
карьер 3		20	30	35	45	0	550
Доставленно		400	400	200	300	300

2. Запишем целевую функцию.

F(X)=20*x₁₁+35*x₁₂+20*x₁₃+40*x₁₄+0*x₁₅+50*x₂₁+30*x₂₂+50*x₂₃+20*x₂₄+

+0*x₂₅+20*x₃₁+30*x₃₂+35*x₃₃+45*x₃₄+0*x₃₅ → min(1а´)

3. Сформулируем ограничения рассматриваемой задачи.

3.1. Необходимо вывезти весь песок с карьеров:

(2а´)

3.2. Удовлетворить потребности каждой стройки в песке.

(3а´)

3.3. Введем граничные условия, которые определяют предельно допустимые значения искомых переменных (условие неотрицательности):

x₁₁≥0, x₁₂≥0, x₁₃≥0, x₁₄≥0, x₁₅≥0, x₂₁≥0, x₂₂≥0, x₂₃≥0, x₂₄≥0, x₂₅≥0,

x₃₁≥0, x₃₂≥0, x₃₃≥0, x₃₄≥0, x₃₅≥0 (4а´)

Таким образом, целевая функция (1а´) и ограничения (2а´− 4а´) образуют математическую модель несбалансированной транспортной задачи случая а.

Решение в среде MS Excel:

Рис 1. Математическая модель и матрица перевозок.

Рис 2. Решение с помощью надстройки «Поиск решения»

Рис 3. Результат решения задачи

Случай б: суммарные потребности превышают суммарные запасы.

Для того чтобы определить начальные условия и построить математическую модель данного типа изменим данные таблицы 1, увеличив потребности строек на 300 единиц.

1. Определим неизвестные и их количество.

Обозначим через x_ij количество песка (м³), перемещаемого из i-го карьера на j-ю стройку. Учтем несбалансированность задачи и введем фиктивный источник ресурса (Карьер 4) с нулевыми расходами на перевозку песка. Получаем запас ресурса на фиктивном источнике по формуле (2). Таким образом, элементы x_ijобразуют матрицу перевозок X _4х4.

Таблица 3. Начальные условия для несбалансированной транспортной задаче (случай б)
карьер стройка	стройка 1	стройка 2	стройка 3	стройка 4	Вывезено
карьер 1	20	35	20	40	350
карьер 2	50	30	50	20	500
карьер 3	20	30	35	45	250
Карьер 4	0	0	0	0	300
Доставленно	500	500	250	350

2. Запишем целевую функцию.

F(X)=20*x₁₁+35*x₁₂+20*x₁₃+40*x₁₄ +50*x₂₁+30*x₂₂+50*x₂₃+20*x₂₄+

+20*x₃₁+30*x₃₂+35*x₃₃+45*x₃₄+0*x₁₄+0*x₂₄ +0*x₃₄ +0*x₄₄→ min(1б´)

3. Сформулируем ограничения рассматриваемой задачи.

3.1. Необходимо вывезти весь песок с карьеров:

(2б´)

3.2. Удовлетворить потребности каждой стройки в песке.

(3б´)

3.3. Введем граничные условия, которые определяют предельно допустимые значения искомых переменных (условие неотрицательности)

x₁₁≥0, x₁₂≥0, x₁₃≥0, x₁₄≥0, x₂₁≥0, x₂₂≥0, x₂₃≥0, x₂₄≥0,

x₃₁≥0, x₃₂≥0, x₃₃≥0, x₃₄≥0, x₄₁≥0, x₄₂≥0, x₄₃≥0, x₄₄≥0 (4б´)

Таким образом, целевая функция (1.б´) и ограничения (2.б´− 4.б´) образуют математическую модель несбалансированной транспортной задачи случая б.

Решение в среде MS Excel:

Рис 4. Математическая модель и матрица перевозок.

Рис 5. Решение с помощью надстройки «Поиск решения»

Рис 6. Результат решения задачи

2. Несбалансированная задача о назначениях. Назначения претендентов на вакансии.

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

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

Работы Рj Исполнители Иi	Р1	Р2	…	Рm
И1	c11	c12	…	c1n
И2	c21	c22	…	c2n
…	…	…	…	…
Иn	cn1	cn2	…	cnm

При этом возможны два случая:

а) число исполнителей n больше числа выполняемых работ m (n > m),

б) число исполнителей n меньше числа выполняемых работ m (n m, вводится k = n – m фиктивных работ P_m+1, P_m+2, …, P_m+k. Во втором случае (n m) т.к. мы формируем данные для задачи из таблицы 2, то сведем её к следующему виду:

Таблица 3. Несбалансированная задача о назначениях. Случай а.

	Объект 1	Объект 2	Объект 3	Объект 4	Объект 5	Объект 6
Кран 1	23,50	20,3	22,5	19	0	0
Кран 2	31,2	30	31	27,5	0	0
Кран 3	31,2	31,1	31,5	30	0	0
Кран 4	28,5	32	25,5	28,5	0	0
Кран 5	32,5	33,2	31,5	29	0	0
Кран 6	30	32,2	29,3	30	0	0

Таким образом целевая функция будет иметь вид:

Случай б: (n

Код для цитирования: Скопировать