В качестве критерия оптимальности транспортной. Критерий оптимальности базисного решения транспортной задачи

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

Х1,Х2,Х3,…Хп.

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

Целевая функция. Это - выражение, значение которого инженер стремиться сделать максимальным или минимальным. Целевая функция позволяет количественно сравнить два альтернативных решения. С математической точки зрения целевая функция описывает некоторую (п+1) - мерную поверхность. Ее значение определяется проектными параметрами

М = М (х1,х2,…,хп).

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

Рисунок 1. Одномерная целевая функция.

Рисунок 2. Двумерная целевая функция.

Целевая функция в ряде случаев может принимать самые неожиданные формы. Например, ее не всегда удается выразить в замкнутой математической форме, в других случаях она может представлять собой кусочно-линейную функцию. Для задания целевой функции иногда может потребоваться таблица технических данных (например, таблица состояния водяного пара) или может понадобиться провести эксперимент. В ряде случаев проектные параметры принимают только целые значения. Примером может служить число зубьев в зубчатой передаче или число болтов во фланце. Иногда проектные параметры имеют только два значения - да или нет. Качественные параметры, такие как удовлетворение, которое испытывает приобретший изделие покупатель, надежность, эстетичность, трудно учитывать в процессе оптимизации, так как их практически невозможно охарактеризовать количественно. Однако в каком бы виде ни была представлена целевая функция, она должна быть однозначной функцией проектных параметров.

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

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

Рисунок 3. При изменении знака целевой функции на противоположный в задаче на минимум, превращает ее в задачу на максимум.

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

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

С1 (X1, X2, Х3, . . ., Хп) = 0,

С2 (X1, X2, Х3, . . ., Х п) = 0,

..……………………………..

Сj(X1, X2, Х 3, . . ., Хп) = 0.

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

z1 ?r1(X1, X2, Х3, . . ., Хп) ?Z1

z2 ?r2(X1, X2, Х3, . . ., Хп) ?Z2

………………………………………

zk ?rk(X1, X2, Х3, . . ., Хп) ?Zk

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

Прямые и функциональные ограничения. Прямые ограничения имеют вид

xнi ? xi ? xвi при i ? ,

где xнi , xвi - минимально и максимально допустимые значения i-го управляемого параметра; п - размерность пространства управляемых параметров. Например для многих объектов параметры элементов не могут быть отрицательными: xнi ? 0 (геометрические размеры, электрические сопротивления, массы и т.п.).

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

1) типа равенств
ш (Х) = 0; (2.1)
2) типа неравенств

ц (Х) › 0, (2.2)

где ш (Х) и ц (Х) - вектор-функции.

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

ХД = {Х | ш(Х) = 0, ц (Х)›0, xi › xнi ,

xi ‹ xвi при i ? }.

Если ограничения (2.1) и (2.2) совпадают с условиями работоспособности, то допустимую область называют также областью работоспособности ХР.

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

Локальный оптимум. Так называется точка пространства проектирования, в которой целевая функция имеет наибольшее значение по сравнению с ее значениями во всех других точках ее ближайшей окрестности. На рис.4 показана одномерная целевая функция, имеющая два локальных оптимума. Часто пространство проектирования содержит много локальных оптимумов и следует соблюдать осторожность, чтобы не принять первый из них за оптимальное решение задачи.

Рисунок 4. Произвольная целевая функция может иметь несколько локальных оптимумов.

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

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

Целевая функция должна быть одна (принцип однозначности). Сведение многокритериальной задачи к однокритериальной называют сверткой векторного критерия. Задача поиска его экстремума сводится к задаче математического программирования. В зависимости от того каким образом выбираются и объединяются выходные параметры, в скалярной функции качества, различают частные, аддитивные, мультипликативные, минимаксные, статистические критерии и другие критерии. В техническом задании на проектирование технического объекта указываются требования к основным выходным параметрам. Эти требования выражаются в виде конкретных числовых данных, диапазона их изменения, условия функционирования и допустимых минимальных или максимальных значений. Требуемые соотношения между выходными параметрами и техническими требованиями (ТТ) называют условиями работоспособности и записываются в виде:

