Транспортные задачи как решать

Решение транспортной задачи – онлайн калькулятор

Онлайн калькулятор для решения транспортной задачи методом потенциалов. Расчет первого опорного плана осуществляется методом наименьшей стоимости или методом северо-западного угла. Решение выполняется как для закрытой, так и для открытой модели.

Онлайн калькулятор

Исходные данные задачи

Метод ввода данных:
Вручную Из электронной таблицы

Редактировать Рассчитать Копировать Удалить все
Идут вычисления .

Достигнуто максимальное число шагов, но задача не решена. Можно продолжить вычисления, добавив желаемое количество шагов.

Руководство по использованию калькулятора

Математическая модель задачи

Пусть некоторый продукт, который будем называть грузом, нужно перевезти от m поставщиков к n потребителям. При этом у поставщика с номером i имеется a_i единиц груза, ; потребителю с номером j требуется b_j единиц груза, . Величины a_i и b_j мы будем называть, соответственно, мощностью i — го поставщика и мощностью j — го потребителя. Известны величины стоимости c_ij перевозки единицы груза от i — го поставщика к j — му потребителю. Пусть x_ij – количество груза, перевезенного от i — го поставщика к j — му потребителю. Организовать перевозки можно различными способами, то есть величины x_ij можно выбрать с помощью различных вариантов. Требуется определить такие значения величин x_ij , при которых суммарные затраты F на перевозки будут минимальными: .

Таким образом, математическая модель задачи имеет следующий вид:

.

Предлагаемый калькулятор позволяет решить транспортную задачу онлайн методом потенциалов.

Ввод исходных данных

Исходными данными являются мощности поставщиков a_i , мощности потребителей b_j и затраты на перевозки c_ij . Все исходные данные вводятся в таблице, у которой m + 1 строк и n + 1 столбцов. При этом либо первая слева клетка (1, 1) , либо клетка (m + 1, n + 1) справа в последнем ряду, пустая.

Существует два способа ввода данных:
1. Вручную, вводом значений в соответствующие поля.
2. Загружая данные из электронной таблицы.

Ввод данных вручную

Чтобы ввести исходные данные вручную нужно выполнить следующие действия.
1. В строке ′Метод ввода данных′ ⇑, нужно поставить переключатель в положение ′Вручную′.
2. Ввести число поставщиков a , число потребителей b , и нажать кнопку ′Применить′.
3. В появившейся таблице заполнить столбец мощностей поставщиков a_i , строку мощностей потребителей b_j , и матрицу затрат c_ij .
4. Выбрать метод расчета начального опорного плана – отметить либо ′Метод наименьшей стоимости′, либо ′Метод северо-западного угла′.
5. Нажать кнопку ′Рассчитать′. В результате появится подробное решение задачи.
6. После расчета можно сохранить исходные данные. Для этого в строке ′Метод ввода данных′ ⇑, нужно отметить ′Из электронной таблицы′. В текстовом поле будут исходные данные задачи. Их можно скопировать в буфер обмена и вставить в электронную таблицу или текстовый документ. Для этого нужно нажать кнопку ′Копировать′. Данные будут скопированы в буфер обмена. Далее можно открыть электронную таблицу или текстовый документ, и вставить данные из буфера обмена, нажимая Ctrl-V . После чего сохранить изменения в документе.

Ввод данных из электронной таблицы

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

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

Транспортная задача – основные понятия, определения и теоремы

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

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

Постановка задачи

Пусть некоторый продукт, который мы будем называть грузом, нужно перевезти с одних складов в другие. Склады, в которых первоначально находится груз, мы будем называть поставщиками. Склады, в которые нужно перевести груз, будем называть потребителями. То есть весь груз нужно перевезти от поставщиков к потребителям. Считаем, что есть m поставщиков и n потребителей. Пронумеруем поставщиков от единицы до m . Пусть в i -ом складе поставщика имеется a_i единиц груза, . И пусть каждый j -ый потребитель может принять только определенное количество груза b_j , . Известна стоимость c_ij перевозки единицы груза от i -го поставщика к j -му потребителю. Требуется составить такой план перевозок, то есть определить количество груза x_ij , которое нужно перевести от i -го поставщика к j -му потребителю, при котором весь груз от поставщиков будет перевезен к потребителям с минимальными затратами на перевозки.

Построим математическую модель транспортной задачи. Затраты на перевозку груза от i -го поставщика к j -му потребителю равны произведению стоимости перевозки единицы груза на количество перевозимого груза. Суммируя по всем поставщикам и потребителям, получим суммарную стоимость перевозок:
.
Задача состоит в том, чтобы подбором величин , сделать суммарную стоимость перевозок минимальной:
.

Если просуммировать x_ij по всем потребителям j , то получим суммарное количество груза, перевезенного от i -го поставщика ко всем потребителям. Оно должно равняться запасам a_i этого поставщика:
.

Если просуммировать x_ij по всем поставщикам i , то получим суммарное количество груза, доставленного j -му потребителю от всех поставщиков. Оно должно равняться потребностям b_j этого потребителя:
.

Также мы должны учесть, что количество перевезенного груза не может быть отрицательным:
.

В результате, мы получаем математическую модель транспортной задачи:

.

Определение транспортной задачи

Транспортная задача – это задача линейного программирования следующего вида:
(М.1)
(М.2)
(М.3)
(М.4) ,
где .
В транспортной задаче требуется определить количество груза , которое нужно перевезти от -го поставщика к -му потребителю, чтобы перевезти весь груз от поставщиков к потребителям, и при этом суммарные затраты на перевозки были минимальны.
Здесь – стоимость перевозки единицы груза от -го поставщика к -му потребителю; – мощность -го поставщика, то есть максимальное количество груза, которое может отправить этот поставщик; – мощность -го потребителя, то есть максимальное количество груза, которое может принять этот потребитель; m – число поставщиков; n – число потребителей.
Матрица транспортных издержек – это матрица, составленная из элементов , каждый из которых равен затратам на перевозку единицы груза от -го поставщика к -му потребителю.
План перевозок транспортной задачи – это совокупность переменных , каждая из которых равна количеству груза, перевозимого от -го поставщика к -му потребителю. Эти переменные удовлетворяют условиям (М.2), (М.3) и (М.4). План перевозок обычно записывают в виде матрицы.

Исследование математической модели

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

Rfid защита что это

Как запаять морозилку в холодильнике

Как снять пароль с телефона самсунг галакси

Какая может быть тень