Навигация
1. ОСНОВНАЯ ЧАСТЬ
1.1 МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ
Транспортная задача-
Однородный груз сосредоточен у т поставщиков в объемах 
.
Данный груз необходимо доставить п потребителям в объемах 
.
Известны 
(i=1,2,…,m; j=1,2,…,n)- стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью и суммарные затраты на перевозку всех грузов минимальны.
Исходные данные транспортной задачи записываются в таблице вида
Таблица 1
| | | … | | |
|
| | | … | |
|
| | | … | |
| … | … | … | … | … |
|
| | | … | |
Переменными(неизвестными) транспортной задачи являются 
(i=1,…,m;i=1,2,…,n)- объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные могут быть записаны в матрице перевозок 
Математическая модель транспортной задачи в общем случае имеет вид
(1.1)
i=1,2,…,m, (1.2)
j=1,2,…,n, (1.3)
i=1,2,…,m; j=1,2,…,n. (1.4)
Целевая функция задачи (1.1) выражает требования обеспечить минимум суммарных затрат на перевозку всех грузов. Первая группа из т уравнений (1.2) описывает тот факт, что запасы всех т поставщиков вывозятся полностью. Вторая группа из n уравнений (1.3) выражает требования полностью удовлетворить запросы всех n потребителей. Неравенства (1.4) являются условиями неотрицательности всех переменных задачи.
Таким образом, математическая формулировка транспортной задачи состоит в следующем: найти переменные задачи
i=1,2,…,m; j=1,2,…,n,
удовлетворяющее системе ограничений (1.2), (1.3), условиям неотрицательности (1.4) и обеспечивающее минимум целевой функции (1.1).
В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е.
.
Такая задача называется задачей с правильным балансом, а ее модель- закрытой. Если же это неравенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель- открытой.
Для того чтобы транспортная задача линейного программирования имела решение, необходимо и достаточно, чтобы суммарные запасы поставщиков равнялись суммарным запросам потребителей, т.е. задача должна быть с правильным балансом.
Пример 1:
Составить математическую модель транспортной задачи перевоза груза из двух складов в 3 магазина:
Таблица 2
|
| 50 | 70 | 80 |
| 90 | 9 | 5 | 3 |
| 110 | 4 | 6 | 8 |
Решение. Введем переменные задачи(матрицу перевозок)
Запишем матрицу стоимостей
.
Целевая функция задачи равна сумме произведений всех соответствующих элементов матриц С и Х:
Данная функция, определяющая суммарные затраты на все перевозки, должна достигать минимального значения.
Составим систему ограничений задачи. Сумма всех перевозок, стоящих в первой строке матрицы Х, должна равняться запасам первого поставщика, а сумма перевозок во второй строке матрицы Х – запасам второго поставщика:
Это означает, что запасы поставщиков вывозятся полностью.
Суммы перевозок, стоящих в каждом столбце матрицы Ч, должны быть равны запросам соответствующих потребителей:
Это означает, что запросы потребителей удовлетворяются полностью.
Необходимо также учитывать, что перевозки не могут быть отрицательными:
i=1,2,…,m; j=1,1,…,n.
Ответ: математическая модель задачи формулируется следующим образом: найти переменные задачи, обеспечивающие минимум функции
и удовлетворяющие системе ограничений
и условиям неотрицательности
i=1,2,…,m j=1,2,…,n.
1.2 АЛГОРИТМ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ
1.2.1 СБАЛАНСИРОВАННОСТЬ ТРАНСПОРТНОЙ ЗАДАЧИ
Транспортная задача является сбалансированной, если суммарные запасы поставщиков равны суммарным запросам потребителей, т.е.
.
Если транспортная задача не сбалансирована, то возникают особенности в ее решении.
Особенности решения транспортных задач с неправильным балансом:
1.Если суммарные запасы поставщиков превосходят суммарные запросы потребителей, т.е.
то необходимо ввести фиктивного (n+1)-го потребителя с запросами 
равными разности суммарных запасов поставщиков и запросов потребителей, и нулевыми стоимостями перевозок единиц груза 
2. Если суммарные запросы потребителей превосходят суммарные запасы поставщиков, т.е.
то необходимо ввести фиктивного (m+1)-го поставщика с запасами 
равные разности суммарных запросов потребителей и запасов поставщиков, и нулевыми стоимостями перевозок единиц груза 
3. При составлении начального опорного решения в последнюю очередь следует распределять запасы фиктивного поставщика и удовлетворять запросы фиктивного потребителя, несмотря на то, что им соответствует наименьшая стоимость перевозок, равная нулю.
Похожие работы
... пункт отправления Am+1 с запасов am+1 равным недостающему запасу и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равным нулю. 5. Составление опорного плана. Решение транспортной задача начинается с нахождения опорного плана. Для этого существуют различные способы. Например, способ "северо-западного угла", способ минимальной стоимости по строке, способ ...
... сразу же составлен план перевозок, удовлетворяющий балансовым условиям. Полученное решение является опорным решением транспортной задачи. Составленный нами план перевозок, не является оптимальным по стоимости, так как при его построении мы совсем не учитывали стоимость перевозок Сij . 3. Метод потенциалов. Пусть имеется транспортная таблица, соответствующая начальному решению, хil= для ...
... . При этом значения cij соответствуют коэффициентам целевой функции исходной замкнутой транспортной задачи (1) и в последующем не изменяются. Элементы xij соответствуют значениям переменных промежуточных решений транспортной задачи линейного программирования и изменяются на каждой итерации алгоритма. Если в некоторой ячейке xij=0, то такая ячейка называется свободной, если же xij>0, то такая ...
... ). Требуется распределить все работы между всеми рабочими так, чтобы время выполнения работ было минимальным, а каждую работу выполнял только один рабочий. §4. Решение транспортной задачи в Excel В качестве примера я рассмотрел транспортную задачу для 2 складов и 5 магазинов. · В ячейки C4:C5 записал объемы продукции, имеющиеся на 2 складах. · В ячейки E5:I5 - заявки на продукцию, ...
0 комментариев