yi < TTi , i О ; yi > TTj , j О ;

yr = TTr ± ?yr; r О .

где yi, yj, yr - множество выходных параметров;

TTi, TTj, TTr - требуемые количественные значения соответствующих выходных параметров по техническому заданию;

Yr - допустимое отклонение r-го выходного параметра от указанного в техническом задании значения TTr.

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

Частные критерии могут применяться в случаях, когда среди выходных параметров можно выделить один основной параметр yi(Х), наиболее полно отражающий эффективность проектируемого объекта. Этот параметр принимают за целевую функцию. Примерами таких параметров являются: для энергетического объекта - мощность, для технологического автомата - производительность, для транспортного средства - грузоподъемность. Для многих технических объектов таким параметром служит стоимость. Условия работоспособности всех остальных выходных параметров объекта относят при этом к функциональным ограничениям. Оптимизация на основе такой постановки называется оптимизацией по частному критерию.

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

Взвешенный аддитивный критерий применяют тогда, когда условия работоспособности позволяют выделить две группы выходных параметров. В первую группу входят выходные параметры, значения которых в процессе оптимизации нужно увеличивать y+i(X) (производительность, помехоустойчивость, вероятность безотказной работы и т. п.), во вторую - выходные параметры, значения которых следует уменьшать y-i (X) (расход топлива, длительность переходного процесса, перерегулирование, смещение и пр.). Объединение нескольких выходных параметров, имеющих в общем случае различную физическую размерность, в одной скалярной целевой функции требует предварительного нормирования этих параметров. Способы нормирования параметров будут рассмотрены ниже. Пока будем считать, что все у(Х) безразмерны и среди них нет таких, которым соответствуют условия работоспособности типа равенства. Тогда для случая минимизации целевой функции свертка векторного критерия будет иметь вид

где aj>0 - весовой коэффициент, определяющий степень важности j-го выходного параметра (обычно aj выбираются проектировщиком и в процессе оптимизации остаются постоянными).

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

определяет среднеквадратичное приближение yj(X) к заданным техническим требованиям TTj.

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

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

Критерий формы функции используют, когда ставится задача наилучшего совпадения заданной (эталонной) характеристики yТТ(Х,щ) с соответствующей выходной характеристикой y(Х,щ) проектируемого объекта, где щ - некоторая переменная, например частота, время, избранная фазовая переменная. К таким задачам относятся: проектирование системы автоматического регулирования, обеспечивающей требуемый вид переходного процесса по регулируемому параметру; определение параметров модели транзистора, дающих максимальное совпадение его теоретических вольт-амперных характеристик с экспериментальными; поиск параметров сечений балки, значения которых приводят к наилучшему совпадению заданной эпюры напряжений с расчетной, и т. п.

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

где р -- количество узловых точек щj на оси переменной щ; aj - весовые коэффициенты, значения которых тем больше, чем меньшее отклонение y(Х, щj) - yTT(Х, щj) нужно получить в j-и точке.

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

Введем количественную оценку степени выполнения j-го условия работоспособности, обозначим ее через zj и будем называть запасом работоспособности параметра yj. Расчет запаса по j-му выходному параметру можно выполнить различными способами, например,

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

Здесь предполагается, что все соотношения сведены к виду yi < TТj. Если yi > TТj , то -yj < -TТj . Следует принимать аj >1 (рекомендуемые значения 5 ? аj ? 20), если желательно достичь выполнения j-го технического требования с заданным допуском, т. е. yj = TТj ± ?yj; aj=l, если необходимо получить максимально возможную оценку zj.

Качество функционирования технической системы характеризуется вектором выходных параметров и, следовательно, вектором Z=(zm,zm,…,zm). Поэтому целевую функцию следует формировать как некоторую функцию ц(Z) вектора оценок. Например, если в качестве целевой функции рассматривается запас только того выходного параметра, который в данной точке X является наихудшим с позиций выполнения требований ТЗ, то

где m - количество запасов работоспособности.

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

где ХД - допустимая для поиска область.

Критерий оптимизации с целевой функцией (2.6) называют максиминным критерием.

