Учебное пособие 1817

Пример 6.3. Решить задачу, заданную табл. 6.9.

Таблица 6.9

Решение. Проверяем задачу на условие правильности баланса (см. теорему 6.1). Имеем

∑3 ai = 40 +30 +90 =160,

i =1

∑4 b j = 40 +20 +30 +60 =150.

j =1

Задача открытая: она неразрешима в такой постановке. Вводим «фиктивного» потребителя с потребностью b5 = 10

и принимаем ci5 = 0, i =1,3 .

Составим распределительную (транспортную) таблицу для новой закрытой задачи (табл. 6.10). В ней построим первоначальный план, определим его стоимость, вычислим потенциалы и проверим план на оптимальность.

«Фиктивный» потребитель (или отправитель, если он был), рассматривается в последнюю очередь.

1)Определим начальный план. Минимальный тариф с33 =

1.Положим х33 = min(30,90) = 30 и запишем эту поставку в клетке (3,3) минимального тарифа. Столбец j = 3 зачеркнем под номером 1.

Минимальные тарифы c12 = c34 = 2. Положим х1 2 = 20, зачеркнем под номером 2 столбец j = 2. Далее возьмем х34 = 60 и одновременно зачеркнем строку i = 3 и столбец j = 4 под

номером 3. Учитывая с11 = 3, запишем х11 = 20 и зачеркнем строку i = 1 под номером 4.

Следующая поставка х21 = 20 очевидна, и в последнюю очередь рассматриваем «фиктивного» потребителя, записывая

х25 = 10. План, как видим, вырожденный, потому что на третьем шаге зачеркнули две линии (под линией понимается либо строка, либо столбец). В одну из них запишем нуль, т.е. занимаем одну клетку либо в третьей строке, либо в четвертом столбце так, чтобы она не составляла с другими занятыми клетками замкнутый цикл. Из нескольких возможностей

выбираем х31 = 0, потому что на момент зачеркивания этих линий в столбце j = 1 сохранилась потребность в 20 ед. Полученный таким образом начальный план вырожденный, но занятых клеток имеем нужное количество: m + n – 1 = 7.

2)Потенциалы занятых клеток определим, исходя из

начального условия u1 = 0. Остальные потенциалы определим без труда и занесем их в эту же таблицу. Также в уме обнаруживаем, что среди оценок

i j = cij – ui - vj

отрицательных нет. Первоначальный план

84

в котором «фиктивный» потребитель участвует, является оптимальным, и стоимость этого плана равна

F(Х) = 20 • 3 + 20 • 2 + 20 • 5 + 30 • 1 + 60 • 2 + 10 • 0 = 350.

Задача решена. Остается исключить «фиктивного» потребителя, не влияющего на стоимость оптимального плана задачи.

Ответ:

Вопросы для самопроверки

6.1.Чем отличаются друг от друга транспортные задачи с правильным и с неправильным балансом?

6.2.В чем состоит метод наименьших тарифов построения начального решения (плана)?

6.3.Чем отличается вырожденное решение от невырожденного? Когда появляется то или другое?

6.4.Можно ли проверять на оптимальность вырожденное решение?

6.5.Каким образом получить невырожденное опорное решение?

6.6.Какстроитсяцикл? Вчемсостоитегоматематическийсмысл?

6.7.Какпроверитьнаоптимальностьполученноеопорноерешение?

6.8.Какулучшитьнеоптимальноерешениетранспортнойзадачи?

6.9.Может ли транспортная задача иметь два решения? бесконечно много решений?

6.10.Какимобразомрешитьоткрытуютранспортнуюзадачу?

85

7.Транспортная задача по критерию времени

7.1.Транспортная задача по критерию времени связана со срочными перевозками грузов. Имеется m поставщиков с

запасами однородного груза а1, а2, ..., аm и n потребителей того же груза с потребностями b1, b2, ..., bn . Известна матрица

промежутков времени, за которые грузы от i-го поставщика доставляются j-му потребителю. Эта матрица напоминает матрицу С тарифов из предыдущего параграфа, поэтому иногда для сравнения или сопоставления действий матрицу Т будем ассоциировать с матрицей С.

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

Решение. Проведем его по схеме общей транспортной задачи.

1)Сначала составляем начальный опорный план X методом «наименьших тарифов» (этот термин мы используем условно вместо термина «наименьших времен»).

2)Оптимальность плана проверяем известным методом потенциалов. Если план оптимален, то его выводим в ответ, а минимальное время его осуществления считаем равным

наибольшему из значений ti j из занятых клеток (наибольший из тарифов занятых клеток). В таком случае задача решена.

3)Если план неоптимален, то, как обычно, составляем оценки незанятых клеток, строим цикл с вершиной в клетке с наименьшей отрицательной оценкой и перераспределяем по

