Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Переменными (неизвестными) транспортной задачи являются хij, i =1,2,..., m, j= 1, 2, ..., п — объемы перевозок от каждого i -го поставщика каждому j -му потребителю. Эти переменные можно записать виде матрицы перевозок:
.
Так как произведение сijхij определяет затраты на перевозку груза от i -го поставщика j -му потребителю, то суммарные затраты на перевозку всех грузов равны . По условию задачи требуется обеспечить минимум суммарных затрат. Следовательно, целевая функция имеет вид:
F (X)= → min.
Система ограничений задачи состоит из двух групп уравнений. Первая группа из т уравнений описывает тот факт, что запасы всех т поставщиков вывозятся полностью:
, i =1, 2,..., т.
Вторая группа из п уравнений выражает требование полностью удовлетворить запросы всех п потребителей:
, j = 1, 2,..., п.
Учитывая условие неотрицательности объемов перевозок, математическую модель задачи можно записать так:
F (X) = → min,
, i =1, 2,..., т, , j =1, 2,..., п, хij ≥ 0, i =1,2,..., т, j =1,2,..., п.
В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е.
= .
Такая задача называется задачей с правильным балансом, а ее модель ― закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель — открытой.
Математическая формулировка транспортной задачи такова: найти переменные задачи Х=(хij), i =1, 2,..., т, j = 1, 2,..., п,удовлетворяющие системе ограничений, условиям неотрицательности и обеспечивающие минимум целевой функции. Математическая модель транспортной задачи может быть записана и векторномвиде. Для этого рассмотрим матрицу А системы уравнений-ограничений задачи:
х 11 х 12 … х 1 n x 21 x 22… x 2 n … xm 1 xm 2… xmn
Сверху над каждым столбцом матрицы указана переменная задачи, коэффициентами при которой являются элементы соответствующего столбца в уравнениях системы ограничений. Каждый столбец матрицы А, соответствующий переменной хij, является вектором-условием задачи и обозначается через Аij. Каждый вектор имеет всего т + п координат, и только две из них, отличные от нуля, равны единице. Первая единица вектора Аij, стоит на i -м месте, а вторая на (т +j) - мместе, т.е.
Номер
координаты
Обозначим через А 0 вектор ограничений и представим систему ограничений задачи в векторном виде. Тогда математическая модель транспортной задачи запишется следующим образом:
F (X) = → min,
,
хij ≥ 0, i =1,2,..., т, j =1,2,..., п.
Пример. Составить математическую модель транспортной задачи, исходные данные которой приведены в таблице:
bj ai | |||
Решение. Введем переменные задачи (матрицу перевозок):
.
Запишем матрицу стоимостей:
.
Целевая функция задачи равна сумме произведений всех соответствующих элементов матриц С и X:
F (X) = 3 х 11+ 5 х 12 + 7 х 13 + 4 х 21 + 6 х 22 + 10 х 23.
Данная функция, определяющая суммарные затраты на все перевозки, должна достигать минимального значения.
Составим систему ограничений задачи. Сумма всех перевозок, стоящих в первой строке матрицы X, должна равняться запасам 1-го поставщика, а сумма перевозок во второй строке матрицы X — запасам 2-го поставщика:
х 11 + х 12 + х 13 = 40, х 21 + х 22 + х 23 = 50.
Это означает, что запасы поставщиков вывозятся полностью. Суммы перевозок, стоящих в каждом столбце матрицы X, должны быть равны запросам соответствующих потребителей:
х 11+ х 21 = 20,
х 12+ х 22 = 30,
х 13+ х 23 = 40.
Это означает, что запросы потребителей удовлетворяются полностью. Необходимо также учитывать, что перевозки не могут быть отрицательными:
хij ≥ 0, i =1,2,..., т, j =1,2,..., п.
Следовательно, математическая модель рассматриваемой задачи такова: найти переменные задачи, обеспечивающие минимум функции
F (X) = 3 х 11+ 5 х 12 + 7 х 13 + 4 х 21 + 6 х 22 + 10 х 23
и удовлетворяющие системе ограничений
и условиям неотрицательности хij ≥ 0, i =1,2,..., т, j =1,2,..., п.
Дата публикования: 2015-11-01; Прочитано: 323 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!