Статистические критерии. Оптимизация при статистических критериях имеет целью получение максимальной вероятности Р выполнение работоспособности. Эту вероятность принимают в качестве целевой функции. Тогда имеем задачу

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

Возможны различные способы нормирования. В качестве примера рассмотрим способ логарифмического нормирования, достоинством которого является переход от абсолютных приращений параметров к относительным. В этом случае i-и управляемый параметр ui преобразуется в безразмерный хi следующим образом:

где оi - коэффициент, численно равный единице параметра ui .

Нормирование выходных параметров можно выполнить с помощью весовых коэффициентов, как в аддитивом критерии, или переходом от уj к запасам работоспособности zj по (2.5).

Математическая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из т пунктов отправления А 1 , А 2 , …, А т в п пунктов назначения В 1 , В 2 , …, В п . При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза.

Обозначим:

c ij – тарифы перевозки единицы груза из i -го пункта отправления в j -й пункт назначения,

a i – запасы груза в i -м пункте отправления,

b j – потребности в грузе в j– м пункте назначения,

x ij – количество единиц груза, перевозимого из i -го пункта отправления в j -й пункт назначения.

Тогда математическая постановка задачи состоит в определении минимального значения функции: (6.1)

при условиях
(6.2)

(6.3)

Всякое неотрицательное решение систем линейных уравнений (6.2) и (6.3), определяемое матрицей Х=(х ij ) , называется планом транспортной задачи.

План Х*=(х* ij ) , при котором функция (6.1) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные транспортной задачи записывают в виде таблицы.

Для определения опорного плана существует несколько методов: метод северо-западного угла, метод наименьшей стоимости, метод аппроксимации Фогеля и др.

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

В самую северо-западную клетку таблицы заносится максимально допустимая перевозка, при этом либо вывозится весь груз со станции А 1 и все остальные клетки первой строки вычеркиваются, либо потребности первого потребителя В 1 полностью удовлетворяются, тогда все клетки первого столбца вычеркиваются. После этого самой северо-западной клеткой становится клетка А 1 В 2 или В 2 А 1 . Алгоритм продолжается до заполнения таблицы. Недостатки – не учитывается стоимость перевозки, и получается план далекий от оптимального.

Метод наименьшей стоимости

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

Метод аппроксимации Фогеля

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

Широкораспространенным методом решения транспортных задач является метод потенциалов.

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

Теорема 1. Если опорный план Х=(х ij ) является оптимальным, существует система из (т+п) чисел, называемых потенциалами, U i , V j , такая, что:

U i + V j =С ij ,для х ij >0 (базисные переменные);

U i + V j =С ij ,для х ij =0 (свободные переменные).

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

для каждой занятой клетки сумма потенциалов равна стоимости перевозки единицы груза, стоящей в этой клетке:

U i + V j =С ij

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

U i + V j £ С ij

Теорема 2. Любая закрытая транспортная задача имеет решение, которое достигается за конечное число шагов метода потенциалов.

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

Циклом в таблице перевозок называется ломаная с вершинами в клетках и ребрами, расположенными вдоль строк или столбцов матрицы, удовлетворяющая двум требованиям:

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

в каждой вершине цикла сходятся ровно два ребра – одно по строке, другое по столбцу.

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

Приведем примеры некоторых циклов.

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

Алгоритм метода потенциалов

Поставим в соответствие каждой станции А i потенциал и i , а каждой станции В j потенциал v j . Для этого для каждой заполненной клетки х ij ≠0 составим уравнение и i + v j =с ij . Придадим и 1 =1 (можно любое другое значение) и найдем все остальные потенциалы.

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

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

4. Для новых потенциалов проверяем условие оптимальности. Если условия оптимальности выполняются, то получено оптимальное решение, если нет, то продолжаем поиск оптимального решения по методу потенциалов.

Пример 7.1. Четыре предприятия данного экономического района для производства продукции использует три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 160, 140, 170 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей
.

Составить такой план перевозок, при котором общая себестоимость перевозок является минимальной.

Решение:

задача закрытого типа.

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