86

циклу соответствующую поставку θ. Одновременно с этим вычеркиваем все значения ti j , которые превышают время выполнения этого плана (или такие клетки далее не рассматриваются).

4) После перераспределения поставок по циклу получаем новый план, он может быть оптимальным или нет. В первом случае решение задачи обеспечивается за время, равное максимальному значению ti j из занятых клеток (ясно, что это время не больше предыдущего, потому что большие значения ti j удалены). Если план неоптимален, то повторяем действие из п.З).

Пример 7.1. Четыре поставщика с грузами соответственно в 550, 250, 300, 100 единиц могут обеспечить четырех потребителей, которые нуждаются соответственно в 400, 200, 150 и 450 единицах этих грузов.

Найти минимальное время на осуществление всех перевозок, если матрица времен имеет вид

Решение. Составляем рабочую таблицу (табл. 7.1).

Таблица 7.1

Методом «наименьших тарифов» строим первый опорный план, заполняя последовательно клетки (1,1), (4,4), (2,4), (1,4), (3,3), (3,2), (1,2).

В табл. 7.2, кроме опорного плана, внесены потенциалы занятых клеток.

Вычисляя потенциалы незанятых клеток, получаем две отрицательные оценки, поэтому план неоптимален. При этом время на его реализацию равно наибольшему из времен, записанных в занятых клетках, т.е. наибольшему из чисел 1, 2, 3, 7. Время равно 7 ед. Наименьшая отрицательная оценка соответствует клетке (4,2). Строим цикл с началом в этой клетке и вершинами в клетках (1,2), (1,4), (4,4). Величина поставки, которую надо перераспределить по этому циклу, равна θ = 50. Клетки с временами (тарифами) 8 и 9 можно вычеркивать или просто не использовать в дальнейшем (при их использовании время осуществления плана увеличивается).

Новый опорный план с соответствующими потенциалами заносим в табл. 7.3.

Таблица 7.2

Таблица 7.3

Все оценки незанятых клеток неотрицательны, полученный план — оптимальный.

Ответ: оптимальный план перевозок имеет вид

Время на его реализацию равно t = 3.

Вопросы для самопроверки

7.1.В чем состоит смысл транспортной задачи по критерию времени? Каков критерий в обычной транспортной задаче?

7.2.Могут ли быть открытые и закрытые задачи по критерию времени?

7.3.Надо ли считать стоимость выполнения плана в транспортной задаче по критерию времени?

89

8.Целочисленное программирование. Метод Гомори

8.1.Задача целочисленного программирования в канонической форме формулируется следующим образом:

найти экстремум линейной целевой функции

L(X ) = ∑n cj xj

j =1

при условиях

∑n ai j xj = bi , i =1, m, j =1

xj ≥ 0, xj −целые числа, j =1, n

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

Сначала напомним определения и способ нахождения целой и дробной частей данного действительного числа. Целой частью числа а называется наибольшее целое число [а], не превосходящее а. Разность {а} = а — [а] называется дробной частью числа а. Например,

1)если а =3, то [а] = 3, {а} = 0;

2)если а = 3,7, то [а] = 3, {а} = 0,7;

3)если а = -2, 8, то [а] = -3, {а} = -2,8 - (-3) = 0,2;

4)если а = -2/7, то [а] = -1, {а} = -2/7 + 1 = 5/7.

Вернемся к методу отсечения. Предположим, что среди

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

90

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

В таблице Гаусса строка неизвестных и строка, соответствующая этому уравнению, выглядят так:

x1 x2 … xp … xm xm+ 1 … xn св. чл.

0 0 … 1 … 0 ap , m+ 1 … apn bp

(неизвестное хр базисное, переменные хm+ 1 , хm+ 2 ,…, хn свободные). Согласно этому уравнению составим следующее неравенство (ограничение, отсечение):

Это уравнение присоединим к системе ограничений решенной задачи, т.е. составим новую таблицу Гаусса с дополнительным столбцом для нового неизвестного хn + 1 , содержащую последний блок таблицы решенной задачи и новую строку, соответствующую построенному уравнению.

Если решение новой задачи целочисленное, то тем самым получено решение исходной задачи (компоненту,

соответствующую хn +1 , отбрасываем). Если новое решение нецелочисленное, то повторяем описанный алгоритм.

В последнем блоке таблицы Гаусса выбираем строку с наибольшей дробной частью свободного члена. Составляем новое ограничение (отсечение), соответствующее этой строке, и решаем новую задачу. Процесс прекращается, как только все нужные компоненты оптимального решения станут целыми числами.

