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

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

Чтобы ввести исходные данные вручную нужно выполнить следующие действия.1. В строке ′Метод ввода данных′ ⇑, нужно поставить переключатель в положение ′Вручную′.2. Ввести число поставщиков a, число потребителей b, и нажать кнопку ′Применить′.3.

В появившейся таблице заполнить столбец мощностей поставщиков ai, строку мощностей потребителей bj, и матрицу затрат cij.4.

Выбрать метод расчета начального опорного плана – отметить либо ′Метод наименьшей стоимости′, либо ′Метод северо-западного угла′.5. Нажать кнопку ′Рассчитать′. В результате появится подробное решение задачи.6. После расчета можно сохранить исходные данные.

Для этого в строке ′Метод ввода данных′ ⇑, нужно отметить ′Из электронной таблицы′. В текстовом поле будут исходные данные задачи. Их можно скопировать в буфер обмена и вставить в электронную таблицу или текстовый документ. Для этого нужно нажать кнопку ′Копировать′.

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

Исходными данными являются мощности поставщиков ai, мощности потребителей bj и затраты на перевозки cij.

Все исходные данные вводятся в таблице, у которой m 1 строк и n 1 столбцов. При этом либо первая слева клетка (1, 1), либо клетка (m 1, n 1) справа в последнем ряду, пустая.

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

Выбор новых базисных переменных

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

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

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

Поскольку мы ищем минимальное значение F, то отрицательные оценки указывают, что целевая функция уменьшится при включении переменной в базис.

Чем меньше значение , тем сильнее будет уменьшение F, в расчете на одну поставку. Поэтому, если у нас несколько свободных клеток с отрицательными оценками, то нужно вводить в базис переменную, с наименьшей оценкой.

Проиллюстрируем переход от одного базиса к другому на следующем примере. Пусть у нас имеется следующий опорный план.

Здесь базисные переменные:.Значение целевой функции:.

Определяем потенциалы. Для этого выпишем уравнения (П.1) для базисных переменных:(П.5.1)   ;(П.5.2)   ;(П.5.3)   ;(П.5.4)   ;(П.5.5)   ;(П.5.6)   .

Полагаем . Из уравнений (П.5.1), (П.5.2) и (П.5.3) находим:.

Из уравнения (П.5.6):.Из уравнения (П.5.5):.

Из уравнения (П.5.4):.В результате мы нашли потенциалы:.

Находим оценки свободных клеток.;;;;;.

Вводим переменную с наименьшей оценкой в базис. Для этого строим для нее цикл (см. Цикл – переход от одного базиса к другому ⇑).

Наименьшая поставка в клетках, отмеченных знаком ′–′:   в клетке (1, 1). Выполняем сдвиг по циклу на величину .Значение целевой функции нового опорного плана:.

Изменение целевой функции после введения в базис переменной :.

Как и следовало ожидать, оно равно произведению на :.

Закрытая и открытая модели

Согласно теореме о существовании решения ⇑, чтобы транспортная задача имела решение, сумма мощностей поставщиков должна равняться сумме мощностей потребителей:.

Транспортная задача с правильным балансом

– это задача, у которой сумма запасов (мощностей) поставщиков равна сумме потребностей (мощностей) потребителей. Математическая модель такой задачи называется закрытой.

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

– это задача, у которой сумма запасов (мощностей) поставщиков не равна сумме потребностей (мощностей) потребителей. Математическая модель такой задачи называется открытой.

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

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

. При этом общее число N переменных равно произведению числа поставщиков на число потребителей: .

Чтобы использовать общие положения линейного программирования, нам нужно сделать переход от нумерации двумя индексами к нумерации одним индексом. Рассмотрим такой переход на примере с . Выпишем уравнения системы ограничений (М.2), (М.3) для этого случая:

Введем переменные, нумерованные одним индексом:.

Тогда система ограничений примет обычный для задач ЛП вид:Ее можно записать в матричном виде:, где ;   ;   .

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

В нашем примере векторы условий имеют следующий вид:m и n, система ограничений транспортной задачи имеет каноническую форму:, где,   .Элементы матрицы A удобно выразить через векторы условий. Тогда матрицу можно записать в виде одной строки:, где.

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

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

Идут вычисления …

Как решить транспортную задачу. руководство

Метод северо-западного угла

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