S 1 =120·7+40·8+10·5+130·9+60·3+110·6=3120

Составим первый план методом минимальной стоимости. Будем заполнять клетки с минимальными тарифами.

S 2 =160·1+120·4+20·8+50·2+30·3+90·6=1530

Стоимость при таком плане перевозок почти в два раза меньше. Начнем решение задачи с этого плана. Проверим его на оптимальность. Введем потенциалы α i – соответственно отправления, β j – соответственно назначения. По занятым клеткам составляем систему уравнений α i + β j =c ij:

Для свободных клеток таблицы проверяем критерий оптимальности

Будем составлять разности

План не оптимальный т. к. имеется положительная оценка
Построим из неё цикл пересчета. Это ломаная линия звеньев которые расположены строго по вертикали или горизонтали, а вершины находятся в занятых клетках. В плохой клетке поставим знак (+). В остальных вершинах знаки чередуются. Из отрицательных вершин выбираем наименьшее число и сдвигаем его по циклу. Перешли к новому опорному плану.

S 3 =70·1+90·2+120·4+20·8+50·2+120·3=1350

Стоимость перевозок меньше, т.е. план улучшили. Проверяем теперь новый план на оптимальность. По занятым клеткам:

По свободным клеткам:

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

S 4 =50·1+110·2+120·4+20·5+30·2+140·3=1330

Проверяем новый план на оптимальность.

По занятым клеткам:

По свободным клеткам:

Критерий оптимальности выполнен, т. е. последний план оптимальный.

Ответ:

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

1) Объем работы транспорта (критерий - расстояние в т/км). Минимум пробега удобен для оценки планов перевозок, поскольку расстояние перевозки определяется легко и точно для любого направления. Поэтому критерию нельзя решать транспортные задачи с участием многих видов транспорта. С успехом применяется при решении транспортных задач для автомобильного транспорта. При разработке оптимальных схем перевозки однородных грузов автомобилями.

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

3) Эксплутационные расходы на транспортировку грузов (критерий - себестоимость эксплутационных расходов). Более верно отражает экономичность перевозок различными видами транспорта. Позволяет делать обоснованные выводы о целесообразности переключения с одного вида транспорта на другой.

4) Сроки доставки грузов (критерий - затраты времени).

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

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

где - эксплутационные издержки,

Расчетный коэффициент эффективности капиталовложения,

Капитальные вложения, приходящие на 1 т груза на протяжении участка,

Т - время следования,

Ц - цена одной тоны груза.

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

Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через – запасы груза в i-м пункте отправления, через – потребности в грузе в j–м пункте назначения, а через – количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции

при условиях

(2)

(3)

(4)

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

Таким образом, Т-задача представляет собой задачу ЛП с m*n числом переменных, и m + n числом ограничений - равенств.

Очевидно, общее наличие груза у поставщиков равно , а общая потребность в грузе в пунктах назначения равна единиц. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т. е.

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

Существует ряд практических задач, в которых условие баланса не выполняется. Такие модели называются открытыми . Возможные два случая:

В первом случае полное удовлетворение спроса невозможно .

Такую задачу можно привести к обычной транспортной задаче следующим образом. В случае превышения потребности над запасом, т. е. вводится фиктивный (m +1)–й пункт отправления с запасом груза и тарифы полагаются равными нулю:

Тогда требуется минимизировать

при условиях

Рассмотрим теперь второй случай .

Аналогично, при вводится фиктивный (n +1)–й пункт назначения с потребностью и соответствующие тарифы считаются равными нулю:

Тогда соответствующая Т-задача запишется так:

Минимизировать

при условиях:

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

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

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

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

· из запаса соответствующего пункта отправки;

· из потребности соответствующего пункта назначения.

Пример.

Четыре предприятия данного экономического района для производства продукции используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 160, 140, 170 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

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

(6)

При данном плане перевозок общая стоимость перевозок составит

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

Решение транспортной задачи

Основные шаги при решении транспортной задачи:

1. Найти начальный допустимый план.

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

3. Выбрать выводимую из базиса переменную, найти новое базисное решение. Вернуться к шагу 2.

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

