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

Получение исходного плана основано на заполнении следующей таблицы:

В каждой ячейке в левом верхнем углу помещаются стоимости перевозок, в правом нижнем углу объемы поставок от i-го поставщика к j-му потребителю. В верхней строке указываются мощности поставщиков, в левом столбце – спрос потребителей.

Рассмотрим методы получения первого опорного плана.

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

Рассматривается незаполненная левая верхняя ячейка.

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

ячейки этого столбца зачеркиваются и в последующих распределениях не участвуют.

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

Вновь рассматривается незаполненная северо-западная ячейка, и итерации повторяются.

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

54

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

б) Метод минимальной стоимости.

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

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

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

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

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

Если план получается вырожденным, т.е. m+n-1 не совпадает с числом заполненных ячеек, то вводится фиктивно заполненная нулем ячейка. Для этого из всех незаполненных ячеек находится ячейка с минимальной стоимостью. Если на

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

Для оценки плана:

1)Вычисляются потенциалы поставщиков Ui и

ячеек Sij > 0 , то оптимальный план является единственным. Если какая-либо оценка Sij = 0 , то существует бесчисленное

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

55

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

(решение оптимальное, но альтернативное). Если какое-либо значение Sij < 0 , то план неоптимальный, и необходимо

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

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

В свободную вершину цикла вписывается “+”, а все последующие вершины по часовой стрелке будут иметь “-”, “+”, “-”,…

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

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

вырожденный, то необходимо выбрать свободную ячейку с

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

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

П р и м е р . Предприятие имеет 3 склада готовой продукции: А1, А2, А3, на которых соответственно имеются 70, 90 и 60 единиц товара. Рынкам сбыта, находящимся в городах B1, B2, B3, B4, необходимо распределить следующее количество единиц продукции – 90, 40, 50 и 20. Стоимость перевозки

единицы продукции со склада на рынок сбыта задается таблицей (в у.е.):

56

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

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

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

задачи.

Обозначим через xij - объём перевозки от i –ого склада

j – ому рынку сбыта.

Тогда суммарные затраты на перевозку Z составят:

Z = 2× x11 +1× x12 + 5× x13 + 3× x14 + 5× x21 + 2× x22 + 3× x23 + 5× x24 + 3× x31 + 4× x32 + 4× x33 + 6× x34 ® min

Заданные мощности складов и потребности рынков сбыта накладывают ограничения на значения объемов перевозок

57

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

− Объемы перевозимых грузов не могут быть отрицательными:

xij ³ 0 (i = 1,2,3 j = 1,2,3,4)

Р е ш е н и е .

1. Определим характер транспортной задачи.

(суммарные мощности не равны суммарным потребностям), то

данная задача является открытой и необходимо её привести к закрытой. Для этого введем фиктивного потребителя (рынок

перевозок для этого потребителя ci4 = 0 (i = 1,4) .

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

2. Заполним распределительную таблицу исходными данными.

В результате введения фиктивного потребителя распределительная таблица исходных данных примет вид:

58

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