Если первый поставщик реализует весь свой запас, то вычеркиваем первую строку. Если первый потребитель получит требуемое количество груза, то вычеркиваем первый столбец. Если и первый поставщик реализовал весь свой запас, и первый потребитель получил требуемое количество груза , то вычеркиваем на выбор, или первую строку, или первый столбец. За один шаг можно вычеркнуть только одну строку или один столбец.

См. Пример составления первого опорного плана методом северо-западного угла.

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

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

Множественное решение

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

Предположим, что оценка свободной клетки равна нулю. Тогда, в силу (П.3),(П.6)   .

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

Тогда для определения потенциалов, мы получим ту же систему уравнений (П.1), в которой вместо уравнения будет уравнение (П.6). Но поскольку при решении первой системы мы получили, что уравнение (П.6) выполняется, тогда и новой системе удовлетворяют те же значения потенциалов. Поэтому новый план также будет оптимальным.

См. Пример решения транспортной задачи методом потенциалов

Использованная литература:С. Гасс. Линейное программирование (методы и приложения). Москва, «Государственное издательство физико-математической литературы», 1961.Общий курс высшей математики для экономистов. Под общей редакцией В. И. Ермакова.

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

Открыть в новой вкладке с параметрами по умолчанию

Открытая модель

Если задача с неправильным балансом, то система ограничений (М.2), (М.3), (М.4) не имеет решений, поскольку, или часть потребителей не получат требуемое количество, или часть поставщиков не смогут реализовать все грузы.

То есть уравнения системы ограничений не будут выполняться ни при каком плане перевозок . Чтобы исправить ситуацию, мы должны или в (М.2), или в (М.3), заменить равенства равенствами.

Пусть сумма мощностей поставщиков меньше суммы мощностей потребителей:.Тогда часть потребителей не получат требуемого количества груза.

При этом все поставщики смогут реализовать груз в полном объеме. Это означает, что количество полученного потребителем j груза, , может быть меньше его потребности .

Аналогичным образом, пусть сумма мощностей поставщиков больше суммы мощностей потребителей:.В этом случае, можно составить такой план перевозок, при котором все потребители получат требуемое количество груза, но часть поставщиков не реализуют свой груз в полном объеме.

То есть количество отправленного поставщиком i груза, , может быть меньше имеющегося запаса .

Таким образом, в открытой задаче всегда подразумевается, что если сумма мощностей поставщиков меньше суммы мощностей потребителей, то вместо уравнений (М.3) стоят неравенства (Т.1). Если сумма мощностей поставщиков больше суммы мощностей потребителей, то вместо (М.2) будут неравенства (Т.2).

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

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

То есть весь груз нужно перевезти от поставщиков к потребителям. Считаем, что есть m поставщиков и n потребителей. Пронумеруем поставщиков от единицы до m.

Пусть в i-ом складе поставщика имеется ai единиц груза, . И пусть каждый j-ый потребитель может принять только определенное количество груза bj,.

Известна стоимость cij перевозки единицы груза от i-го поставщика к j-му потребителю. Требуется составить такой план перевозок, то есть определить количество груза xij, которое нужно перевести от i-го поставщика к j-му потребителю, при котором весь груз от поставщиков будет перевезен к потребителям с минимальными затратами на перевозки.

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

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

Если просуммировать xij по всем потребителям j, то получим суммарное количество груза, перевезенного от i-го поставщика ко всем потребителям.

Если просуммировать xij по всем поставщикам i, то получим суммарное количество груза, доставленного j-му потребителю от всех поставщиков.

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

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

Построение первого опорного плана

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

Транспортная задача (М.1) – (М.4) имеет каноническую форму. Тогда, согласно теореме о числе базисных переменных, число базисных переменных в любом опорном плане равно рангу r матрицы коэффициентов системы ограничений.

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

Остальные переменные равны нулю. Это не означает, что все базисные переменные отличны от нуля. Некоторые базисные переменные также могут иметь нулевые значения. Но свободные переменные всегда равны нулю, а базисные переменные определяются из решения системы ограничений (М.2) – (М.3).

О ячейках со свободными переменными говорят как о свободных, или пустых. Ячейки с базисными переменными называют занятыми.

Приведение открытой модели к закрытой

Открытую модель можно легко привести к закрытой, если добавить фиктивного поставщика или потребителя с нулевыми затратами на перевозки.