Обычно исходные данные транспортной задачи записывают в виде таблицы.

Матрицу С называют матрицей транспортных затрат, матрицу X, удовлетворяющую условиям Т-задачи (2) и (3) называют планом перевозок, а переменные - перевозками. План , при котором целевая функция минимальна, называется оптимальным.

Число переменных в транспортной задаче с m пунктами отправления и n пунктами назначения равно m*n , а число уравнений в системах (2) и (3) равно m+n . Так как мы предполагаем, что выполняется условие (5), то число линейно независимых уравнений равно m+n–1 . Следовательно, опорный план транспортной задачи может иметь не более m+n–1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонент равно в точности m+n–1 , то план является невырожденным, а если меньше – то вырожденным.

Как и для всякой задачи линейного программирования, оптимальный план транспортной задачи является и опорным планом.

Построение допустимого (опорного) плана в транспортной задаче

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

Наиболее простой способ его нахождения основывается на так называемом методе северо-западного угла. Суть метода состоит в последовательном распределении всех запасов, имеющихся в первом, втором и т. д. пунктах производства, по первому, второму и т. д. пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в очередном пункте производства или к попытке полного удовлетворения потребностей в очередном пункте потребления. На каждом шаге q величины текущих нераспределенных запасов обозначаются а i (q ), а текущих неудовлетворенных потребностей - b j (q ) . Построение допустимого начального плана, согласно методу северо-западного угла, начинается с левого верхнего угла транспортной таблицы, при этом полагаем а i (0) = а i , b j (0) = b j . Для очередной клетки, расположенной в строке i и столбце j , рассматриваются значения нераспределенного запаса в i -ом пункте производства и неудовлетворенной потребности j -ом пункте потребления, из них выбирается минимальное и назначается в качестве объема перевозки между данными пунктами: х i, j =min{а i (q) , b j (q) } . После этого значения нераспределенного запаса и неудовлетворенной потребности в соответствующих пунктах уменьшаются на данную величину:

а i (q+1) = а i (q) - x i , j , b j (q+1) = b j (q) - x i , j

Очевидно, что на каждом шаге выполняется хотя бы одно из равенств: а i (q+1) = 0 или b j (q+1) = 0 . Если справедливо первое, то это означает, что весь запас i-го пункта производства исчерпан и необходимо перейти к распределению запаса в пункте производства i+1 , т. е. переместиться к следующей клетке вниз по столбцу. Если же b j (q+1) = 0, то значит, полностью удовлетворена потребность для j -го пункта, после чего следует переход на клетку, расположенную справа по строке. Вновь выбранная клетка становится текущей, и для нее повторяются все перечисленные операции.

Основываясь на условии баланса запасов и потребностей, нетрудно доказать, что за конечное число шагов мы получим допустимый план. В силу того же условия число шагов алгоритма не может быть больше, чем m+n-1 , поэтому всегда останутся свободными (нулевыми) mn-(m+n-1) клеток. Следовательно, полученный план является базисным. Не исключено, что на некотором промежуточном шаге текущий нераспределенный запас оказывается равным текущей неудовлетворенной потребности (а i (q) =b j (q)) . В этом случае переход к следующей клетке происходит в диагональном направлении (одновременно меняются текущие пункты производства и потребления), а это означает «потерю» одной ненулевой компоненты в плане или, другими словами, вырожденность построенного плана.

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

Пример нахождения опорного плана

F=14 x 11 + 28 x 12 + 21 x 13 + 28 x 14 + 10 x 21 + 17 x 22 + 15 x 23 + 24 x 24 + 14 x 31 + 30 x 32 +25 x 33 + 21 x 34

Первоначальный план получен по методу северо-западного угла. Задача сбалансированная (закрытая).

Таблица 1

Стоимость перевозок по данному плану составляет: 1681:

