III этап. Определение переменной, выводимой из базиса

↑

▷ Содержание

⇐ ПредыдущаяСтр 56 из 58Следующая ⇒

(построение цикла).

Процедура построения цикла эквивалентна использова- нию условия допустимости в симплекс-методе.

1. Строится замкнутый цикл, соответствующий вводимой переменной. Он состоит из последовательности горизонталь- ных и вертикальных связанных отрезков, концами которых должны быть базисные переменные (за исключением тех кон- цов, которые относятся к вводимой в базис переменной). Для каждого базисного решения и соответствующей небазисной переменной можно построить лишь один цикл.

2. Нечетным вершинам цикла (начиная с вводимой в базис переменной) присваивается знак “+”, четным — “−” (будем на- зывать эти клетки плюсовыми и минусовыми).

3. Определяется выводимая из базиса переменная, кото- рой является одна из базисных переменных, расположенных в вершинах цикла, отмеченных знаком “−” и имеющих наимень- шее значение.

4. Формируется новое допустимое базисное решение. Для этого переменные, находящиеся в вершинах цикла, соответс- твующим образом корректируются, а именно уменьшаются или увеличиваются на величину вводимой в базис переменной в зависимости от знака вершины цикла.

Описанный выше переход от одного опорного плана транс- портной задачи к другому ее опорному плану называется сдви- гом по циклу пересчета. Следует отметить, что при сдвиге по циклу пересчета число занятых клеток остается неизменным и равным (n + m − 1).

Однако при определении опорного плана или в процессе решения задачи может быть получен вырожденный опорный план. Чтобы избежать зацикливания, следует соответствую- щие нулевые элементы опорного плана заменить сколь угодно малым числом ε и решать задачу как невырожденную. В опти- мальном плане такой задачи необходимо считать ε = 0.

Пример 10.1. Найти квазиоптимальное решение транспор- тной задачи по методу Фогеля.

Матрица транспортной задачи представлена таблицей вида:

В скобках в клетках таблицы представлены цены пере- возок.

Найти план по методу Фогеля.

Решение

Справка

Поиск квазиоптимального решения транспортной задачи по алгоритму Фогеля включает выполнение следующих шагов:

a) Для каждой строки таблицы упорядочить элементы цен перевозок cij по возрастанию. Вычислить величину так называ- емого штрафа строки как разность значений второго и первого элемента в ранжированном ряду.

b) Для каждого столбца таблицы упорядочить элементы цен перевозок cij по возрастанию и вычислить величину “штра- фа столбца” аналогично шагу 1.

c) Найти строку или столбец, имеющую (имеющий) на- ибольший штраф по всем штрафам строк и столбцов, а в ней (в нем) — элемент с минимальной величиной стоимости перево- зок cij. Зафиксировать индексы (i, j) этого элемента.

d) Присвоить переменной xij, индексы которой соответс-

твуют шагу с, наибольшее из допустимых для нее значений (с учетом ограничений задачи).

e) Скорректировать величины аi и bj и вычеркнуть строку i, если оказалось, что аi  = 0, или столбец j, если bj  = 0.

f) Проверить, все ли величины аi  и bj  равны нулю. Если

да, то окончить вычисления; в противном случае взять в ка- честве исходной оставшуюся часть таблицы и перейти к шагу с алгоритма.

2. Вычисляем штрафы строк:

Ранжированные цены в строках: Штрафы строк: (0,4; 2,7; 4,0; 4,8)     2,3

(0,6; 1,9; 3,2; 4,0)                            1,3

(1,0; 1,1; 2,2; 4,6)                            0,1

3. Вычисляем штрафы столбцов:

Штрафы столбцов: Разности штрафов столбцов: (0,4; 0,6; 4,6)           0,2

(1,0; 3,2; 4,0)                               2,2

(1,9; 2,2; 2,7)                               0,3

(1,1; 4,0; 4,8)                               2,9

4. Определяем максимальный штраф. Он составляет 2,9 и находится в четвертом столбце. Фиксируем элемент с наимень- шей ценой перевозок в четвертом столбце: это элемент с коор- динатами (3, 4).

5. Присвоим переменой x34 наибольшее из допустимых для нее значений 20.

6. Корректируем содержимое исходной таблицы, уменьшив запас на складе А3 на 20 т и вычеркнув четвертый столбец:

7. Вычисляем штрафы строк:

Ранжированные цены в строках: Штрафы строк: (0,4; 2,7; 4,0) 2,3

(0,6; 1,9; 3,2)                                1,3

(1,0; 2,2; 4,6)                                1,2

8. Вычисляем штрафы столбцов:

Штрафы столбцов: Разности штрафов столбцов: (0,4; 0,6; 4,6)           0,2

(1,0; 3,2; 4,0)                               2,2

(1,9; 2,2; 2,7)                               0,3

9. Определяем максимальный штраф. Он составляет 2,3 и на- ходится в первой строке. Фиксируем элемент с наименьшей ценой перевозок в первой строке: это элемент с координатами (1, 1).

10. Присвоим переменой x11 наибольшее из допустимых для нее значений 30.

11. Продолжая действовать таки образом, окончательно получим квазиоптимальный план перевозок:

Можно проверить, что полученное решение оказалось оп- тимальным.

10.3. Практическое решение задачи оптимального планирования

Перевозки товаров различными транспортными средства- ми в ряде случаев приводят к таким нежелательным явлениям, как порожние пробеги, простои, встречные и нерациональные перевозки. Для их исключения используются методы опти- мального планирования перевозок, в частности такая экономи- ко-математическая модель, как транспортная задача.

Простейшим примером транспортной задачи является задача о планировании перевозок некоторого продукта из ко- нечного числа пунктов отправления в конечное число пунктов назначения при обеспечении минимальных затрат на выполне- ние данной операции.

Постановку и методику решения подобных задач рассмот- рим с использованием следующего примера:

Пример 10.2. Три поставщика некоторого товара распола- гают следующими запасами: первый — 120 единиц, второй — 100 единиц, третий — 80 единиц. Товар должен быть перевезен трем потребителям: спрос первого — 90 единиц; спрос второ- го — 90 единиц; спрос третьего — 120 единиц. Известны также

показатели затрат (cij) на перевозку единицы товара от каждо- го поставщика к каждому потребителю.

Требуется составить оптимальный план перевозок, приводя- щий к наименьшим затратам на выполнение данной операции.

Под планом перевозок понимается матрица

x11  x12 x13 x21  x22 x23 x31 x32 x33,

в которой xij — количество единиц товара, планируемого к пе- ревозке от поставщика с номером i к потребителю с номером j.

Для решения задачи исходные данные удобно свести в табл. 10.2.

Таблица 10.2

Поставщики

Возможности поставщиков

Потребители и их спрос

Постав- щики

Возможности поставщиков

Потребители и их спрос

A i

1

2

90

90

1

120

Bj

7

6

90

90

120

7

8

2

7