Замечание. Иногда в исходной задаче требование целочисленности всех компонент решения необязательно. В таком случае речь идет о частичной целочисленности и решение сводится к получению только нужных целых компонент. Если исходная задача задана не в канонической форме, то ее сначала следует привести к каноническому виду введением дополнительных неизвестных. На эти дополнительные неизвестные условия целочисленности не распространяется.

Пример 8.1. Решить задачу целочисленного программирования

L(X) = 2x1 + x2 → max,

x1 +2x2 + x3 = 9,3x1 + x2 + x4 =10,

xj ≥ 0, xj −целые числа, j =1,4.

Решение. Имеем дело с канонической задачей линейного программирования. Решим ее симплексным методом без учета требования целочисленности. Таблица Гаусса (табл. 8.1), соответствующая решению задачи, имеет вид

92

Таблица 8.1

Полученное оптимальное решение Х1 = (11/5,17/5,0,0) не целочисленное, Lmах(Х1) = 39/5.

Применим метод Гомори. В последнем блоке таблицы определим максимальную дробную часть свободных членов:

Составим ограничение, соответствующее уравнению (первой строки)

Это неравенство заменим равенством (см. U.1 из п. 1),

Составим новую таблицу Гаусса (табл. 8.2), содержащую последний блок предыдущей таблицы, к которому присоединим построенное последнее уравнение (в таблице вводится дополнительный столбец для дополнительной неизвестной).

Таблица 8.2

Получили новое оптимальное решение с одной целой компонентой X2 = (7/3,3,2/3,0,0) — нецелое оптимальное

решение, Lmах(Х2) = 23/3.

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

Максимальная дробная часть свободного члена в последнем блоке соответствует третьей строке, т.е. уравнению

94

x3 + 43 x4 − 53 x5 = 23 .

Составим новое неравенство (отсечение):

23 − 13 x4 − 13 x5 ≤ 0,

или уравнение

−13 x4 −13 x5 + x6 = − 23 .

Новая рабочая таблица имеет вид табл. 8.3 (заметим, что и здесь выполним симплекс-преобразование с отрицательным разрешающим коэффициентом, поскольку система ограничений содержит недопустимое решение, а условие оптимальности удовлетворяется).

Таблица 8.3

Некоторые компоненты оптимального решения (нас интересуют только x1, x2, х3 и x4) Х3 = (5/3, 11/3,0,4/3,2/3,0) не являются целыми числами, при этом L(Х3) = 7, поэтому надо строить очередное отсечение, которое соответствует уравнению (второй строки). Новое уравнение имеет вид

23 − 23 x3 − 23 x6 + x7 = 0, или − 23 x3 − 23 x6 + x7 = − 23 .

Третью строку, содержащую базисную неизвестную х5, отбрасываем, так как х5 является дополнительной неизвестной, а в качестве разрешающего будем брать новое уравнение, из которого найдем значение некоторой базисной неизвестной

(табл. 8.4).

Таблица 8.4

компоненты (было бы достаточно, если бы целыми были только первые четыре компоненты).

Отбрасывая значения дополнительных неизвестных,

составляем ответ: Хопт = (2,3,1,1) и Lmax(2,3,1,1) = 7.

II. Прикладные задачи оптимизации

1. Оптимизация планирования комплекса работ

1°. Основным материалом для сетевого планирования является список или перечень работ, который называется структурной таблицей комплекса работ. В структурной таблице для нахождения ai должно быть указано, выполнение каких работ она требует или на какие работы опирается.

называется работой 1-го ранга, если для ее начала не требуется выполнение никаких других работ. Работа называется работой второго ранга, если она опирается на одну или несколько работ первого ранга и т. д.

97

Если задано ti - время выполнения работы ai , то

минимально возможный срок окончания работы находится по формуле

i=1

примере 1.2.

3°. Рассмотрим задачу перераспределения уже имеющихся средств между отдельными работами. Известно, что

98

количество средств x > 0, снятое с работы ai , увеличивает время ее выполнения с t i до ti¢ = fi (xi ) , а количество средств x , вложенных дополнительно в работу al уменьшает время ее

выполнения до ti ² =ji (x) . Сумма средств, снимаемых с каких-

то работ, должна быть равна сумме средств, добавляемых к другим работам, так что

где Ф – функция Лапласа находится из таблицы. 99

1.1. Пусть дана упорядоченная структурная таблица

Построить временный график и найти критические работы. Решение. Для работы первого ранга имеем:

t1 = 0 ; t 2 = 0 ;t 3 = 0 ;T1 = t1 = 10 ;T2 = t2 = 5 ;T3 = t3 = 15 .

Работа a4 опирается на работыa1 ,a2 , т.е. она может начаться тогда, когда закончится наиболее большая работа t 4 = max{T1 ,T2 } = max{10,5}= 10 .