Построим математические модели задач:
1. Несбалансированная транспортная задача:
Пусть имеется m источников финансирования А1, А2, ..., Аm и n периодов финансирования В1, B2, ..., Вn. Известны затраты, связанные с выделением единицы денежных ресурсов Сij из i-го источника в j-ом периоде, а также объемы финансирования из каждого i-го источника в течение всего времени – аi. Известны суммарные объемы финансирования из всех источников в каждый j-й период времени – bj. Требуется определить объемы финансирования xij из i-го источника в j-ом периоде, чтобы:
1. Ресурсы всех источников были реализованы.
2. Обеспечить финансирование в полном объеме в каждом периоде.
3. Достигнуть экстремума выбранного критерия оптимизации.
Различают закрытую (сбалансированную) и открытую (несбалансированную) транспортную задачу. Транспортная задача, в которой суммарные запасы и потребности совпадают, т.е., называется закрытой; в противном случае − открытой. Для открытой транспортной задачи возможны два случая:
а) суммарные запасы превышают суммарные потребности ;
б) суммарные потребности превышают суммарные запасы.
Линейная целевая функция одинакова в обоих случаях, изменяется только вид системы ограничений, при этом открытая задача решается сведением к закрытой модели путем введения фиктивных пунктов доставки или источников ресурса.
В случае а), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель Вm+1 потребность которого составит
(1).
В случае б), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик Аn+1, запасы которого составляют
(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. Определим неизвестные и их количество.
Обозначим через xij количество песка (м3), перемещаемого из i-го карьера на j-ю стройку. Учтем несбалансированность задачи и введем фиктивного потребителя (Стройку 5) с нулевыми расходами на перевозку песка. Получаем потребность фиктивного потребителя по формуле (1). Таким образом, элементы xijобразуют матрицу перевозок 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*x11+35*x12+20*x13+40*x14+0*x15+50*x21+30*x22+50*x23+20*x24+
+0*x25+20*x31+30*x32+35*x33+45*x34+0*x35 → min(1а´)
3. Сформулируем ограничения рассматриваемой задачи.
3.1. Необходимо вывезти весь песок с карьеров:
(2а´)
3.2. Удовлетворить потребности каждой стройки в песке.
(3а´)
3.3. Введем граничные условия, которые определяют предельно допустимые значения искомых переменных (условие неотрицательности):
x11≥0, x12≥0, x13≥0, x14≥0, x15≥0, x21≥0, x22≥0, x23≥0, x24≥0, x25≥0,
x31≥0, x32≥0, x33≥0, x34≥0, x35≥0 (4а´)
Таким образом, целевая функция (1а´) и ограничения (2а´− 4а´) образуют математическую модель несбалансированной транспортной задачи случая а.
Решение в среде MS Excel:
Рис 1. Математическая модель и матрица перевозок. |
Рис 2. Решение с помощью надстройки «Поиск решения» |
Рис 3. Результат решения задачи |
Случай б: суммарные потребности превышают суммарные запасы.
Для того чтобы определить начальные условия и построить математическую модель данного типа изменим данные таблицы 1, увеличив потребности строек на 300 единиц.
1. Определим неизвестные и их количество.
Обозначим через xij количество песка (м3), перемещаемого из i-го карьера на j-ю стройку. Учтем несбалансированность задачи и введем фиктивный источник ресурса (Карьер 4) с нулевыми расходами на перевозку песка. Получаем запас ресурса на фиктивном источнике по формуле (2). Таким образом, элементы xijобразуют матрицу перевозок 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*x11+35*x12+20*x13+40*x14 +50*x21+30*x22+50*x23+20*x24+
+20*x31+30*x32+35*x33+45*x34+0*x14+0*x24 +0*x34 +0*x44→ min(1б´)
3. Сформулируем ограничения рассматриваемой задачи.
3.1. Необходимо вывезти весь песок с карьеров:
(2б´)
3.2. Удовлетворить потребности каждой стройки в песке.
(3б´)
3.3. Введем граничные условия, которые определяют предельно допустимые значения искомых переменных (условие неотрицательности)
x11≥0, x12≥0, x13≥0, x14≥0, x21≥0, x22≥0, x23≥0, x24≥0,
x31≥0, x32≥0, x33≥0, x34≥0, x41≥0, x42≥0, x43≥0, x44≥0 (4б´)
Таким образом, целевая функция (1.б´) и ограничения (2.б´− 4.б´) образуют математическую модель несбалансированной транспортной задачи случая б.
Решение в среде MS Excel:
Рис 4. Математическая модель и матрица перевозок. |
Рис 5. Решение с помощью надстройки «Поиск решения» |
Рис 6. Результат решения задачи |
Решить задачу о назначении значит распределить исполнителей (людей или механизмы) по имеющимся работам так, чтобы выполнение всех работ сопровождалось минимальными суммарными затратами. При этом, если количество исполнителей равно количеству выполняемых работ, то задача о назначениях является сбалансированной, в противном случае наоборот. Задача о назначениях является частным случаем транспортной задачи.
Рассмотрим решение несбалансированной задачи о назначениях, когда число исполнителей 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 фиктивных работ Pm+1, Pm+2, …, Pm+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