2014-02-09
187Таблица 5.37
Таблица 5.36
Таблица 5.34
Таблица 5.32
| В А | |||||
| М | |||||
| Таблица 5.33 |
При нахождении потенциалов удобно считать, что 
. Тогда оставшиеся значения быстро находятся из системы уравнений (по занятым клеткам)
| В А | ui | ||||
| 6+(-1)-2=3>0 | 3+(-1)-4<0 | 6+(-1)-M<0 М | -1 | ||
| 2+(-2)-3<0 | 6+(-2)-5<0 | 6+(-2)-5<0 | -2 | ||
| vj |
Результаты вычислений, а также расчет оценок в свободных клетках приведены в таблице 5.34. В ней в ячейке (1;2) находится положительная оценка, значит, решение не оптимальное. Цикл для перехода будем строить, начиная с этой ячейки (других «кандидатов» просто нет). В цикл войдут ячейки (1;2), (3;2), (3;1), (1;1). При этом у ячеек (1;2) и (3;1) знак «+», у ячеек (3;2) и (1;1) знак «-». Из значений в «отрицательных» ячейках (50 и 40) наименьшее 40, это и будет перемещаемый объем перевозок q.
|
|
|
| В таблице 5.35 приведен результат перемещения по циклу (новое опорное решение), ячейка (3;2) освободилась, но число занятых клеток сохранилось. Результат нахождения потенциалов (проверьте!) и расчет оценок находятся в таблице 5.36. |
|
| В А | ui | ||||
| 3+(-1)-4<0 | 6+(-1)-M<0 М | -1 | |||
| 2+(-2)-3<0 | 3+(-2)-5<0 | 6+(-2)-5<0 | -2 | ||
| 3+0-6<0 | |||||
| vj |
| Итак, найденное решение оптимально (все оценки неположительны) – для задачи с таблицей 5.32. Теперь нужно вернуться к исходной задаче, в соответствии с правилами 1 и 2. Для этого объединим объемы перевозок из второго и четвертого столбца; запасы второй строки и запросы первого столбца увеличим на 30 (т.е. вернем в исходное состояние) и объем перевозок в ячейке (1;1) также увеличим на 30 (он был равен 0, поэтому получили 30). |
|
Оптимальный план исходной задачи дан в таблице 5.37 (обратите внимание, что за счет объединения столбцов и появления ненулевого объема перевозок в ячейке (2;1) количество занятых клеток больше числа N+M-1, равного в данной задаче 3+3-1=5). Итак, остается найти оптимальное значение целевой функции: 
.
Предположим, что существуют N потребителей и M поставщиков некоторого однородного груза, у каждого из поставщиков определенный запас этого груза (Ai единиц, i=1,2,…,M), а каждому из потребителей требуется Bj единиц груза (j=1,2,…, N). Известны также затраты cij на перевозку единицы груза от поставщика Ai к потребителю Bj. Требуется составить такой план перевозок от поставщиков к потребителям, чтобы суммарные затраты на перевозки оказались минимальными (при этом должны быть по возможности вывезены все запасы поставщиков и удовлетворены все запросы потребителей).
|
|
|
В случае, когда суммарные запасы совпадают с суммарными запросами, задача называется задачей с правильным балансом, а ее модель - закрытой. В противном случае говорят о задаче с неправильным балансом и об открытой модели. Существуют специальные приемы приведения открытой модели к закрытой (они будут рассмотрены позже).
Данные транспортной задачи обычно записываются в виде таблицы, заголовки строк которой содержат информацию о запасах, заголовки столбцов – информацию о запросах, а в нижнем правом углу каждой ячейки указывается стоимость перевозки единицы груза (затраты на перевозку единицы груза).
При составлении математической модели через xij обозначается количество единиц груза, который будет перевезен от поставщика Ai к потребителю Bj (объем перевозок от Ai к Bj). Эти значения будут вноситься в центр соответствующей ячейки.
С учетом сказанного целевая функция принимает вид
(просуммированы все произведения затрат на соответствующий объем перевозок). Ограничения связаны с вывозом запасов и удовлетворением запросов, поэтому математическая модель имеет вид:
| Пример 1. Транспортная задача задана с помощью таблицы 1, из которой видно, что на складах трех поставщиков A1, A2, A3 сосредоточены соответственно 30, 190 и 250 единиц груза, потребители B1, B2, B3, B4 нуждаются соответственно в 70, 120, 150, 130 единицах груза, а стоимости перевозок указаны непосредственно в таблице. |
Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:
 Сейчас читают про:
  7377 7296 |
