13. Тз. Построение исходного базисного плана.

Метод минимального элемента:

1. Выбираем клетку таблицы с минимальным значением С_ij, в кот. записывается min между и

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

3. Повторяем шаг 1 до тех пор, пока все запасы продукции не будут исчерпаны.

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

Груз будем распределять с верхней левой клетки 11. В клетку с номером 11 записываем минимальное из того, что может отдать поставщик и взять потребитель. Если а_i>b_j, то заносится b₁ и т.д.

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

1.Коэффициенты во всех управлениях равны 1

2.Каждая переменная встречается только в 2х уравнениях

3.Система ур-ний симметрична относительно всех переменных

4.Матрица, составл-ная из коэф-ов при переем-х состоит из единиц 0.

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

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

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

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

Теорема. Если план Х* ТЗ является оптимальным, то соответствующая система из m+n чисел удовлетворяют условию U_i^*+V_j^*=C_ij, U_i^*+ V_j^*≥0

14 Тз. Метод потенциалов

Каждому поставщику поставили в соответствие Ui,а каждому потребителю -,а каждому потребителю Vj.К каждой занятой клетке будет соответствовать переменная Ui+Vj=Cij.

Неизвестные ui, vj называются потенциалами.

Т.к. кол-во занятых клеток m+n-1, то в сис-ме ур-ний будет (m+n) неизвестных и m+n-1 ур-ний, т.е. она является неопределённой.

Для её решния надо к-л потенциалу присвоить к-л значение (U1=0).

Алгоритм:

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

2. Вычислить потенциалы, решив сис-у уравнений.

3. Для свободных клеток найти оценки Sij=Cij –(Ui+Vj).Если все оценки >=0, то полученный план перевозок явл. оптимальным. Если сущ-ет хотя бы одна оценка = 0, то мы имеем множ-во оптим. планов и решение задачи окончательно. Если все оц-ки >0, то этот план единственный.

4. Если план не явл-тся оптим-ым, т.е. сущ-ет Sij<0, то план будут улучшать за счёт загрузки клетки с отриц-ым знач-ем оценки. Если таких клеток неск-ко, то наиб. перспективной для загрузки явл-тся клетка с наименьшей оценкой.

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

Алгоритм повторяется, переходим к шагу 2.