Определение допустимого базисного решения транспортной
Задачи
При решении транспортных задач используют не симплексную таблицу, а матрицу перевозок, в которой совмещены матрица решений и матрица стоимости перевозок:
.
Таким образом, каждой клетке такой матрицы соответствуют два числа xij, cij, как показано в таблице 7.1.
Таблица 7.1
| Ai/Bj | B1 … | Bj | … Bn | |
| A1 | c11 x11 | … | c1n x1n | a1 |
| Ai | … | cij xij | … | ai |
| Am | cm1 xm1 | … | cmn xmn | am |
| b1 | bj | bn |
A1, …,Ai, …,Am – обозначения пунктов отправления, B1,…,Bj,…,Bn – обозначения пунктов назначения.
В матрице перевозок приведены также запасы пунктов отправления и потребности (заявки) пунктов назначения.
В матрице перевозок существуют базисные (занятые) и свободные (незанятые) клетки. Базисные клетки соответствуют базисным переменным, и в них записываются значения базисных неизвестных из допустимого базисного решения (в том числе и нулевые). Свободные клетки, соответствующие свободным переменным, не заполняются, нули в них не записываются. Число базисных переменных в матрице перевозок: r=m+n-1.
Существует несколько методов нахождения допустимого базисного решения.
Первым рассматривается диагональный метод (метод северо-западного угла) на конкретном примере с цифровыми данными, приведенными в таблице 7.2.
Таблица 7.2
| В1 | В2 | В3 | В4 | ||
| А1 | 2 х11=20 | 3 | 2 | 4 | 30 |
| А2 | 3 | 2 | 5 | 1 | 40 |
| А3 | 4 | 3 | 2 | 6 | 20 |
| 20 | 30 | 30 | 10 | å=90 |
При этом методе, начиная с угловых объектов, попытаемся удовлетворить потребность пункта В1 запасами пункта А1. Это можно сделать, т.к. a1>b1. Удовлетворим его, осуществив перевозки х11=20. Пункт В1 оказывается удовлетворенным полностью, поэтому этот столбец можно временно исключить, в результате получаем таблицу 7.3.
Таблица 7.3
| В2 | В3 | В4 | ai | |
| A1 | x12=10 | a1¢ 30-20=10 | ||
| A2 | 40 | |||
| A3 | 20 | |||
| bj | b2=30 | 30 | 10 | 70 |
Запасы пункта А1 при этом уменьшаются и становятся равными a1¢=30-20=10. Далее попытаемся удовлетворить потребность пункта В2 (играющего теперь роль первого) запасами пункта А1. Т.к. b2 > a1¢, то потребности можно удовлетворить лишь частично x12=10 единицами груза из А1. При этом потребности b2 сократятся и станут равными b2¢=b2 – a1¢=30 –10= 20, при этом запасы пункта А1 окажутся исчерпанными, и его строку можно исключить, что приводится в таблице 7.4.
Таблица 7.4
| В2 | В3 | В4 | ai | |
| A2 | x22=10 | 40 | ||
| A3 | 20 | |||
| bj | b2’=20 | 30 | 10 | 60 |
Для этой таблицы выбирается х22=20, при этом сокращаются запасы А2. Они становятся равными a2¢ = a2 – b2¢ = 20 единицам груза. Столбец В2 исключается, получается новая таблица.
Таблица 7.5
| В3 | В4 | ai | |
| A2 | x23=20 | а2’=20 | |
| A3 | x33=10 | x34=10 | 20 |
| bj | 30 | 10 | 40 |
В таблице 7.5 перевозится в текущем северо-западном углу x23=20, т. к. запасы А2 составляют только а2’=20. Исключается строка А2, а оставшиеся потребности b3’=b3 – a2 ’= 10 удовлетворяются перевозками x33=10 и x34=10. Следует заметить, что при каждом шаге удовлетворяется и вычеркивается только один пункт – либо отправления, либо назначения. И только на последнем шаге удовлетворяются одновременно два пункта.
Таким образом, получим для решения задач возможные допустимые значения базисных переменных х11=20, х12=10, х22=20, х33=10, х23=20, х34=10. Общая стоимость перевозок F=290. Это и есть допустимое базисное решение, приведенное в таблице 7.6.
Таблица 7.6
| В1 | В2 | В3 | В4 | ||
| А1 | 2 х11=20 | 3 х12=10 | 2 | 4 | 30 |
| А2 | 3 | 2 х22=20 | 5 х23=20 | 1 | 40 |
| А3 | 4 | 3 | 2 х33=10 | 6 х34=10 | 20 |
| 20 | 30 | 30 | 10 | å=90 |
Число базисных переменных равно r=m+n-1=6, т.е. соответствует требуемому числу базисных переменных.
Второй метод нахождения исходных базисных решений транспортной задачи - это метод наименьшей стоимости.
В этом методе выбор пунктов перевозки осуществляется с учетом стоимости, и на каждом шаге пытаются добиться меньшей стоимости перевозок.
| В1 | В2 | В3 | В4 | ai |
| A1 | 2 | 3 | 2 | 4 | |
| A2 | 3 | 2 | 5 | 1 x24=10 | |
| A3 | 4 | 3 0 | 2 | 6 | |
| bj | å=90 |
Из таблицы следует, что минимальная стоимость перевозок будет между пунктами А2 и В4, поэтому полагаем х24=10. Удовлетворяем пункт В4 и мысленно исключаем этот столбец. Запасы а2 уменьшились и стали a2¢ = a2 – b4¢ = 30. Следующая по цене стоимость «2» перевозок в нескольких клетках. Выбираем пункты А1 и В1, полагаем х11=20, тогда a1¢ = a1 – b1 = 10. Удовлетворяем В1 и исключаем его (мысленно) из рассмотрения. Затем выбираем клетку 2-2, полагаем х22=30 и исключаем строку А2, т.к. запасы исчерпаны (но В2 не исключаем, т.к. два исключения одновременно запрещаются), поэтому удовлетворим В2, но его «нулевая» потребность осталась.
Следующей клеткой (по-прежнему с ценой «2») выбираем 1-3, т.к. b3>a1, то возьмем x13 = a1’ = 10, исключаем строку А1. Потребность пункта В3 уменьшилась до b3’ = b3 – a1’=20. Теперь в матрице перевозок осталось два пункта В2 с нулевой потребностью b2 =0 и В3 с потребностью b3’ = 20. Удовлетворяем потребности В2 и В3, полагая х32=х33=20. F =170. Таким образом, получили допустимое базисное решение методом наименьшей стоимости.