F=14 *27 + 28* 0 + 21*0 + 28*0 + 10 *6 + 17 *13 + 15*1 + 24 *0 + 14 *0 + 30 *0 +25*26 + 21 *17 =1681

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из т пунктов отправления в п пунктов назначения . При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через тарифы перевозки единицы груза из i -го пункта отправления в j -й пункт назначения, через – запасы груза в i -м пункте отправления, через – потребности в грузе в j – м пункте назначения, а через – количество единиц груза, перевозимого из i -го пункта отправления в j -й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции

при условиях

(64)

(65)

(66)

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

Определение 15.

Всякое неотрицательное решение систем линейных уравнений (64) и (65), определяемое матрицей , называется планом транспортной задачи.

Определение 16.

План , при котором функция (63) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные транспортной задачи записывают в виде таблицы 21.

Таблица 21

то модель такой транспортной задачи называется закрытой. Если же указанное условие не выполняется, то модель транспортной задачи называется открытой.

Теорема 13.

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

В случае превышения запаса над потребностью, т. е. вводится фиктивный (n +1)–й пункт назначения с потребностью и соответствующие тарифы считаются равными нулю: Полученная задача является транспортной задачей, для которой выполняется равенство (67).

Аналогично, при вводится фиктивный (m +1)–й пункт отправления с запасом груза и тарифы полагаются равными нулю: Этим задача сводится к обычной транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи. В дальнейшем будем рассматривать закрытую модель транспортной задачи. Если же модель конкретной задачи является открытой, то, исходя из сказанного выше, перепишем таблицу условий задачи так, чтобы выполнялось равенство (67).

Число переменных в транспортной задаче с т пунктами отправления и п пунктами назначения равно пт , а число уравнений в системах (64) и (65) равно п+т . Так как мы предполагаем, что выполняется условие (67), то число линейно независимых уравнений равно п+т – 1. Следовательно, опорный план транспортной задачи может иметь не более п + т – 1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонент равно в точности п +т – 1, то план является невырожденным, а если меньше – то вырожденным.

Как и для всякой , оптимальный план транспортной задачи является и опорным планом.

Для определения оптимального плана транспортной задачи можно использовать изложенные выше методы.

Пример 19.

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

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

(68)

При данном плане перевозок общая стоимость перевозок составит

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

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

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления (поставщики) A 1 , A 2 , . . ., A m в n пунктов потребления (потребители) B 1 , B 2 , . . . B n так, чтобы:

Вывезти все грузы от поставщиков;

Удовлетворить спрос каждого потребителя;

Обеспечить минимальные суммарные транспортные расходы на перевозку всех грузов.

Рассмотрим транспортную задачу, в качестве критерия оптимальности которой используется минимальная стоимость перевозки всего груза .

Обозначим:

a i - наличие груза в i -ом пункте отправления ;

b j - величина потребности в этом грузе в j -ом пункте назначения ;

с ij - стоимость перевозки единицы груза из i -ого пункта отправления в j -ый пункт потребления (тариф перевозки);

x ij - количество груза, перевозимого из i -ого пункта отправления в j -ый пункт назначения, назначения, x ij ≥ 0.

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

Запишем математическую модель транспортной задачи.

Требуется определить матрицу ) , которая удовлетворяет следующим условиям:

,
(5.1)

,
(5.2)

,
,
(5.3)

и доставляет минимальное значение целевой функции

L () =
(5.4)

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

Определение 1. Всякое неотрицательное решение систем линейных уравнений (5.1) и (5.2), определенное матрицей ) называется допустимым планом транспортной задачи .

Определение 2. План ) при котором функция (5.4) принимает максимальное значение, называется оптимальным планом транспортной задачи.

Теорема 1. Ранг матрицы, составленный из коэффициентов при неизвестных системы линейных уравнений (5.1) и (5.2) транспортной задачи, на единицу меньше числа уравнений, т.е. равен (m + n – 1).

Следовательно, число линейно независимых уравнений равно (m + n – 1), они образуют базис, а соответствующие им переменные будут являться базисными.

Определение 3 . Допустимый план транспортной задачи, имеющий не более (m + n – 1) отличных от нуля величин , называется базисным или опорным.

Определение 4. Если в опорном плане число отличных от нуля значений переменных в точности равно (m + n – 1), то план является невырожденным, а если меньше – вырожденным.

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

