Решение. Составим экономико-математическую модель задачи

Составим экономико-математическую модель задачи.

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

Ограничения:

1. Кирпич, расположенный на складах 3-х заводов должен быть вывезен в полном объеме.

х₁₁+ х₁₂ + х₁₃ + х₁₄ = 60

х₂₁+ х₂₂ + х₂₃ + х₂₄ = 80

х₃₁ + х₃₂+ х₃₃ + х₃₄ = 106

2. Потребности каждого объекта строительства должны быть удовлетворены в полном объеме.

3. Условие неотрицательности переменных.

Первый базисный план построим методом «северо-западного угла».Суть этого метода состоит в распределении поставок, начиная с «северо-западной» клетки, т.е. с первой клетки, находящейся в левом верхнем углу. Это клетка (1:1). В это клетку делают максимально возможную поставку, учитывая потребности и возможности пунктов. И так далее делают поставки, последовательно исчерпывая мощности поставщиков и удовлетворяя потребности потребителей. Заполненные клетки при данном методе имеют вид лесенки.

1. Подсчитывают значение целевой функции: Z ₁

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

Потенциалы – это числа, приписываемые к каждому столбцу и каждой строке. За U_i обозначают потенциалы строк, а за V_j обозначают потенциалы столбцов. Потенциалы определяются по занятым клеткам. Для удобства расчетов принимают U₁ =0.

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

V_j = C_{i j} + U_i, (1)

где V_j - потенциал столбца

C_ij – оценка клетки (стоимость)

U_i, - потенциал строки.

Контур перераспределения составляется по следующим правилам:

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

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

 все углы контура (многоугольника) прямые – 90;

 в каждой вершине контура встречаются только два звена, одно из них располагается по строке, другое – по столбцу;

 число вершин контура четное;

 в каждой строке (столбце) имеются две вершины: одна загружаемая, другая – разгружаемая.

Теорема. Для каждой свободной (пустой) клетки можно построить один единственный замкнутый контур.

Для перераспределения перевозок вершины контура чередуя, помечают знаками «+», «-», начиная с пустой клетки, где ставится знак «+».

Далее в вершинах со знаком «-» выбирают минимальный объем поставки. Данный объем должен перераспределяться по контуру с учетом знаков, т.е в положительных вершинах прибавляться, в отрицательных – вычитаться.

Далее следует повторить процедуру проверки плана на оптимальность, т.е. вычислить потенциалы и характеристики свободных клеток.