Так, если , то мы вводим фиктивного поставщика с мощностью , и нулевыми затратами .

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

Решение транспортной задачи методом потенциалов

Транспортную задачу можно решить различными методами, применяемыми в линейном программировании. При этом наиболее широко используются методы, которые позволяют получить решение, используя специфический вид системы ограничений (М.2) – (М.3).

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

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

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

Сохранение данных расчета

После того как выполнен расчет, можно сохранить его данные. Это можно сделать тремя способами.

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

2) После выполнения расчета можно открыть вкладку Метод ввода данных: Из электронной таблицы ⇑, и нажать кнопку «Копировать». В результате данные будут скопированы в буфер обмена. Затем можно вставить данные из буфера обмена в электронную таблицу, нажав Ctrl-V, и сохранить саму электронную таблицу.

3) Можно выделить данные расчета курсором, скопировать в буфер обмена, и вставить в текстовый документ, поддерживающий работу с таблицами. После чего сохранить текстовый документ.

Использованная литература:Общий курс высшей математики для экономистов. Под общей редакцией В. И. Ермакова. Москва, «ИНФРА-М», 2007.К. Н. Лунгу. Линейное программирование. Руководство к решению задач. Москва, «ФИЗМАТЛИТ», 2005.

Таблицы для расчетов

Выполнение решения транспортной задачи удобно проводить в таблицах. Обычно их заполняют следующим образом.

Верхняя левая клетка является пустой. Под ней расположен столбец из m клеток со значениями мощностей поставщиков . В верхнем ряду расположена строка из n клеток со значениями мощностей потребителей .

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

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

При вычислении оценок, таблицу дополняют еще одним столбцом и строкой, в которые записывают значения потенциалов и . В таких таблицах строки и столбца.

При обращении к определенной клетке, указывают ее номер, состоящий из двух цифр, точно так, как и при обращении к элементам матрицы издержек . То есть, например, когда мы говорим, что это клетка (1, 2), то тем самым подразумеваем, что это клетка, в которой записано значение .

Первой строкой считается строка, относящаяся к первому поставщику . А первым столбцом – к первому потребителю .

Расчетная таблица транспортной задачи

Теорема о ранге матрицы системы ограничений

Ранг матрицы системы ограничений (М.2) – (М.3) транспортной задачи равен m n – 1.Доказательство

Теорема о существовании решения транспортной задачи

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

Теоремы

Ниже приводим важные теоремы, имеющие отношение к циклам.

Теорема о линейной зависимости векторов-условийВыберем произвольным образом некоторое множество векторов-условий ⇑, которые как известно, являются столбцами матрицы коэффициентов A.

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

Теорема о существовании и единственности циклаЕсли таблица транспортной задачи заполнена опорным планом, то для любой свободной клетки существует цикл, причем единственный.

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

Улучшение плана методом потенциалов

Выше мы показали, как построить начальный опорный план транспортной задачи. Также мы выяснили, как переходить от одного базиса к новому, включая в него одну из свободных переменных, и исключая одну из базисных. Теперь выясним правило выбора свободной переменной, включаемой в базис, чтобы в результате переходов от одного базиса к другому, мы за конечное число шагов пришли к оптимальному плану. Для этого нужно воспользоваться следующими теоремами.

Теорема (признак оптимальности опорного решения)Если опорный план транспортной задачи является оптимальным, то существуют чисел , удовлетворяющих следующим условиям:(П.1)     для базисных переменных ;(П.2)     для свободных переменных .

Оценками свободных переменных

называются величины
(П.3)   ,
где – издержки на перевозки; и – потенциалы поставщиков и потребителей. Величины также называют оценками свободных клеток таблицы, или оценками векторов-условий.

Теорема об оценках свободных переменныхЕсли в базис ввести свободную переменную , то изменение целевой функции составит,где – оценка переменной ⇑.

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

Например, потенциальная энергия U тела, находящегося в поле тяготения Земли, или другой планеты, зависит от расстояния r до ее центра: .

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

Если рассмотреть уравнения (П.1) – (П.2), то видно, что они не изменятся, если вместо и подставить другие величины и , отличающихся от прежних на произвольную постоянную C:(П.4)   .

В самом деле, подставляя (П.4) в (П.1) и (П.2), постоянная сокращается:;.

