Транспортная задача
Курсовой проект - Менеджмент
Другие курсовые по предмету Менеджмент
°дачу, исходные данные которой приведены в табл. 6.13.
Таблица 6.13
bj ai100100300300100 1 2 3 1200 2 3 4 6300 3 4 7 12
Решение. 1. Проверяем выполнение необходимого и достаточного условия разрешимости задачи. Находим суммарные запасы поставщиков и запросы потребителей
Задача с неправильным балансом. Вводим четвертого, фиктивного поставщика с запасами и нулевыми стоимостями перевозки единиц груза (табл. 6.14).
2.Составляем начальное опорное решение методом минимальной стоимости (табл. 6.14).
Таблица 6.14
bj ai100100300300100 1 100 2 3 1200 2 0 3 100 4 100 6300 3 4 7 200 12 100200 0 0 0 0 200
Записываем матрицу стоимостей C. Находим в этой матрице наименьшие на каждом шаге стоимости и направляем в клетку, которая соответствует этим стоимостям, максимально допустимые объемы перевозок грузов.
При этом исключаем на каждом шаге одного поставщика или потребителя. Кружочками в матрице C указаны минимальные элементы, а цифрами рядом со строками и столбцами - порядок исключения из рассмотрения поставщиков и потребителей. Напомним, что запасы фиктивного поставщика вывозятся в последнюю очередь.
Полученное решение X1 имеет m+n-1=4+4-1=7 базисных переменных. Опорное решение является вырожденным, так как одна из его координат равна нулю. Вычислим значение целевой функции на этом опорном решении Z(X1)=1001+02+1003+1004+2007+10012+2000=3400.
. Для проверки оптимальности опорного решения необходимо найти потенциалы. По признаку оптимальности в каждой занятой опорным решением клетке таблицы транспортной задачи сумма потенциалов равняется стоимости (ui+vj=cij при xij>0). Записываем систему уравнений для нахождения потенциалов
u1+v1=1,
u2+v1=2,
u2+v2=3,2+v3=4,3+v3=7,3+v4=12,4+v4=0.
Система состоит из семи уравнений и имеет восемь переменных. Система неопределенная. Одному из потенциалов задаем значение произвольно: пусть u2=0. Остальные потенциалы находятся однозначно
u2=0
v1=2-u2=2-0=2;
v2=3-u2=3-0=3;
v3=4-u2=4-0=4;
u1=1-v1=1-2=-1;
u3=7-v3=7-4=3;
v4=12-u3=12-3=9;
u4=0-v4=0-9=-9.
Значения потенциалов записываем рядом с запасами или запросами соответствующих поставщиков и потребителей в таблицу (табл. 6.15).
Система уравнений для нахождения потенциалов достаточно проста, обычно ее решают устно, глядя на таблицу задачи, ее занятые клетки и известные потенциалы. Любой неизвестный потенциал, соответствующий занятой клетке, равен находящейся в этой клетке стоимости, минус известный потенциал, соответствующий этой клетке (6.14), (6.15).
Таблица 6.15
X1v1=2v2=3v3=4v4=9 bj ai100100300300 u1=-1100- 1 100 2 0 3 0+ 1 7 u2=0200 2 + 0 3 100- 4 100 6 3 u3=3300 3 2 4 2 + 7 200 12 100- u4=-9200 0 0 0 0 200
4. Проверяем опорное решение X1 на оптимальность. С этой целью вычисляем оценки для всех незаполненных клеток таблицы (для всех занятых ).
Положительные оценки записывают в левые нижние углы соответствующих клеток таблицы, вместо отрицательных просто ставим знак -.
Начальное опорное решение не является оптимальным, так как имеются положительные оценки.
. Переходим к новому опорному решению. Находим клетку таблицы, которой соответствует наибольшая положительная оценка. Имеем для клетки (1,4). Для этой клетки строим цикл. Ставим в нее знак +, присоединяем ее к занятым клеткам и применяем метод вычеркивания. После проведения вычеркиваний в таблице остаются только образующие цикл клетки. Цикл изображен в табл. 6.15. на основании теоремы 6.6 такой цикл единственный . В угловых точках цикла расставляются поочередно знаки + и , начиная с + в клетке (1,4). В клетки, отмеченные знаком + добавляется груз ?, а из клеток, отмеченных знаком минус, вычитается такой же по величине груз. Определяем величину груза ?, перераспределяемого по циклу. Она равняется значению наименьшей из перевозок в клетках цикла, отмеченных знаком -
Осуществляем сдвиг по циклу на величину ?=100. Получаем второе опорное решение X2 (табл. 6.16).
Таблица 6.16
X2v1=2v2=3v3=4v4=9 bj ai100100300300 u1=-1100 1 0 2 0 3 0 1 100 u2=0200 2 100- 3 100+ 4 0 6 u3=3300 3 2 4 2 + 7 300- 12 u4=-2200 0 0 1 0 2 0 200
В данном случае минимум перевозок в клетках, отмеченных знаком - достигался сразу в трех клетках, поэтому для того, чтобы число занятых клеток опорного решения было по-прежнему равно m+n-1=7, в клетки с номерами (1,1) и (2,3) поставлены нулевые базисные перевозки. Следует освобождать клетку с большей стоимостью перевозки, т.е. клетку (3.4).
Вычисляем значение целевой функции на втором опорном решении
Z(X2)=01+1001+1002+1003+04+3007+2000=2700.
. Проверяем второе опорное решение X2 на оптимальность. Находим потенциалы и оценки. Они приведены в табл. 6.16. Решение не является оптимальным, так как имеются положительные оценки ?31=2, ?32=2, ?42=1 и ?43=2. Наибольшая из них равняется 2 одновременно для трех клеток (3,1), (3,2), (4,3). В одну из них, пусть в клетку (3,2), ставим знак +. Для этой клетки строим цикл (табл. 6.16), и находим величину груза для перераспределения по циклу:
Осуществляем сдвиг по циклу на величину ?=100. Получаем третье опорное решение X3 (табл. 6.17).
Таблица 6.17
X3v1=1v2=0v3=3v4=1 bj ai100100300300 u1=0100 1 0 2 3 0 1 100 u2=1200 - 2 100 3 + 4 100 6 u3=4300 3 2 + 4 100 7 200- 12 u4=-1200 0 0 0 0 2 0 200
Вычисляем значение целевой функции на третьем опорном решении
Z(X3)=01+1001+1002+1004+1004+2007+2000=2500.
. Проверяем третье опорное решение X3 на оптимальность. Находим потенциалы и оценки. Они приведены в табл. 6.17. Решение не является оптимальным, так как имеются положительные оценки ?31=2 и ?43=2. В одну из клеток с положительной оценкой, пусть в клетку (3,1), ставим знак +. Для эт