Определение 5. Модель транспортной задачи, удовлетворяющая условию (5.5), называется закрытой. Если указанное условие не выполняется, то модель является открытой.

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

В случае превышения запаса над потребностью, т.е. > , вводится фиктивный (n+ 1) –ый пункт назначения с потребностью b n +1 = − , а соответствующие тарифы считаются равными нулю: С i , n + 1 = 0

Если < , то вводится фиктивный (m + 1) –ый пункт отправления с потребностью a m +1 = − и тарифами С m + 1, j = 0

Рассмотрим один из методов построения первого опорного плана транспортной задачи – метод минимальной стоимости или наилучшего элемента матрицы удельных затрат.

Определение 6. Наилучшим элементом матрицы удельных затрат (тарифов) будем называть наименьший тариф, если задача поставлена на минимум целевой функции, наибольший тариф – если задача поставлена на максимум.

Алгоритм построения первого опорного плана.

1. Среди матрицы удельных затрат находим наилучший тариф.

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

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

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

Дальнейшее улучшение первого опорного плана транспортной задачи и получение оптимального плана производим методом потенциалов.

Теорема 3 . План ) транспортной задачи является оптимальным, если существует система (m + n) чисел u i и v j (называемых потенциалами), удовлетворяющая условиям:

(5.6)

(5.7)

Потенциалы u i и v j являются переменными двойственной задачи, составленной к исходной транспортной задаче, и обозначают оценку единицы груза в пунктах отправления и назначения соответственно.

Обозначим: ) оценка свободной (незанятой) клетки таблицы.

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

Алгоритм метода потенциалов

1. Построение первого опорного плана транспортной задачи методом минимальной стоимости.

2. Проверка вырожденности плана .

Потенциалы могут быть рассчитаны только для невырожденного плана. Если число занятых клеток в опорном плане (число базисных переменных) меньше, чем (m+n−1), то вносим нуль в одну из свободных клеток таблицы так, чтобы общее число занятых клеток стало равным (m+n−1). Нуль вводят в клетку с наилучшим тарифом, которая принадлежит строке или столбцу. Одновременно вычеркиваемых при составлении первого опорного плана. При этом фиктивно занятая нулем клетка таблицы не должна образовывать замкнутого прямоугольного контура с другими занятыми клетками таблицы.

3. Расчет значения функции цели (5.4) путем суммирования произведений тарифов (удельных затрат) на объемы перевозимого груза по всем занятым клеткам таблицы.

4. Проверка оптимальности плана.

Определяем потенциалы . Для каждой занятой клетки записываем уравнение , в результате получаем систему (m + n−1) уравнений с (m + n) переменными.

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

Для каждой свободной клетки определяем оценки .

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

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

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

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

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

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

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

Замечания

1. Если в минусовых клетках построенного цикла находятся два или несколько одинаковых минимальных значений , то при перераспределении объемов груза освобождается не одна, а две или несколько клеток. В этом случае план становится вырожденным. Для продолжения решения необходимо одну или несколько одновременно освобождающихся клеток таблицы занять нулем, причем предпочтение отдается клеткам с наилучшим тарифом. Нулей вводят столько, чтобы во вновь полученном опорном плане число занятых клеток (базисных переменных) было ровно (m + n−1).

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

3. Значение целевой функции на каждой итерации можно рассчитать следующим образом:

(задача поставлена на минимум),

(задача поставлена на максимум),

где - величина перемещаемого по контуру объема груза;

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

− значение функции цели на k-ой итерации;

− значение функции цели на предыдущей итерации.

Пример

На трех складах оптовой базы имеется однородный груз в количествах 40, 80 и 80 единиц. Этот груз необходимо перевезти в четыре магазина, каждый из которых должен получить соответственно 70, 20, 60 и 60 единиц. Стоимости доставки единицы груза (тарифы) из каждого склада ) во все магазины ) заданы матрицей .

Составить план перевозок однородного груза с минимальными транспортными затратами (числа условные).

Решение.

1. Проверим необходимое и достаточное условие разрешимости задачи:

40+80+80 = 200,