И соотношения для и имеют тот же вид, что и (П.1) – (П.2):;.

Поэтому, при определении потенциалов и , мы можем присвоить одному из них произвольное значение. Мы будем полагать, что.Тогда из уравнений (П.1) легко определить остальные потенциалы.

Когда мы определим все потенциалы и , нужно проверить выполнение неравенств (П.2). Если они выполняются, то план оптимален. Если нет, то план не оптимален, нужно переходить к другим базисным переменным.

Цикл – переход от одного базиса к другому

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

Циклом в транспортной задаче

называется замкнутая последовательность клеток таблицы, которые называются вершинами цикла, обладающая следующими свойствами.
1) Две соседние вершины располагаются в одной строке или одном столбце. То есть геометрически, изображение цикла состоит из чередования горизонтальных и вертикальных линий, соединяющихся в вершинах цикла.
2) В любой строке или столбце таблицы могут располагаться только две вершины цикла, или ни одной.

Занятая клетка

(заполненная клетка) – это клетка таблицы транспортной задачи, в которой записано значение базисной переменной. Клетки, соответствующие базисным переменным заполняются всегда, даже для нулевых значений.

Свободная клетка

(пустая клетка) – это клетка таблицы транспортной задачи, относящаяся к свободной переменной. Все свободные переменные равны нулю. Однако нулевые значения для свободных клеток не заполняют, оставляя поле для переменной пустым.

Циклом для выбранной свободной клетки

(или просто циклом для клетки) называется цикл, у которого одна из вершин находится в выбранной свободной клетке, а остальные вершины – в занятых клетках.

Сдвигом по циклу

на величину θ называется операция, при которой свободной клетке присваивается значение θ; ко всем отстоящих от нее четным вершинам цикла прибавляются поставки на величину θ; а из всех отстоящих от нее нечетных вершин цикла вычитаются поставки на величину θ.

Простейшим циклом является прямоугольник. Вот примеры более сложных циклов. Вершины циклов отмечены знаком ′ ′ или ′–′.

Особенностью цикла является то, что прибавление и вычитание одинакового количества поставок в его смежных вершинах, не нарушает выполнение системы уравнений (М.2) – (М.3). Это позволяет видоизменять начальный план перевозок, включая в него новые переменные, и исключая старые.

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

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

Соответствующая ей клетка (5, 1) свободная.2) Строим цикл для выбранной свободной клетки. Как указано в определении ⇑, у такого цикла одна вершина находится в выбранной свободной клетке, а другие вершины – в занятых клетках (с базисными переменными).

В рассматриваемой таблице ⇑, это цикл с вершинами (5, 1); (5, 2); (2, 2); (2, 3); (3, 3) и (3, 1). 3)

Отмечаем вершину цикла выбранной свободной клетки знаком ′ ′. Далее отмечаем остальные вершины знаками ′–′ и ′ ′, чередуя их. Теперь если увеличить значения переменных со знаком ′ ′ и уменьшить значения переменных со знаком ′–′ на одно и то же число, то это не приведет к нарушению баланса.

То есть система уравнений (М.2) – (М.3) по прежнему будет выполняться. Однако, если изменить переменные на слишком большое число, то это может привести к появлению отрицательных значений, что не допустимо. Чтобы такого не произошло, переходим к следующему шагу.4)

Находим наименьшее значение переменной для клеток, помеченных знаком ′–′. Для нашей таблицы ⇑ это клетка (3, 1) со значением .

То есть 5) В клетках, отмеченных знаком ′ ′, прибавляем ; в клетках со знаком ′–′, вычитаем .

То есть выполняем сдвиг по циклу ⇑ на величину . В результате свободная клетка, для которой строился цикл окажется заполненной значением , то есть соответствующая ей переменная станет базисной.

А значение переменной с наименьшим начальным значением , станет равным нулю. Эту переменную мы исключаем из базиса. В результате переходим к новому набору базисных переменных. Для нашего примера он отображен во второй таблице ⇑.

На последнем шаге может оказаться, что несколько базисных переменных станут равными нулю. Тогда мы исключаем из базиса любую из них. Остальные будут в базисе с нулевыми значениями.

Также может встретиться случай, когда минимальное значение в клетке, помеченной знаком ′–′ равно нулю: . Тогда значения переменных не изменятся, но мы все равно переходим к новому базису.