Файл: 1ЭМММ-Линейное программирование.pdf

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

Для проверки опорного плана на оптимальность,

необходимо вычислить оценки всех свободных ячеек по формуле Sij = cij - (Ui + V j ) . Если полученные значения Sij ³ 0 ,

то найденный план оптимальный. При этом если какая-либо оценка Sij = 0 , то оптимальный план неединственный, т.е.

существует бесконечное множество решений с одним и тем же значением целевой функции. В случае, если все оценки Sij > 0 ,

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

Вычислим оценки свободных ячеек:

S13 = c13 − (U1 +V3) = 5 − (0 + 0) = 5

S14 = c14 − (U1 + V4 ) = 3 − (0 + 2) =1

S22 = c22 − (U2 +V2 ) = 2 − (3 +1) = −2

63

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

S25 = c25 − (U 2 + V5 ) = 0 − (3 + 0) = −3

S32 = c32 − (U3 + V2 ) = 4 − (1 + 1) = 2

S33 = c33 − (U3 + V3 ) = 4 − (1 + 0) = 3

S34 = c34 − (U3 + V4 ) = 6 − (1 + 2) = 3

S35 = c35 − (U3 + V5 ) = 0 − (1 + 0) = −1

Среди полученных оценок есть отрицательные, значит, найденный опорный план неоптимальный, и следует

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

иперейти к новому опорному плану.

Вкачестве такой ячейки выберем ячейку (2,5), т.к. она имеет наименьшую оценку S25 = −3 .

7. Построим новый опорный план.

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

Построим следующий замкнутый цикл: (2,5) – (2,1) – (1,1) – (1,5) – (2,5). В свободную ячейку с минимальной отрицательной оценкой вписывается знак «+», в вершину, следующую за свободной клеткой в цикле, ставится знак «-» и т.д. по порядку.

64

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

Поставка, передаваемая по циклу, определяется как минимум среди поставок в ячейках цикла со знаком «-». Для нашей задачи знак «-» имеют ячейки (2,2), (1,5). Минимальный объем груза для этих ячеек равен min{20,20}= 20 .

Ввершинах цикла со знаком «+» объем груза увеличивается на 20 единиц, а в вершинах со знаком «-» - уменьшается на тот же объем груза. Например, поставка ячейки (2,5) станет равной 20 единицам груза, ячейки (2,1) и (1,5) станут свободными и т.д. Поскольку ячейки со знаком «-» имеют одинаковый объем поставок, равный 20, то для сохранения невырожденности плана ячейку (1,5) (данная ячейка является клеткой с минимальной стоимостью, и на её основе нельзя построить замкнутого цикла) будем считать условно заполненной с объемом поставки, равным 0.

Врезультате баланс распределения поставок не нарушается.

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

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

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

Вычислим оценки свободных ячеек:

S13 = c13 − (U1 +V3) = 5 − (0 + 3) = 2 S14 = c14 − (U1 +V4 ) = 3− (0 + 5) = −2 S21 = c21 − (U 2 +V1) = 5 − (0 + 2) = 3 S22 = c22 − (U 2 +V2 ) = 2 − (0 +1) =1 S32 = c32 − (U3 +V2 ) = 4 − (1+1) = 2 S33 = c33 − (U3 +V3) = 4 − (1+ 3) = 0 S34 = c34 − (U3 +V4 ) = 6 − (1+ 5) = 0 S35 = c35 − (U3 +V5) = 0 − (1+ 0) = −1

Среди полученных оценок есть отрицательные, значит, найденный опорный план неоптимальный, и следует

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

S14 = −2 .

Построим следующий замкнутый цикл: (1,4) – (1,5) – (2,5) – (2,4) – (1,4). Определяем поставку, передаваемую по циклу, как min{20,0}= 0 . В вершины цикла со знаком «+» объем

груза условно увеличивается на 0 единиц груза, а в вершинах со знаком «-» - уменьшается на тот же объем.

Ячейка (1,5) становится свободной, ячейка (1,4) – становится условной заполненной. Поставки в остальных ячейках цикла остаются неизменными.

66

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

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

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

Положив u1 ≡ 0 , получим

u2 = 2,u3 = 1, v1 = 2,v2 = 1,v3 = 1,v4 = 3, v5 = −2.

Вычислим оценки свободных ячеек:

S13 = c13 − (U1 +V3) = 5 − (0 +1) = 4 S15 = c15 − (U1 + V5) = 0 − (0 − 2) = 2 S21 = c21 − (U2 +V1) = 5 − (2 + 2) = 1 S22 = c22 − (U2 +V2 ) = 2 − (2 +1) = −1 S32 = c32 − (U3 +V2) = 4 − (1+1) = 2 S33 = c33 − (U3 +V3) = 4 − (1+1) = 2 S34 = c34 − (U3 +V4) = 6 − (1+ 3) = 2 S35 = c35 − (U3 +V5) = 0 − (1− 2) = 2

Полученный опорный план снова неоптимальный, т.к. среди оценок свободных ячеек есть отрицательные ( S22 = −1 ).

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

Построим замкнутый цикл: (2,2) – (1,2) – (1,4) – (2,4) –

(2,2).

67

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com