70+20+60+60 = 210.

Как видно, суммарная потребность груза превышает его запасы на складах оптовой базы. Следовательно, модель транспортной задачи является открытой и в исходном виде решения не имеет. Для получения закрытой модели введем дополнительный (фиктивный) склад А 4 с запасом груза, равным а 4 = 210 – 200 = 10 ед. тарифы перевозки единицы груза из склада А 4 во все магазины полагаем равными нулю.

Все исходные данные заносим в таблицу 7.

Запасы

В 1

В 2

В 3

В 4

A 1

A 2

A 3

A 4

Потребности

2. Построение первого опорного плана методом минимальной стоимости.

Среди тарифов минимальным или наилучшим является С 14 =1. В клетку А 1 В 4 направляем максимально возможный груз, равный min{60,40} = 40. Тогда x 14 = 40. Из склада А 1 весь груз вывезен, но потребность четвертого магазина неудовлетворенна на 20 ед. строка А 1 выходит из рассмотрения.

Среди оставшихся тарифов минимальный элемент - С 23 = 2. В клетку А 2 В 3 направляем груз min{60,80} = 60. При этом столбец В 3 выходит из рассмотрения, а из склада А 2 не вывезено 20 ед.

Из оставшихся элементов минимальный С 22 = 3. В клетку А 2 В 2 направляем груз в количестве min{20,20} = 20. При этом столбец одновременно вычеркиваются строка А 2 и столбец В 2 .

Выбираем минимальный элемент С 31 = 4. В клетку А 3 В 1 направляем груз, равный min{70,80} = 70. При этом столбец В 1 выходит из рассмотрения, а из склада А 3 не вывезено 10 ед. Оставшийся груз с третьего склада направляем в летку А 3 В 4 , x 34 = 10. Потребность четвертого магазина не удовлетворена на 10 ед. направим от фиктивного поставщика – склад А 4 10 ед. груза в клетку А 4 В 4 , x 44 = 10.

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

3. Проверка вырожденности плана

Число занятых клеток или базисных переменных в первом опорном плане равно шести. план транспортной задачи является вырожденным, так как число базисных переменных в невырожденном плане равно m + n – 1 = 4 + 4 – 1 = 7. Для продолжения решения задачи опорный план необходимо дополнить введением фиктивной перевозки, т.е. занять нулем одну из свободных клеток.

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

4. Расчет значения целевой функции

Значение целевой функции первого опорного плана определяем путем суммирования произведений тарифов на объемы перевозимого груза по всем занятым клеткам таблицы.

L(Х 1) = 4∙70 + 3∙20 + 2∙60 + 1∙40 + 3∙0 + 6∙10 + 0∙10 = 560 (тыс.руб.).

5. Проверка условия оптимальности

Рассчитаем потенциалы по занятым клеткам таблицы из условия: ( Так как число неизвестных потенциалов больше числа уравнений (m + n > m + n – 1), то один из потенциалов принимаем равным нулю. Пусть . Тогда для занятых клеток можем записать систему уравнений:

Полагая , получим , , , ,

Рассчитанные потенциалы заносим в таблицу 7. Подсчитаем оценки свободных клеток.

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

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

Для клетки А 3 В 2 построим прямоугольный замкнутый контур 0таблица 7) и проведем перераспределение груза контуру. Вершинам контура, начиная от вершины, находящейся в свободной клетке А 3 В 2 ,присваиваем поочередно знаки «+» и «−» .

Из объемов груза, стоящих в минусовых клетках, выбираем наименьшее, т.е. θ = min(20,10) = 10. Прибавляем значение θ = 10 к объемам груза, стоящих в плюсовых клетках, вычитаем из объемов груза, стоящих в минусовых клетках замкнутого контура. В результате получим новый опорный план, приведенный в таблице 8.

Запасы

В 1

В 2

В 3

В 4

A 1

A 2

A 3

3 10

A 4

Потребности

Второй опорный план транспортной задачи невырожденный, так как число занятых клеток равно 7.

L(X 2) = L(X 1) – θ∙ = 560 – 10∙3 = 530 (тыс.руб.).

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