Пособие и методические указания к выполнению курсовой работы
| Вид материала | Методические указания |
- Методические указания по выполнению курсовой работы студентам заочной формы обучения, 668.08kb.
- Методические указания по выполнению курсовой работы для студентов фф зфо, обучающихся, 175.52kb.
- Методические указания по выполнению курсовой работы Ижевск, 289.74kb.
- Методические указания по выполнению курсовой работы 11 Тема курсовой работы, 211.19kb.
- Методические указания по самостоятельной подготовке к практическим занятиям и выполнению, 426.22kb.
- Методические указания по выполнению курсовой работы для студентов 2 курса всех специальностей, 1477.96kb.
- Методические указания к выполнению курсовой работы для студентов специальности 100110., 198.16kb.
- Методические указания для выполнения курсовой работы по дисциплине «Теория принятия, 547.84kb.
- Методические указания к выполнению курсовой работы Владивосток, 732.88kb.
- Методические указания и рекомендации по выполнению курсовой работы для студентов специальности, 189.13kb.
В матрице (табл. 2) свободных клеток четыре Б-а, В-а, А-в и Б-в.
Начнем с клетки Б-а, и дадим в нее поставку равную единице, тогда в клетках А-а и Б-б поставки уменьшаются на единицу, в клетке А-б, увеличатся на единицу.
Б-а +3
А-а -2
А-б +1 А-а -2 +1 А-б
Б
-б -4-----
-2
Б-а +3 -4 Б-б
Таким образом, давая поставку равную единице в клетку Б-а происходит уменьшение функции на 2, т. е. F(Xij)=748. Показатель можно получить и путем алгебраической суммы характеристик в вершинах цепи. Если в алгебраической сумме получились отрицательные значения, то план не оптимален. Исследуем алгебраически все свободные клетки, перемещая в них поставку равную единице по закону многоугольника цепей. Построение цепей приведено в табл. 1, а именно:
Б-а +3-2+1-4= -2
В-а +4-2+1-6= -3
А-в +5-6+6-1= +4
Б-в +3-6+6-4= -1
Как видно, в свободных клетках В-а и Б-а имеются отрицательные значения, следовательно, план не оптимален. Назначение поставок корреспонденций назначают в клетку в которой имеются наибольшая отрицательная величина, что приблизит функцию к оптимуму на максимально возможную величину на данной итерации. Но брать большую величину чем величина наименьшей поставки в отрицательных вершинах цепи, нельзя, так как там где была наименьшая поставка после перераспределения, она станет отрицательной (-хij), что недопустимо, т. е. величина новой поставки должна быть в точности равна величине наименьшей поставки в отрицательных вершинах цепи.
Наибольшая отрицательная величина в свободной клетке В-а. В нее и назначается поставка величиной 15, т.е. с наименьшим значением из отрицательных значений вершин поставок цепи, а за тем производится перемещение поставок по клеткам вершин цепи соблюдая ограничения. (табл. 3).
Таблица 3.
-
Пункты производства
Пункты потребления
Объем производства
а
б
в
А
2
5
2
2
5
1
5
50
Б
3
60
4
3
60
В
1
5
4
6
55
6
70
Объем потребления
40
85
55
Целевая функция уменьшается и составит на величину
F(Xij)=2*25+1*25+4*60+4*15+6*55=705
(Алгебраическая сумма –3*15= -45)
План поставок допустимый, он лучше прежнего.
Путем построения цепей в матрице табл. 3, выясним, оптимален ли план.
Цепи плана приведены в табл. 3.
Б-а +3-2+1-4= -2
А-в +5-2+4-6= +1
В-б +6-4+2-1= +3
Б-в +3-6+4-2+1-4= -4
Как видно из построения цепей план не оптимален. Назначим поставку (25) в квадрат Б-в. улучшенный план представлен в табл. 4.
Имеются отрицательные величины и в клетке Б-в, она максимальная по абсолютной величине. В эту клетку, соблюдая закон цепей, направляем поставку наименьшей величины из отрицательных значений цепи. В данном случае 25 в клетку Б-в. смотри таблицу 4.
Таблица 4.
-
Пункты производства
Пункты потребления
Объем производства
а
б
в
А
2
5
0
1
5
50
Б
3
35
4
25
3
60
В
40
4
6
30
6
70
Объем потребления
40
85
55
План не оптимален. В показателях - характеристик клеток, имеется отрицательная величина, клетка В-б.
А-а +2-1+4-3+6-4= +4
А-в +5-3+4-3=+5
Б-а +3-3+6-4=+2
В-б +6-4+3-6= -1
Но целевая функция уменьшена на 100.
F(Xij)=1*50+4*35+3*25+4*40+30*6=605
Поставку даем в клетку В-б.
Строим цепи плана таблица 4.
Поставка составляет величину 30. Новый план представлен в таблице 5.
Таблица 5.
-
Пункты производства
Пункты потребления
Объем производства
а
б
в
А
2
5
0
1
5
50
Б
3
5
4
55
3
60
В
40
4
30
6
6
70
Объем потребления
40
85
55
Целевая функция уменьшилась на (30).
F(Xij)=1*50+4*5+3*55+4*40+6*30=575
Строим цепи
А-а +2-1+6-4=+3
А-в +5-3+4-1=+5
Б-а +3-4+6-4=+1
В-в +6-3+4-6=+1
Построение цепей для всех клеток не дает отрицательных характеристик. Это свидетельствует об оптимальности плана.
Таким образом, при распределительном методе, решение задачи на оптимум состоит из следующих этапов:
I этап. Составляется замкнутый контур (цепь), начиная с любой свободной клетки. При этом контур цепи можно поворачивать только под прямым углом и только в занятых квадратах, т.е. в клетках не с нулевой величиной поставки. Такой контур для каждой свободной клетки является единственным. Контуры цепи составляются для каждой свободной клетки.
II этап. Каждой клетке, которой соответствует вершина контура, присваивается знак (минус, плюс). Знаки чередуются.
III этап. Определяется алгебраическая сумма значений стоимости перевозок тех корреспонденций, которые расположены в вершинах контура. Если эта сумма хотя бы для одной из свободных клеток отрицательна, план не оптимален, и он может быть улучшен. Улучшение опорного плана начинают с перераспределения поставок.
ЭКОНОМИЧЕСКАЯ ИНТЕРПРИТАЦИЯ МЕТОДА
ПОТЕНЦИАЛОВ.
Потенциалы строк характеризуют допустимые затраты на единицу продукции в пункте отправления (поставщика), а потенциалы столбцов – совокупность затрат в пункте потребления (получателя). Экономическое содержание потенциалов строк и столбцов заключается в том, что рассматривая потенциалы как условные цены продукции в пунктах производства (строки) и в пунктах потребления (столбцы) в оптимальном плане любая намеченная перевозка должна быть безубыточной и не давать прибыли.
Экономия, получаемая на каждой итерации равна произведению величины устраняемого нарушения на величину Х.
Решение транспортной задачи методом потенциалов (моди).
Идея метода потенциалов заключается в том, что для проверки допустимого плана на оптимальность определяются числа (потенциалы) с помощью которых вычисляются характеристики пустых клеток.
Обозначим потенциалы строк через Ui, потенциалы столбцов через Vi, и показатели стоимости в занятых квадратах через Cij.
Допустимый план считается оптимальным, если каждому поставщику и каждому потребителю соответствуют условия Хij>0 и CijVj-Ui для всех ij
из равенства следует, что потенциал строки Ui=Vj-Cij потенциал столбца Vj= Cij+Ui или Vj=Ui+Cij (условия 1).
Начальный потенциал строки или столбца выбирается произвольным, а чтобы не было отрицательных значений потенциалов целесообразнее принимать начальный потенциал несколько большим по сравнению с Cij.
В примере табл. 1 опорный план составлен диагональным методом.
Таблица 1.
-
Пункты производства
Пункты потребления
Объем пр-ва
Потенц. строк
Ui
а
б
в
А
_
2
+
1
5
50
8
40
10
Б
3
4
3
60
5
60
В
+
4
_
6
6
70
5
15
55
Объем потребления
40
85
55
Потенц. столб. Vj
10
9
9