ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 09.02.2024
Просмотров: 20
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
1. Определим потенциалы каждого поставщика Аi и каждого потребителя Вj. Для этого поставим в соответствие:
поставщику А1, т.е. первой строке, потенциал 1,
поставщику А2, т.е. второй строке, потенциал 2,
поставщику А3, т.е. третьей строке, потенциал 3,
потребителю B1, т.е. первому столбцу, потенциал 1,
потребителю B2, т.е. второму столбцу, потенциал 2,
потребителю B3, т.е. третьему столбцу, потенциал 3,
потребителю B4, т.е. четвертому столбцу, потенциал 4,
потребителюB5, т.е. пятому столбцу, потенциал 5.
2. Для нахождения потенциалов составляем для каждой ненулевой клетки соотношения i + j = сij :
| 1 + 1 = с11 = 4; | 1 + 1 = 4; | |
| 1 + 3 = с13 = 6; | 1 + 3 = 6; | |
| 1 + 4 = с14 = 5; | 1 + 4 = 5; | |
| 2 + 3 = с23 = 9; | 2 + 3 = 9; | |
| 2 + 5 = с25 = 10; | 2 + 5 = 10; | |
| 3 + 2 = с32 = 5; | 3 + 2 = 5; | |
| 3 + 5 = с35 = 20; | 3 + 5 = 20; | |
Для решения системы полагаем 1=0. Тогда из первого уравнения получаем 1 = 4; из второго 0 +3 = 6 3 = 6; из третьего 0 +4, = 5, 4
= 5.
Подставляем найденное значение 3 = 6 в четвертое уравнение системы 2 + 3 = 9, тогда 2 + 6 = 9, т.е. 2 = 3.
Далее подставляем значение 2 = 3 в пятое уравнение системы
2 + 5 = 10, отсюда 3+5 = 10, или 5 =7.
Следующее уравнение системы пропускаем, т.к. в нем обе переменные неизвестные.
А в последнее уравнение 3 + 5 = 20 подставляем найденное значение 5 =7, получим:, 3 + 7 = 20, т.e. 3 = 13.
Возвращаемся к шестому уравнению: 3 + 2 = 5, подставляем 3 = 13, получаем 13 + 2 = 5 или 2 = - 8.
Выпишем найденные значения потенциалов:
| 1 = 0 | 1 = 4 | 4 = 5 |
| 2 = 3 | 2 = -8 | 5 = 7 |
| 3 = 13 | 3 = 6 | |
Занесем их в таблицу №10. В результате получим таблицу № 11.
Таблица № 11
| Поставщики | Потребители | Запасы | |||||||||||||||
| В1 1=4 | В2 2=-8 | В3 3=6 | В4 4=5 | В5 5=7 | |||||||||||||
| А1 1=0 | | 4 | | 11 | | 6 | | 5 | | 15 | 200 | ||||||
| 70 | | 0 | | 20 | | 110 | | 0 | | ||||||||
| А2 2=3 | | 8 | | 7 | | 9 | | 13 | | 10 | 200 | ||||||
| 0 | | 0 | | 130 | | 0 | | 70 | | ||||||||
| А3 3=13 | | 10 | | 5 | | 12 | | 7 | | 20 | 100 | ||||||
| 0 | | 80 | | 0 | | 0 | | 20 | | ||||||||
| Потребность | 70 | 80 | 150 | 110 | 90 | | |||||||||||
3. Определим косвенные тарифы сij* для каждой незаполненной клетки таблицы №11.
Косвенным тарифом сij для клетки с номером (i,j) таблицы перевозок называется алгебраическая сумма потенциалов i-той строки и j-ого столбца, на пересечении которых находится эта клетка, то есть сij* = i + j.
Отсюда следует, что для всех заполненных (базисных) клеток косвенный тариф равен истинному, т.е. сij* = сij .
Для свободных клеток в общем случае сij* сij.
Вычислим для всех незанятых поставками клеток косвенные тарифы:
для клетки с номером (1, 2): с12*= 1 + 2 = 0 - 8 = -8,
для клетки с номером (1, 5): с15* = 1 + 5 =0 + 7 = 7,
для клетки с номером (2, 1): с21* = 2 + 1 = 3 + 4 = 7,
для клетки с номером (2, 2): с22* = 2 + 2 = 3 - 8 = -5
для клетки с номером (2, 4): с24* = 2 + 4 = 3 + 5 = 8,
для клетки с номером (3, 1): с31* = 3 + 1 = 13 + 4 = 17,
для клетки с номером (3, 3): с33* = 3 + 3 = 13 + 6 = 19,
для клетки с номером (3, 4): с34* = 3 + 4 = 13 + 5 = 18.
4. Проверим полученный план перевозок на оптимальность. Сформируем сначала общие правила проведения такой проверки:
1) для всех незаполненных клеток вычисляем величину
, представляющую собой разницу между косвенным и истинным тарифом.2) если для всех свободных клеток таблицы перевозок значение критерия оптимальности ij ≤ 0, то этот план перевозок является оптимальным. Причемесли для всех свободных клеток значение критерия оптимальности ij<0, то этот оптимальный план перевозок является к тому же и единственным. Если же для некоторых свободных клеток значение критерия оптимальности ij = 0, то этот оптимальный план перевозок не является единственным;
3) если имеются свободные клетки, для которых критерий оптимальности
ij 0, то полученный план перевозок не является оптимальным.
В соответствии с вышеизложенным записываем рядом косвенные и истинные тарифы, а также критерий оптимальности:
с12* = -8 с12 = 11 12 = -8 – 11 = -19 0
с15* = 7 с15 = 15 15 = 7 – 15 = -8 0
с21* = 7 с21 = 8 21 = 7 – 8 = -1 0
с22* = -5 с22 = 7 22 = -5 – 7 = -12 0
с24* = 8 с24 = 13 24 = 8 – 13 = -5 0
с31* = 17 с31 = 10 31 = 17 – 10 = 7 > 0
с33* = 19, с33 = 12 33 = 19 – 12 = 7 > 0
с34* = 18, с34 = 7 34 = 18 – 7 = 12 > 0.
Так как среди полученных оценок ijесть положительные то, план перевозок не оптимален и его необходимо улучшить.
5. Для удобства изложения воспроизведем опорный план перевозок (таблица № 11) еще раз как таблицу № 12.
Таблица № 12
| Поставщики | Потребители | Запасы | |||||||||||||||
| В1 1=4 | В2 2=-8 | В3 3=6 | В4 4=5 | В5 5=7 | |||||||||||||
| А1 1=0 | | 4 | | 11 | | 6 | | 5 | | 15 | 200 | ||||||
| 70 | | 0 | | 20 | | 110 | | 0 | | ||||||||
| А2 2=3 | | 8 | | 7 | | 9 | | 13 | | 10 | 200 | ||||||
| 0 | | 0 | | 130 | | 0 | | 70 | | ||||||||
| А3 3=13 | | 10 | | 5 | | 12 | | 7 | | 20 | 100 | ||||||
| 0 | | 80 | | 0 | | 0 | + | 20 | | ||||||||
| Потребность | 70 | 80 | 150 | 110 | 90 | | |||||||||||
Для клеток (3,1), (3,3), (3,4) ij > 0. Среди них выбираем клетку с максимальным значением ij. Это клетка с номером (3, 4). Ставим в ней знак "+".
Для нее строим цикл, вычеркивая в таблице №12 те столбцы и строки, в которых есть только одна поставка, считая, что в клетке (3, 4) также есть поставка.
Вычеркнутыми будут первый и второй столбец, выделим их серым цветом. Все остальные заполненные клетки образуют цикл а) на рис 3.
Каждой вершине цикла будут соответствовать чередующиеся знаки "+" или "-", расставлять которые надо, начиная с "" в клетке (3, 4), для которой мы строим этот цикл.
Затем в тех вершинах, где стоит знак "-", находим наименьшую поставку min{ 130, 110, 20}. Это 20 в вершине (3, 5).
Обозначим эту величину Δ = 20, и теперь величину Δ вычитаем из поставок в вершинах со знаком "-" и прибавляем в те вершины, где стоит "+" (см. рис. 3б). Новый цикл, полученный после пересчета, представлен на рис.3в.
| | + - | | 20+20 | | 110-20 | | 40 | 90 |
| (1,3) (2,3) |
130 | (1,4) + + | (2,5) | | 70+20 | | | 90 |
| | - (3;4) | 70 Δ = 20 | (3,5) | 130-20 +20 | | 20-20 | 110 20 | |
| | + | - | | | | | | |
| | а) | | б) | | в) | |||
Рис. 3. Цикл пересчёта для клетки (3, 4):
а) цикл в исходном плане; б) пересчёт по циклу; в) новый цикл.
6. Заменяя старый цикл в таблице № 12 на новый, получаем таблицу №13. Обратите внимание, что после пересчёта по циклу суммы поставок по строкам и столбцам не изменились и полученный план также невырожденный.
