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

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

(1.14)

при ограничениях:

(1.13)

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

Критерий оптимальности решения транспортной задачи:

Допустимый план является оптимальным в том и только том случае, если каждому пункту производства и каждому пункту потребления могут быть поставлены в соответствие такие числа u_iи v_j(называемые потенциалами), которые удовлетворяют следующим условиям:

– для свободных клеток таблицы;

– для загруженных клеток таблицы (x_ij> 0).

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

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

Алгоритм состоит из предварительного шага и повторяющегося общего шага.

На предварительном ш а ге выполняется следующее:

1) составляется первоначальныйплан одним из методов (метод северо-западного угла, метод наименьшей стоимости);

2) для полученного плана определяется системапотенциалов, т. е. находятся m+n чисел ; из системы m+n-1 линейных уравнений: , где номера i, j соответствуют загруженным клеткам таблицы. Поскольку число неизвестных превышает на единицу число уравнений, то одну из неизвестных полагаем равной произвольному числу, например . Остальные неизвестные находятся из указанной системы уравнений;

3) проверяется оптимальность плана по критерию оптимальности задачи. Такая проверка осуществляется, например, следующим образом. Для всех свободных клеток таблицы находим числа: . Если все числа , то критерий оптимальности выполняется. В противном случае – нет.

Общий шаг (применяется, если план, построенный на предыдущем шаге, не оптимален) состоит из трех этапов:

1) улучшение плана. Поскольку текущий план не является оптимальным, то существует свободная клетка таблицы, для которой справедливо неравенство . Свободную клетку таблицы, у которой положительное число является наибольшим, помечаем символом * (звездочка). Далее строим многоугольник, вершины которого лежат в загруженных клетках таблицы и в свободной клетке, помеченной звездочкой. Помечаем клетки-вершины полученного многоугольника попеременно знаками "+" и "–". Свободная клетка помечается знаком "+". Переход к новому плану перевозок груза осуществляется следующим образом. Наименьшая поставка, стоящая в клетках-вершинах многоугольника и помеченная знаком "–", прибавляется к перевозкам всех клеток-вершин, помеченных знаком "+", и вычитается из поставок всех клеток-вершин, помеченных знаком "–". В результате ранее свободная клетка становится заполненной (загруженной), а клетка, помеченная знаком "–", в которой стояла наименьшая поставка, превращается в свободную клетку. Общее число занятых клеток остается равным n+m–1. Если в пределах данного многоугольника минимальную поставку имели две клетки или более, то освобождаться может лишь одна из них, а остальные считаются загруженными с нулевыми поставками;

2) для полученного плана определяется система потенциалов;

3) проверяется оптимальность плана по критерию оптимальности задачи.

Дата добавления: 2015-11-14