МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ Белорусский национальный технический университет МЕТОДЫ ЛИНЕЙНОЙ И СЕТЕВОЙ ОПТИМИЗАЦИИ Методические указания и контрольные задания М и н с к Б Н Т У 2 0 1 3 МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ Белорусский национальный технический университет МЕТОДЫ ЛИНЕЙНОЙ И СЕТЕВОЙ ОПТИМИЗАЦИИ Методические указания и контрольные задания для студентов заочной формы обучения Минск БНТУ 2013 2 УДК 519.85 (075.8) ББК 18я7 М54 С о с т а в и т е л и : А.Д. Корзников, Л.Д. Матвеева Р е ц е н з е н т ы : А.Н. Рудый, В.В. Карпук Издание включает в себя изложение теоретических методов решения основных задач мате- матического программирования, а также контрольные задания по каждой теме для самостоятельного решения. Состоит из семи разделов, по каждому из которых предлагается 24 задачи. В каждом разделе описывается теоретическое обоснование метода, формальный алгоритм и пример решения типовой задачи. Предназначено для студентов экономических специальностей заочного отделения БНТУ. Может быть полезно преподавателям, ведущим практические занятия по курсу математического программирования.  Белорусский национальный технический университет, 2013 3 I. Решение задачи линейного программирования симплекс-методом Задачей линейного программирования в канонической форме называется задача: Z = c1 x1 + c2 x2 + . . .+ cn xn  min (max) (1.1) при ограничениях : a11 x1 + a12 x2 + . . .+ a1n xn = b1 a21 x1 + a22 x2 + . . .+ a2n xn = b2 (1.2) . . . . . . . . . . . . . . . . . . . . . . . . . . . am1 x1 + am2 x2 + . . .+ amn xn = bm , xj  0 , j = 1, . . . , n (1.3) Симплекс-метод является вычислительной процедурой, которая позво- ляет решить любую каноническую ЗЛП алгебраическим методом. Теоретичес- кой основой метода являются следующие два утверждения: Теорема 1. Если ЗЛП имеет допустимые решения, то существует хотя бы одно базисное допустимое решение задачи. Теорема 2. Если ЗЛП имеет конечное оптимальное решение, то хотя бы одно из оптимальных решений является базисным. Суть симплекс-метода и состоит в последовательном переборе базисных допустимых решений системы (1.2), начиная с некоторого начального, которое еще называют первоначальным опорным планом. Перебор осуществляется таким образом, чтобы каждое новое решение было лучше предыдущего (в смысле приближения к максимуму или минимуму целевой функции Z). Итак, для применения метода необходимо, чтобы задача была в канони- ческой форме, и чтобы существовало начальное базисное допустимое решение (опорный план), наличие которого гарантирует непротиворечивость ограниче- ний задачи. Чтобы преобразовать ЗЛП к каноническому виду к правой части каждого ограничения-неравенства прибавляют или вычитают неотрицательную допол- 4 нительную переменную, например, ограничение 3х1 + 5х2 – 2х3  7 преоб- разуется в уравнение 3х1 + 5х2 – 2х3 + х4 = 7 прибавлением дополнительной переменной х4  0, а неравенство вида х1 – 2х2 + х3  5 заменяется на уравнение х1 – 2х2 + х3 - х5 = 5, где х5  0. Заметим, что знак неравенства  можно заменить на  умножением всего неравенства на -1, например, неравенство х1 – 3х2  -6 эквивалентно неравенст- ву -х1 + 3х2  6. Отметим также, что максимизацию целевой функции Z можно заменить на минимизацию функции –Z и наоборот, так как максимум функции Z = c1 x1 + c2 x2 + . . .+ cn xn достигается в тех же точках, что и минимум функции -Z = -c1 x1 - c2 x2 - . . .- cn xn . Алгоритм симплекс-метода Исходные данные: задача в канонической форме; целевая функция мини- мизируется; найдено начальное базисное допустимое решение (опорный план), то есть система уравнений (1.2) имеет базис и все правые части уравнений bi  0 – неотрицательны; целевая функция выражена через свободные переменные. При выполнении этих условий каждая итерация метода состоит из трех шагов: Шаг 1 . Имеющийся план проверяется на оптимальность. Если в Z – стро- ке нет отрицательных элементов, то имеющийся план оптимален и задача реше- на. Если отрицательные элементы есть, то план не оптимален. Выбираем любой отрицательный элемент Z – строки (как правило, максимальный по модулю) и считаем столбец, в котором он находится в качестве разрешающего. Пусть для определенности это столбец переменной хs. Шаг 2. Выбор разрешающей строки. Пусть разрешающий столбец, вы- бранный на предыдущем шаге, это столбец переменной хs. Для каждой i-ой строки (i = 1,...,m) делим элементы столбца свободных членов “Значение” (напомним, что все они неотрицательные) на положительные элементы 5 разрешающего столбца, стоящие в этой строке, и находим минимальное из полученных частных, т.е. находим .min 0, rs r is i ai a b a b is   Пусть этот минимум достигается в строке r . Тогда r-ая строка является разрешающей, элемент ars – разрешающий элемент таблицы. Шаг 3. Пересчет таблицы. Преобразованиями Жордана-Гаусса пересчи- тываем таблицу относительно разрешающего элемента ars , найденного на предыдущем шаге, для чего: 3.1. Делим разрешающую строку на разрешающий элемент. В результате, на месте элемента ars будет стоять аrs = 1. 3.2. Ко всем остальным строкам таблицы (включая Z – строку) прибав- ляем полученную разрешающую, умноженную на элемент (-ais), где i – номер изменяемой строки i =1,2,...,r-1,r+1,...,m. К Z – строке прибавляем разрешаю- щую строку, умноженную на (-cs). Иначе говоря, элементы новой таблицы (со штрихом) вычисляются по формулам: аrj = arj/ars ; br = br/ars , аij = aij - arj ais ; bi = bi - br ais , cj = cj - arj cs , Z = Z - br cs; ( 1, 2,..., ; 1, 2, ..., )i m j n  . Переходим к шагу 1 и повторяем всю процедуру для нового плана Х. Поскольку базисных решений системы (1.2) конечное число, а каждое новое базисное решение лучше предыдущего, то этот процесс завершится за конечное число шагов. Решение задачи линейного программирования в общем случае. Рас- смотрим следующую задачу ЛП: Z = - 3x1 + х2  min 2x1 – х2  2, -x1 + 2х2  5, x1 + х2  10, x1, х2  0. 6 Приведем ее к каноническому виду введением трех неотрицательных пе- ременных х3, х4, х5. Получим задачу: Z = - 3x1 + х2  min 2x1 – х2 - х3 = 2, -x1 + 2х2 - х4 = 5, (1.4) x1 + х2 + х5 = 10, x1, х2, х3, х4, х5  0. Для решения задачи применим метод искусственного базиса. Введем в первые два уравнения (третье не создает проблем) искусственные переменные х6  0 и х7  0. В результате получим базис из переменных х6, х7, х5 . 2x1 – х2 - х3 + х6 = 2, -x1 + 2х2 - х4 + х7 = 5, (1.5) x1 + х2 + х5 = 10, Соответствующее базисное решение Х0 = (0, 0, 0, 0, 10, 2, 5) является до- пустимым для ограничений (1.5). С целью исключения искусственных переменных из базисного решения системы ограничений (1.5), т.е. для получения допустимого базисного решения системы ограничений (1.4), используем алгоритм симплекс-метода. Для того, чтобы искусственные переменные стали свободными, необходимо, чтобы они были равны нулю (сейчас х6 = 2 , х7 = 5 ). Поэтому введем искусственную целевую функцию W = х6 + х7. и будем ее минимизировать при ограничениях (1.5). Если удастся найти базисное допустимое решение при котором W = 0 (сейчас W = 7), то тогда х6 и х7 будут равны нулю, поскольку они неотрицательны, и мы получим базис из основных и дополнительных переменных. Таким образом, задача разбивается на два этапа. На первом этапе мини- мизируется искусственная целевая функция W. Этот этап закончится либо нахождением опорного плана исходной задачи (1.4), либо тем, что минимизи- 7 ровать функцию W до нуля не удастся, т.е. допустимых планов нет, а значит (ввиду теоремы 1) и нет вообще допустимых решений задачи. Если опорный план найдется, то на втором этапе решаем задачу симп- лекс-методом. Проиллюстрируем описанный выше метод искусственного бази- са, применив его к решению задачи (1.4). Этап 1 . Составим исходную симплекс-таблицу для задачи (1.5). Все вычисления будем проводить также и для целевой функции Z. Тогда после завершения первого этапа получим целевую функцию Z , выраженную через свободные переменные. Таблица 1.1 Базис х1 х2 х3 х4 х5 х6 х7 Значение x6 х7 x5 2 -1 -1 0 0 1 0 -1 2 0 -1 0 0 1 1 1 0 0 1 0 0 2 5 10 - Z -3 1 0 0 0 0 0 0 - W 0 0 0 0 0 1 1 0 Для того, чтобы начать минимизацию функции W, ее надо выразить через свободные переменные. Для этого, из W – строки вычтем первую и вторую строки. Получим Таблица 1.2 Базис х1 х2 х3 х4 х5 х6 х7 Значение x6 х7 x5 2 -1 -1 0 0 1 0 -1 2 0 -1 0 0 1 1 1 0 0 1 0 0 2 5 10 - Z -3 1 0 0 0 0 0 0 - W -1 -1 1 1 0 0 0 -7 8 Так как в W – строке есть отрицательные элементы, то выбираем в качест- ве разрешающего любой из первых двух столбцов, например первый. Посколь- ку min{2/2, 10/1} = 1 достигается в первой строке, то разрешающая строка – первая и разрешающий элемент а11 = 2. Пересчитывая таблицу относительно этого элемента, получим новую таблицу: Таблица 1.3 Базис х1 х2 х3 х4 х5 х7 Значение x1 х7 x5 1 -1/2 -1/2 0 0 0 0 3/2 -1/2 -1 0 1 0 3/2 1/2 0 1 0 1 6 9 - Z 0 -1/2 -3/2 0 0 0 3 - W 0 -3/2 1/2 1 0 0 -6 Так как переменная х6 вышла из базиса, то в дальнейшем ее не исполь- зуем (вычеркиваем столбец х6 ). Теперь разрешающим столбцом будет второй, разрешающей строкой – вторая и после пересчета получим (поскольку искусственная переменная х7 выйдет из базиса, столбец х7 также вычеркиваем) : Таблица 1.4 Базис х1 х2 х3 х4 х5 Значение x1 х2 x5 1 0 -2/3 -1/3 0 0 1 1/3 -2/3 0 0 0 1 1 1 3 4 3 - Z 0 0 -5/3 -1/3 0 5 Этап 1 успешно завершен, так как искусственные переменные выведены из базиса и мы получили опорный план Х0 = (3, 4, 0, 0, 3 ) исходной задачи (1.4), к которому можно применить алгоритм симплекс-метода. На втором этапе W - строка уже не нужна и мы ее вычеркиваем. 9 Этап 2. Таблица 1.5 Базис х1 х2 х3 х4 х5 Значение x1 х2 x5 1 0 -2/3 -1/3 0 0 1 -1/3 -2/3 0 0 0 1 1 1 3 4 3 - Z 0 0 -5/3 -1/3 0 5 Целевую функцию Z можно уменьшить (сейчас Z = -5) если ввести в базис х3 или х4. Выбираем третий столбец в качестве разрешающего, т.к. –5/3 < -1/3. Разрешающей строкой будет третья, т.к. только в ней есть положительный эле- мент разрешающего столбца. Разрешающий элемент а33 = 1. Пересчитывая таблицу, получим: Таблица 1.6 Базис х1 х2 х3 х4 х5 Значение x1 х2 x3 1 0 0 1/3 2/3 0 1 0 -1/3 1/3 0 0 1 1 1 5 5 3 - Z 0 0 0 4/3 5/3 10 Поскольку в Z – строке таблицы 1.6 нет отрицательных элементов, то новый план Х1 = (5, 5) является оптимальным и Zmin = Z(5,5) = -10 . Задача решена полностью. Контрольные задания для самостоятельного решения. Задание 1 Решить задачу линейного программирования симплекс-методом (x, y  0). 10 Варианты 1. 2 min 3 8 4 5 29 4 10 z x y x y x y x y            2. min 3 2 7 2 13 2 1 z x y x y x y x y             3. 2 max 2 3 1 3 2 3 z x y x y x y x y              4. max 2 3 5 2 8 3 10 z x y x y x y x y             5. 2 min 5 2 9 3 11 z x y x y x y x y             6. 2 max 2 10 2 4 2 2 z x y x y x y x y            7. 2 max 0 3 2 3 5 4 1 z x y x y x y x y            8. max 0 2 4 3 4 2 z x y x y x y x y             9. 5 2 max 3 9 2 7 5 2 17 z x y x y x y x y            10. 2 4 max 3 8 3 4 2 11 z x y x y x y x y             11. 2 max 5 4 4 2 z x y x y x y x y             12. min 3 7 2 7 5 7 z x y x y x y x y            13. 3 max 6 5 3 5 29 3 4 7 z x y x y x y x y             14. 3 2 max 3 2 1 4 17 3 z x y x y x y x y              15. 2 5 max 4 3 2 12 2 5 3 z x y x y x y x y            16. 3 min 3 2 11 3 1 6 19 z x y x y x y x y             17. 3 4 max 4 5 11 5 19 4 13 z x y x y x y x y            18. 3 max 3 8 8 3 10 5 4 19 z x y x y x y x y            11 19. 2 max 3 7 4 17 3 2 1 z x y x y x y x y            20. 2 max 5 2 5 18 5 2 18 z x y x y x y x y             21. 3 max 4 3 5 28 9 12 z x y x y x y x y             22. 2 max 3 13 4 13 4 3 13 z x y x y x y x y            23. 3 5 5 max 8 3 3 1 3 4 16 z x y z x z x y z x y z                24. 6 2 max 3 2 15 3 2 13 3 2 13. z x y z x y x y z x y z               II. Двойственность в линейном программировании. Экономический смысл двойственных переменных Рассмотрим задачу линейного программирования в общей форме: Z = c1 x1 + c2 x2 + . . .+ cn xn  max (2.1) при ограничениях : y10 a11 x1 + a12 x2 + . . .+ a1n xn  b1 y20 a21 x1 + a22 x2 + . . .+ a2n xn  b2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (2.2) yk0 ak1 x1 + ak2 x2 + . . .+ akn xn  bk yk+1 ak+1 1 x1 + ak+1 2 x2 + . . .+ ak+1 n xn = bk+1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ym am1 x1 + am2 x2 + . . .+ amn xn = bm , xj  0 , j = 1, . . . , l; l  n (2.3) Каждому i-му ограничению из (2.2) соответствует переменная yi так назы- ваемой двойственной задачи к задаче (2.1) – (2.3) (показана слева от соответст- вующего ограничения). Двойственная задача имеет вид: W = b1 y1 + b2 y2 + . . .+ bm xm  min (2.4) 12 при ограничениях : x1  0 a11 y1 + a21 y2 + . . .+ am1 ym  c1 x2  0 a12 y1 + a22 y2 + . . .+ am2 ym  c2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (2.5) xl  0 a1l y1 + a2l y2 + . . .+ aml ym  cl xl+1 a1 l+1 y1 + a2 l+1 y2 + . . .+ a m l+1 ym = cl+1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xn a1n y1 + a2n y2 + . . .+ amn ym = cn , yi  0 , i = 1, . . . , k ; k  n (2.6) Задачи (2.1) – (2.3) и (2.4) – (2.6) образуют пару задач, называемую в линейном программировании двойственной парой. Теорема 1. (Основная теорема двойственности). Если одна из пары двойственных задач имеет оптимальный план, то и другая имеет оптимальный план причем значения целевых функций задач при их оптимальных планах сов- падают, т.е. Zmax = Wmin. Если же целевая функция одной из задач не ограничена (для исходной (2.1) – (2.3) – сверху, для двойственной (2.4) – (2.6) – снизу), то другая задача вообще не имеет допустимых решений. Теорема 2. (Вторая теорема двойственности). Для того, чтобы два до- пустимых решения ),...,,( **2 * 1 * nxxxX  и ),...,,( ** 2 * 1 * myyyY  пары двойствен- ных задач были их оптимальными решениями, необходимо и достаточно, чтобы они удовлетворяли системам уравнений: njxcya j m i jiij ,...,2,10)( * 1 *   miybxa i n j ijij ,...,2,10)( * 1 *   (2.7) Замечание. Соотношения (2.7) верны только для ограничений в виде неравенств и для неотрицательных переменных. 13 Экономическую интерпретацию двойственных задач рассмотрим на примере. Пример. Для производства трех видов изделий А, В и С используются три различных вида сырья. Каждый из видов сырья может быть использован в количестве, соответственно не большем 180, 210 и 244 кг. Нормы затрат каждого из видов сырья на единицу продукции данного вида и цена единицы продукции каждого вида приведены в таблице 2.1. Требуется : а) составить математическую модель задачи; б) найти план выпуска продукции, обеспечивающий предприятию максимальную прибыль; в) проанализировать результаты решения задачи; г) построить математическую модель двойственной задачи; д) используя соответствие между переменными пары взаимодвойствен- ных задач, найти решение двойственной задачи; е) указать наиболее дефицитный и избыточный ресурс, если он есть. Таблица 2.1 Вид сырья Нормы затрат сырья (кг) на единицу продукции А В С I 4 2 1 II 3 1 3 III 1 2 5 Цены единицы продукции 10 14 12 Решение. а) Пусть производится x1 изделий А, x2 изделий В и x3 изделий С. Суммарная прибыль предприятия выразится формулой 1 2 310 14 12Z x x x   . Поскольку имеются ограничения на выделенный предприятию фонд сырья каждого вида, то математическая модель задачи имеет следующий вид: 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 10 14 12 max, 4 2 180, 3 3 210, 2 5 244, , , 0. Z x x x x x x x x x x x x x x x                 (2.8) б) Приведем задачу (2.8) к канонической форме путем введения в ограничения неотрицательных дополнительных переменных x4 , x5 , x6 : 14 1 2 3 1 2 3 4 1 2 3 5 1 2 3 6 10 14 12 max, 4 2 180, 3 3 210, 2 5 244, 0, 1, 6.j Z x x x x x x x x x x x x x x x x j                     (2.9) Переменные x4 , x5 , x6 в задаче (2.9) – базисные, начальный базисный план X=(0; 0; 0; 180; 210; 244). Решаем задачу (2.9) симплекс – методом, описанным в теме 1. Составим исходную симплексную таблицу. Таблица 2.2 Базис х1 х2 х3 х4 х5 х6 Значение(bi) x4 х5 x6 4 2 1 1 0 0 3 1 3 0 1 0 1 2 5 0 0 1 180 210 244 Z -10 -14 -12 0 0 0 0 В Z – строке есть отрицательные элементы. Так как min(-10; -14; -12)=-14, то второй столбец – разрешающий. Поскольку 180 210 244 min , , 90 2 1 2       достигается в первой строке, то разрешающая строка – первая и разрешающий элемент а12=2. Пересчитывая таблицу относительно этого элемента получим новую таблицу: Таблица 2.3 Базис х1 х2 х3 х4 х5 х6 Значение(bi) x2 х5 x6 2 -1 1/2 1/2 0 0 1 0 5/2 -1/2 1 0 -3 0 4 -1 0 1 90 120 64 Z 18 0 -5 7 0 0 1260 15 Теперь разрешающим столбцом будет третий, а разрешающей строкой – третья, и после пересчета получим Таблица 2.4 Базис х1 х2 х3 х4 х5 х6 Значение(bi) x2 х5 x3 19/2 1 0 5/8 0 -1/8 23/8 0 0 1/8 1 -5/8 -3/4 0 1 -1/4 0 1/4 82 80 16 Z 57/4 0 0 23/4 0 5/4 1340 1y  2y  3y  В Z – строке нет отрицательных элементов. Оптимальный план имеет вид X*=(0; 82; 16). При этом Zmax=1340. в) Результаты решения задачи (2.8) показывают, что предприятие изготавливает 82 изделия В и 16 изделий С. Максимальная прибыль при этом составляет 1340 ден. ед. Подставим решение X* в основные ограничения задачи (2.8): 4.0 2 82 16 180 3.0 82 3 16 130 210 0 2 82 5 16 244                 Следовательно, ресурс второго вида остался в избытке в количестве 80 единиц (x5=80). Ресурсы первого и третьего вида использованы полностью. г) Построим двойственную задачу для задачи (2.8). Припишем каждому из видов сырья, используемых для производства продукции, двойственную оценку, соответственно равную y1 , y2 , y3 . Тогда общая оценка сырья, используемого на производство продукции, составит 1 2 3180 210 244 minW y y y    . (2.10) Согласно условию, двойственные оценки должны быть такими, чтобы общая оценка сырья, используемого на производство единицы продукции 16 каждого вида, была не меньше цены единицы продукции данного вида, т.е. y1 , y2 , y3 должны удовлетворять следующей системе неравенств: 1 2 3 1 2 3 1 2 3 4 3 10, 2 2 14, 3 5 12, y y y y y y y y y            (2.11) 1 2 3, , 0.y y y  (2.12) Задачи (2.8) и (2.10) – (2.12) образуют симметричную пару двойственных задач. Решение прямой задачи дает оптимальный план производства изделий А, В и С, а решение двойственной – оптимальную систему оценок сырья, используемых для производства этих изделий. д) Решение двойственной задачи находим по последней симплекс– таблице в Z – строке. Для этого воспользуемся соответствием переменных прямой и двойственной задач. Элементы Z – строки, соответствующие переменным, которые входили в исходный базис, совпадают с переменными 1y  , 2y  , 3y  оптимального плана двойственной задачи. Следовательно, согласно основной теореме двойственности имеем: min max 23 5 ; 0; , 1340 4 4 Y W Z         . е) Двойственные оценки определяют дефицитность используемого предприятием сырья. Так как 1y  и 3y  отличны от нуля, то сырье первого и третьего видов является дефицитными. При этом 1y =23/4 > 3y =5/4, что означает – наиболее дефицитным является сырье первого вида. Поскольку 2y =0, то ресурс второго вида является избыточным. 17 Контрольные задания для самостоятельного решения. Задание 2 Постановка задачи. Для производства трех видов продукции используются три вида сырья. Нормы затрат каждого из видов сырья на единицу продукции данного вида, запасы сырья, а также прибыль с единицы продукции приведены в таблицах вариантов. Определить план выпуска продукции для получения максимальной прибыли при заданном дополнительном ограничении. Оценить каждый из видов сырья, используемых для производства продукции. Требуется: 1) построить математическую модель задачи; 2) выбрать метод решения и привести задачу к канонической форме; 3) решить задачу(симплекс-методом); 4) проанализировать результаты решения; 5) составить к данной задаче двойственную и, используя соответствие переменных, выписать ответ двойственной задачи; 6) дать экономическую интерпретацию двойственных оценок; 7) указать наиболее дефицитный и избыточный ресурс, если он есть. Вариант 1 Продукция Сырье А В С Запасы сырья, ед. I 3 2 - 18 II - 1 1 4 III 1 2 - 10 Прибыль, ден. ед. 2 5 1 Вариант 2 Продукция Сырье А В С Запасы сырья, ед. I 1 3 1 14 II 3 3 1 28 III - 1 1 4 Прибыль, ден. ед. 4 10 2 Вариант 3 Продукция Сырье А В С Запасы сырья, ед. I 2 1 3 18 II 2 - - 10 III 4 - 3 24 Прибыль, ден. ед. 6 1 9 18 Вариант 4 Продукция Сырье А В С Запасы сырья, ед. I 4 1 3 28 II 2 - 3 14 III 6 1 6 42 Прибыль, ден. ед. 12 2 18 Вариант 5 Продукция Сырье А В С Запасы сырья, ед. I - 1 1 8 II 1 1 - 5 III - 2 1 12 Прибыль, ден. ед. 1 5 2 Вариант 6 Продукция Сырье А В С Запасы сырья, ед. I 1 2 1 13 II 1 3 1 17 III - 3 2 20 Прибыль, ден. ед. 2 10 4 Вариант 7 Продукция Сырье А В С Запасы сырья, ед. I 2 1 - 14 II 1 1 - 8 III - 1 1 3 Прибыль, ден. ед. 3 4 1 Вариант 8 Продукция Сырье А В С Запасы сырья, ед. I 3 2 - 22 II 1 2 1 11 III 2 2 1 17 Прибыль, ден. ед. 6 8 2 Вариант 9 Продукция Сырье А В С Запасы сырья, ед. I - 1 1 7 II 2 1 - 14 III 1 1 - 10 Прибыль, ден. ед. 4 5 1 Вариант 10 Продукция Сырье А В С Запасы сырья, ед. I 2 2 1 21 II 3 2 - 24 III 1 2 1 17 Прибыль, ден. ед. 8 10 2 19 Вариант 11 Продукция Сырье А В С Запасы сырья, ед. I 1 2 - 10 II 2 1 - 8 III 1 - 1 3 Прибыль, ден. ед. 5 2 1 Вариант 12 Продукция Сырье А В С Запасы сырья, ед. I 3 3 - 18 II 3 1 1 11 III 2 2 1 13 Прибыль, ден. ед. 10 4 2 Вариант 13 Продукция Сырье А В С Запасы сырья, ед. I 3 5 - 30 II 1 1 1 8 III - 2 - 8 Прибыль, ден. ед. 3 3 1 Вариант 14 Продукция Сырье А В С Запасы сырья, ед. I 4 6 1 38 II 1 3 1 16 III 3 3 - 22 Прибыль, ден. ед. 6 6 2 Вариант 15 Продукция Сырье А В С Запасы сырья, ед. I 1 1 - 4 II - 2 3 24 III - 4 2 24 Прибыль, ден. ед. 1 5 2 Вариант 16 Продукция Сырье А В С Запасы сырья, ед. I 1 3 3 28 II - 6 5 48 III 1 5 2 28 Прибыль, ден. ед. 2 10 4 Вариант 17 Продукция Сырье А В С Запасы сырья, ед. I 3 - 4 36 II 3 - 2 24 III 1 1 - 6 Прибыль, ден. ед. 7 1 4 20 Вариант 18 Продукция Сырье А В С Запасы сырья, ед. I - - 2 12 II 4 1 2 30 III 4 1 4 42 Прибыль, ден. ед. 14 2 8 Вариант 19 Продукция Сырье А В С Запасы сырья, ед. I 2 - - 8 II 2 3 1 18 III 4 3 - 24 Прибыль, ден. ед. 6 9 1 Вариант 20 Продукция Сырье А В С Запасы сырья, ед. I 3 3 1 22 II 5 3 - 28 III 6 6 1 42 Прибыль, ден. ед. 12 18 2 Вариант 21 Продукция Сырье А В С Запасы сырья, ед. I 2 1 4 20 II - - 1 4 III 3 - 2 18 Прибыль, ден. ед. 3 1 6 Вариант 22 Продукция Сырье А В С Запасы сырья, ед. I 5 1 6 38 II 2 1 5 24 III 3 - 3 22 Прибыль, ден. ед. 6 2 12 Вариант 23 Продукция Сырье А В С Запасы сырья, ед. I - 2 2 16 II 1 1 - 4 III - 1 2 14 Прибыль, ден. ед. 1 3 2 Вариант 24 Продукция Сырье А В С Запасы сырья, ед. I 1 3 2 20 II 1 2 2 18 III - 3 4 30 Прибыль, ден. ед. 3 9 6 21 III. Транспортная задача Общая постановка транспортной задачи состоит в определении оптималь- ного плана перевозок некоторого однородного груза из m пунктов отправления А1, А2, ... , Аm в n пунктов назначения B1, B2, ... , Bn . При этом в качестве критерия оптимальности берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Математическая модель транспортной задачи имеет вид:     m i n j ijijxcZ 1 1 min , (3.1)    m i jij njbx 1 ),...,1( (3.2)    n j iij miax 1 ),...,1( (3.3) ),...,1;,...,1(,0 njmixij  (3.4) Здесь cij – тарифы перевозки единицы груза из i - го пункта отправления Аi в j - ый пункт назначения Bj , bj – потребность в грузе в j - ом пункте на- значения, ai – запасы груза в i - ом пункте отправления. Наличие линейных уравнений (3.2) и (3.3) обеспечивает доставку необхо- димого количества груза в каждый из пунктов назначения и вывоз всего имею- щегося груза из всех пунктов отправления. При этом, ввиду (3.4), исключаются обратные перевозки. Задача (3.1) – (3.4) является частным случаем задачи линейного программирования, однако, в силу своей специфики решается специальным методом. Если выполняется так называемое условие баланса      m i n j ji ba 1 1 , (3.5) 22 то такая транспортная задача называется закрытой. Если условие баланса (3.5) не выполняется, то задача называется открытой. Теорема 1. Для разрешимости транспортной задачи необходимо и доста- точно, чтобы выполнялось условие баланса (3.5). Для решения задачи (3.1) – (3.4) применяется метод потенциалов, который по существу является другой формой симплекс-метода. Замечание. Если условие баланса нарушено, т.е. 1 1 m n i j i j a b     , то вводят фиктивного поставщика 1 1 m n i j i j при a b          или потребителя 1 1 m n i j i j при a b          с поставкой 1 1 1 m n m i j i j a a b      или потребностями     m i i n j jn abb 11 1 соответственно. Стоимости соответствующих перевозок полагаются равными нулю. При построении начального опорного плана в этом случае фиктивные клетки заполняются в последнюю очередь. Опишем алгоритм метода на примере. Пример. Компания контролирует 3 фабрики, производительность кото- рых в неделю (в тыс. изделий) задается вектором (19, 12, 11)a  . Компания заключила договоры с четырьмя заказчиками, еженедельные потребности кото- рых (в тыс.изделий) задаются вектором (9, 10, 8, 11)b  Стоимость транс- портировки 1 тыс. изделий с i-ой фабрики j-му заказчику задается матрицей тарифов 8 5 3 7 2 4 6 3 5 2 3 7 C            . Требуется определить оптимальный план перевозок с целью минимиза- ции суммарных затрат на транспортировку. 23 Р е ш е н и е. 1. Построение математической модели. Обозначим через ( 1,3; 1,4)ijx i j  количество продукта, перевозимого от i-го поставщика j-му потребителю. Тогда общая стоимость перевозок 3 4 11 12 13 14 21 22 23 24 1 1 31 32 33 34 8 5 3 7 2 4 6 3 5 2 3 7 . ij ij i j f c x x x x x x x x x x x x x                  (3.6) Поскольку суммарный объем вывезенных изделий не может превышать их объемов производства, то переменные ( 1,3; 1,4)ijx i j  должны удовлетворять следующим ограничениям: 11 12 13 14 21 22 23 24 31 32 33 34 19, 12, 11. x x x x x x x x x x x x               (3.7) Объем суммарных поставок каждому заказчику должен удовлетворять его потребность, т.е. для переменных ( 1,3; 1,4)ijx i j  выполняются следующие равенства: 11 21 31 12 22 32 13 23 33 14 24 34 9, 10, 8 11. x x x x x x x x x x x x                (3.8) Объем перевозок продукции от любого поставщика любому потребителю не может быть отрицательным числом, поэтому справедливы ограничения: 0, ( 1,3; 1,4)ijx i j   . (3.9) Таким образом, сформулированная выше задача свелась к задаче нахо- ждения таких значений переменных ( 1,3; 1,4)ijx i j  , которые удовлетворяли бы условиям (3.7) – (3.9) и обеспечивали бы минимальное значение целевой функции (3.6). Такая задача (3.6) – (3.9) называется открытой моделью транспортной задачи (ТЗ). 2. Сведение полученной модели к стандартной транспортной задаче. Стандартная ТЗ разрешима только в том случае, если выполняется условие баланса: 3 4 1 1 i j i j a b     . (3.10) 24 В нашей задаче 3 4 1 1 42; 38i j i j a b      , т.е. условие баланса (3.10) нарушено. В связи с этим необходимо привести ТЗ (3.6) – (3.9) к стандартной (закрытой модели), для которой будет выполняться условие баланса (3.10). Поскольку 3 4 1 1 i j i j a b     (42 > 38), введем фиктивного потребителя под номером 5 с объемом потребления 3 4 5 1 1 42 38 4i j i j b a b         (тыс. изд.). Стоимости перевозок от каждого поставщика этому фиктивному потребителю полагаем равными нулю, т.е. 5 0; 1,3ic i  . Получим следующую стандартную ТЗ: 3 4 11 12 13 14 15 21 22 23 24 1 1 25 31 32 33 34 35 8 5 3 7 0 2 4 6 3 0 5 2 3 7 0 min. ij ij i j f c x x x x x x x x x x x x x x x x                      (3.11) 11 12 13 14 15 21 22 23 24 25 31 32 33 34 35 19, 12, 11. x x x x x x x x x x x x x x x                  (3.12) 11 21 31 12 22 32 13 23 33 14 24 34 15 25 35 9, 10, 8, 11, 4. x x x x x x x x x x x x x x x                    (3.13) 0 ( 1,3; 1,5)ijx i j   (3.14) Решение ТЗ (3.11) – (3.14) будет решением исходной открытой задачи (3.6) – (3.9). 3. Решение задачи методом потенциалов. 1. Построение начального до- пустимого опорного плана. Занесем данные задачи (3.11) – (3.13) в табл. 3.1, в которой в верхнем правом углу каждой клетки (i, j), расположенной в i-строке и j-м столбце, помещены соответствующие стоимости ( 1,3; 1,4)ijc i j  и найдем начальный опорный план методом минимальной стоимости (можно построить его и другими методами, например, методом минимального элемента). 25 Таблица 3.1 bj ai 9 10 8 11 4 19 8 5 3 8 7 8 0 3 12 2 9 4 6 3 3 0 11 5 2 10 3 7 0 1 Выпишем начальный опорный план в виде матрицы 0 0 0 8 8 3 9 0 0 3 0 0 10 0 0 1 X            . Стоимость перевозки при этом плане составляет 00 ( ) 3 8 7 8 0 3 2 9 3 3 2 10 0 1 127z z X                (ден. ед.). Так как число занятых клеток в таблице равно 7, 1 3 5 1 7m n      , то этот опорный план является невырожденным. Пустые клетки начального опорного плана в табл. 3.1 соответствуют небазисным переменным ijx . Множество индексов базисных переменных (занятых клеток табл. 3.1)               б 1,1 , 1,2 , 2,2 , 2,3 , 2,4 , 3,4 , 3,5U  образует базисное множество. Тогда множество индексов небазисных переменных (пустых клеток табл. 3.1) образует небазисное множество н б\U U U , где U – множество индексов всех клеток табл. 3.1. 2. Улучшение допустимого опорного плана. Проверим выполнение крите- рия оптимальности для построенного опорного плана. Строке 1 (с наибольшим числом базисных клеток) припишем нулевой потенциал 1 0u  и, используя уравнения   б, ,i j iju v c i j U   , найдем потенциалы всех строк и столбцов для базисных (заполненных) клеток табл. 3.1. Имеем 1 3 2 1 3 23, 2, 2u v u v u v      , 1 4 2 4 3 57, 3, 0u v u v u v      , 1 5 0u v  . 26 Полагая 1 0u  , получаем 3 4 5 3 2 2 13, 7, 0, 0, 2, 4, 6v v v u v u v        . Нулевой потенциал можно выбирать для произвольной строки (столбца). Далее по формулам   н( ), ,ij ij i jc u v i j U     подсчитаем оценки небазисных (пустых) клеток и занесем их в левые нижние углы пустых клеток табл. 3.2. Имеем 11 22 318 (6 0) 2 0, 4 ( 4 2) 6 0, 5 (0 6) 1 0                    , 12 23 335 (2 0) 3 0, 6 ( 4 3) 7 0, 3 (0 3) 0                  , 25 340 ( 4 0) 4 0, 7 (0 7) 0            . Таблица 3.2 bj ai 9 10 8 11 4 iu 19 8 2 5 3 3 8 – ┌ ─ 7 ا 8 ا + ┐0 ا 3 ا 1 0u  12 – ┌ ─ 2 ا 9 ا ─ ─ 4 6 ─ ─ 6 7 + ┘ 3 3 ا 0 ا 4 ا 2 4u   11 + └ ─ 5 -1 ─ ─ 2 10 ─ ─ 3 0 ─ ─ 7 0 – ┘ 0 1 3 0u  jv 1v = 6 2v = 2 3v = 3 4v = 7 5v = 0 Анализ оценок   н, ,ij i j U  показывает, что данный опорный план неоптимален, т.к. среди оценок ij есть отрицательные. Поэтому переходим к итерации построения нового плана, лучшего в том смысле, что значение целевой функции (3.6) будет на нем меньше, чем на начальном. Найдем такую клетку в табл. 3.2, в которой находится минимальное отрицательное значение оценки   н, ,ij i j U  . Это будет клетка (3, 1). Следовательно, переменная 31x будет вводиться в базис. С помощью этой клетки и базисных клеток построим цикл              { 3,1 , 2,1 , 2,4 , 1,4 , 1,5 , 3,5 , 3,3 } , считая первым звеном цикла, например, вертикальное звено из клетки (3, 1). В табл. 3.2 цикл изображен пунктирами. Помечаем клетки цикла поочередно знаками « + »,« – », причем клетка (3, 1), вводимая в базис, помечается знаком « + ». Среди клеток, помеченных знаком « – », выбираем ту, в которой значение ijx минимально. В 27 нашем случае это клетка (3, 5), где 35 1.x  Обозначим 35 1.x   Число  = 1 добавим к перевозкам в клетках, помеченных знаком « + », и вычтем из величин ijx в клетках, помеченных знаком « – ». Объемы ijx остальных перевозок не изменяем. Клетка (3, 5) удаляется из базисного множества, а клетка (3, 1) вводится в базисное множество. В результате получим новый опорный план (табл. 3.3). Таблица 3.3 bj ai 9 10 8 11 4 iu 19 8 2 5 2 3 8 7 7 0 4 1 0u  12 2 8 4 5 6 7 3 4 0 4 2 4u   11 5 1 2 10 3 1 7 1 0 1 3 1u   jv 1v = 6 2v = 3 3v = 3 4v = 7 5v = 0 Новый опорный план имеет вид: 1 0 0 8 7 4 8 0 0 4 0 1 10 0 0 0 X            . Общая стоимость перевозок 11 ( ) 3 8 7 7 0 4 2 8 3 4 5 1 2 10 126z z X                (ден. ед.). Проверим полученное решение на оптимальность. Для этого найдем потенциалы занятых и оценки свободных клеток по ранее указанному правилу. Поскольку среди оценок нет отрицательных, то найденный план является оптимальным. Выписываем матрицу Х* (без последнего столбца): 28 0 0 8 7 8 0 0 4 1 10 0 0 X             . Минимальные суммарные затраты по оптимальному плану составляют min 126z  (ден. ед.). Из таблицы 3.3 видно, что избыточная продукция в количестве 4 тыс. изделий остается на первой фабрике. Контрольные задания для самостоятельного решения Задание 3 Постановка задачи. Компания контролирует 4 фабрики, производительность которых на неделю (в тыс. изделий) задается вектором a = =(а1, а2 , а3 , а4 ). Компания заключила договоры с пятью заказчиками, потребность которых еженедельно (в тыс.изделий) задается вектором b = (b1 , b2 , b3 , b4 , b5). Стоимость транспортировки 1 тысячи изделий j - му заказчику с i -ой фабрики-изготовителя задается матрицей 4 5ij C C   . Требуется: 1) составить математическую модель задачи; 2) привести ее к стандартной задаче ( с балансом); 3) построить начальный опорный план; 4) решить задачу методом потенциалов; 5) проанализировать результаты решения. Вариант a  b С 1 (50,25,25,15) (15,20,15,20,30) 3 9 2 1 6 6 2 4 1 7 1 4 8 3 2 1 4 6 2 4              2 (25,20,15,12) (20,15,20,15,10) 3 5 1 4 2 5 3 2 1 4 6 3 1 4 2 1 3 5 7 4              29 3 (12,14,13,9) (8,10,10,7,7) 2 6 5 1 4 3 6 4 5 6 6 7 4 5 6 6 8 7 2 5              4 (24,18,114,10) (18,15,18,13,8) 4 6 2 5 3 5 3 2 1 4 7 4 2 5 3 1 3 5 7 4              5 (20,13,6,9) (8,11,7,5,12) 5 2 1 5 3 8 7 8 1 2 6 5 4 3 2 3 6 1 5 4              6 (20,14,10,6) (14,11,14,9,4) 5 7 3 6 4 6 4 3 2 5 9 6 4 7 7 2 4 6 8 5              7 (12,14,8,10) (9,11,7,6,9) 4 3 2 1 4 6 3 6 2 4 1 5 3 4 6 4 1 3 5 2              8 (21,15,11,7) (15,12,15,10,5) 6 8 4 7 5 5 3 2 1 4 8 5 3 6 4 1 3 5 7 4              9 (16,11,12,13) (10,9,8,15,7) 4 3 2 1 4 7 3 6 2 4 1 4 2 4 6 4 1 3 5 2              10 (31,25,21,17) (25,22,25,20,15) 7 9 5 8 6 8 6 5 4 7 6 3 1 4 2 3 5 7 9 6              11 (11,13,12,8) (8,9,9,6,5) 3 6 4 5 6 2 6 5 1 4 6 7 4 5 6 6 8 7 2 5              30 12 (29,23,19,15) (23,20,23,18,13) 8 10 6 9 7 7 5 4 3 6 10 7 5 8 6 4 6 8 10 7              13 (19,12,5,8) (7,10,7,5,11) 5 2 1 5 3 8 7 8 1 2 6 5 4 3 2 3 6 1 5 4              14 (26,20,16,12) (20,17,20,15,10) 6 8 4 7 5 5 3 2 1 5 9 6 4 7 5 5 7 9 11 8              15 (15,10,11,12) (9,8,7,14,7) 4 3 2 1 4 7 3 6 2 4 1 4 2 4 6 4 1 3 5 2              16 (15,17,20,18) (20,10,15,20,10) 9 8 6 5 4 6 2 5 7 4 7 4 8 6 4 4 6 3 2 1              17 (30, 25, 20, 15) (10, 20, 18, 12, 25) 2 6 1 4 5 5 1 3 2 6 1 3 6 3 2 1 4 6 2 4              18 (17, 19, 22, 20) (22, 12, 17, 22, 12) 8 7 5 4 3 8 4 7 9 6 8 5 9 7 5 5 7 4 3 2              19 (10, 12, 11, 7) (8, 9, 9, 6, 5) 3 9 2 1 6 6 2 4 1 7 1 4 8 3 2 1 4 6 2 4              20 (16, 81,21,19) (21, 11, 16, 21, 11) 7 6 4 3 2 7 3 6 8 5 5 2 6 4 2 4 6 3 2 1              31 21 (18, 10, 6, 9) (7, 10, 6, 5, 10) 5 4 1 5 3 8 7 8 1 2 6 5 4 3 2 3 6 1 5 4              22 (14, 16, 19, 17) (19, 9, 14, 19, 9) 6 5 3 2 1 5 1 4 6 3 6 3 7 5 3 6 8 5 4 3              23 (35, 25, 20, 15) (15, 20, 10, 20, 20) 2 6 1 4 5 5 1 3 2 6 1 3 6 3 2 1 4 6 2 4              24 (13, 15, 18, 16) (18, 8, 13, 18, 8) 9 8 6 5 4 7 3 6 8 5 8 5 9 7 5 7 9 6 5 4              IV. Задача о максимальном потоке в сети Рассмотрим сеть G(V, U), где V множество вершин, а U множество дуг их соединяющих, (i, j)  U поставлено в соответствие неотрицательное число dij (dij  0), называемое пропускной способностью этой дуги (если дуга (i, j) – неориентированная, то полагаем dij = dji). Выделим в сети две вершины. Одну из них назовем источником и обозначим s, а другую – стоком и обозначим t . Каждой дуге (i, j) сети поставим в соответствие неотрицательное число xij , которое назовем потоком на дуге (i, j). Потоком из источника s в сток t в сети G (V,U) называется множество неотрицательных чисел  ijx , удовлетво- ряющих ограничениям: vxx j sj i is  , (4.1) vxx j tj i it  , (4.2)    i j kjik tskxx ,,0 (4.3) 32 Ujidxv ijij  ),(,0,0 (4.4) Неотрицательная величина v называется величиной потока в сети. Огра- ничения (4.1), (4.2) означают, что суммарная величина v потока, выходящего из источника s, равна суммарной величине v потока, входящего в сток t. Огра- ничения (4.3) выражают тот факт, что в каждую вершину (кроме источника и стока) приходит столько потока, сколько из нее уходит. Если для дуги (i, j) имеем xij = dij, то дуга (i, j) называется насыщенной потоком. Итак, задача нахождения максимального потока является задачей линейного программирования с целевой функцией   i is k sk xxv и ограничениями (4.1) – (4.4). В силу своей специфики для ее решения существует более эффективный алгоритм, чем симплекс-метод. Разобьем множество вершин V сети G(V,U) на два непересекающихся подмножества R и R ( )R R и R R V    . Разрезом ),( RR сети G(V,U) называется множество всех дуг (i, j), таких, что либо i  R, j R , либо j R , i R . Т.е. разрез – это множество всех дуг, концевые вершины которых при- надлежат разным множествам: R и R . При этом положим s R, t R . Тогда мы получим разрез, отделяющий источник s от стока t. Если удалить все дуги некоторого разреза, отделяющего источник s от стока t, то на сети не останется пути ведущего из s в t. Пропускной способностью разреза (R, R ) называется величина    RjRi ijdRRС , ),( , Разрез, отделяющий источник от стока и обладающий минимальной пропускной способностью, называется минимальным разрезом. 33 Теорема (о максимальном потоке и минимальном разрезе). В любой сети величина максимального потока из источника s в сток t равна пропускной способности минимального разреза. Пусть на сети имеется некоторый поток, который не является максимальным. Алгоритм решения задачи объясним на примере. Пример. На рис. 4.1 изображена сеть. Первое число указывает пропускную способность дуги, второе – дуговой поток. 1 9,0 t 7,4 4,4 5,0 7,4 3 s 8,0 2 7,4 Рис. 4.1 Применим алгоритм Форда-Фалкерсона для построения максимального потока и нахождения минимального разреза. 1. Найдем увеличивающий путь методом расстановки меток. 1.1. В сети имеется допустимый поток 0 4 0 0 4is sj i s v x x       . Источник s получает пометку s+ (см. рис. 4.2). 1.2. Просматриваем все непомеченные вершины, соседние с s. Это вершины 1 и 2. Присваиваем вершине 1 метку s+, так как (s, 1) – прямая дуга и 1 1(4 7)s sx d  . Вершине 2 также присваиваем метку s +, поскольку (s, 2) – прямая дуга и 2 2(0 8)s sx d  . 1.3. Теперь просматриваем все непомеченные вершины, соседние с вершиной 1. Это вершины 3 и t. Присваиваем вершине t метку 1+, так как (1, t) – прямая дуга и 1 1 (0 9)t tx d  . Поскольку вершина t – это сток, то на данном этапе вершину 3 можно не рассматривать. Исходная сеть примет вид (рис. 4.2). 34 s + 1 + 1 9,0 t 7,4 4,4 5,0 7,4 s + 3 s 8,0 2 7,4 s + Рис. 4.2 2. Так как сток оказался помеченным, то выписываем увеличивающий путь P1 , двигаясь от стока t к вершине 1, номер которой указан в ее метке, затем от вершины 1 к вершине s, номер которой указан в метке. Таким образом, приходим к источнику s. 1 : 1P s t  . 3. Выписываем множество P+ (прямых дуг) и множество P- (обратных дуг):  ( , 1), (1, ) ,P s t P   (пустое множество), поскольку обратные дуги в увеличивающий путь P1 не входят. 4. Для прямых дуг вычисляем величину    1 1 1 1 1 ( , ) min ( ) min ; min 7 4; 9 0 3ij ij s s t t i j P d x d x d x           . Так как обратных дуг нет, то величину 2 не рассматриваем. 5. Вдоль дуг увеличивающего пути P1 (рис. 4.3) изменяем поток 0 4v  на величину 1 3   и получаем : 1 1 4 3 7s sx x       , 1 1 0 3 3t tx x       . Получаем новый поток 1 0 4 3 7v v      . 35 2 - 1 + 1 9,3 t 7,7 4,4 5,0 7,4 s + 3 s 8,0 2 7,4 2 + s + Рис. 4.3 Опять применим алгоритм Форда-Фалкерсона для построения максимального потока и нахождения минимального разреза. 1. Найдем увеличивающий путь методом расстановки меток. 1.1. Источник s получает пометку s+. 1.2. Просматриваем все непомеченные вершины, соседние с s. Это вершины 1 и 2. Вершине 1 нельзя присвоить метку s+, так как (s, 1) – прямая дуга, но 1 1(7 7)s sx d  . Т.е. дуга (s, 1) является насыщенной. Вершине 2 присваиваем метку s+, поскольку (s, 2) – прямая дуга и 2 2(0 8)s sx d  . 1.3. Просматриваем все непомеченные вершины, соседние с вершиной 2. Это вершины 1 и 3. Вершина 1 получает метку 2–, так как (2, 1) – обратная дуга и 21 4 0x   . Присваиваем вершине 3 метку 2 +, поскольку (2, 3) – прямая дуга и 23 23(4 7)x d  . 1.4. Теперь просматриваем все непомеченные вершины, соседние с вершиной 1. Это вершина t. Присваиваем вершине t метку 1+, так как (1, t) – прямая дуга и 1 1 (3 9)t tx d  . Все метки нанесены на сеть (рис. 4.3). 2. Так как сток оказался помеченным, то выписываем увеличивающий путь P2 , двигаясь от вершины t к вершине 1, номер которой указан в ее метке, затем от вершины 1 к вершине 2, номер которой указан в ее метке, и т.д. пока не придем к источнику s. 2 : 2 1P s t   . 36 3. Выписываем множество P+ (прямых дуг) и множество P- (обратных дуг):    ( , 2), (1, ) , (2, 1))P s t P   . 4. Вычисляем    1 2 2 1 1 ( , ) min ( ) min ; min 8 0; 9 3 6ij ij s s t t i j P d x d x d x           – для прямых дуг, 2 21 ( , ) min 4ij i j P x x     – для обратных дуг. Находим 1 2min( , ) min(6; 4) 4     . 5. Вдоль дуг увеличивающего пути P2 (рис. 4.4) изменяем поток 1 7v  на величину 4  и получаем новый поток 2 1 7 4 11v v      , такой что: 2 2 0 4 4, ( , 2)s sx x s P        ; 1 1 3 4 7, (1, )t tx x t P        ; 12 12 4 4 0, (2, 1)x x P        . Остальные ijx остаются без изменений, так как не входят в увеличивающий путь P2 . 3 + 1 9,7 t 7,7 4,0 5,0 7,4 s + 3 s 8,4 2 7,4 2 + s + Рис. 4.4 Рассуждая, как было написано выше, расставляем метки (см. рис. 4.4) и выписываем третий увеличивающий путь: 3 : 2 3P s t   . Выписываем множество P+ (прямых дуг) и множество P- (обратных дуг):  ( , 2),(2,3), (3, ) ,P s t P   . 37 Вычисляем:    1 2 2 23 23 3 3 ( , ) min ( ) min ; ; min 8 4; 7 4; 7 4 3.ij ij s s t t i j P d x d x d x d x             Так как P  , то 2 не вычисляем. Следовательно 3  . Вдоль дуг увеличивающего пути P3 ( рис. 4.5) изменяем поток 2 11v  на величину 3  , полагая 3 2 11 3 14v v      получаем новый поток, такой что: 2 2 4 3 7, ( , 2)s sx x s P        ; 23 23 4 3 7, (2, 3)x x P        ; 3 3 4 3 7, (3, )t tx x t P        . 1 9,7 t 7,7 4,0 5,0 7,7 s + 3 s 8,7 2 7,7 2 + s + Рис. 4.5 1. Снова находим увеличивающий путь методом расстановки меток. 1.1. Источник s получает пометку s+. 1.2. Просматриваем все непомеченные вершины, соседние с s. Это вершины 1 и 2. Вершине 1 нельзя присвоить метку, так как (s, 1) – прямая насыщенная дуга 1 1( )s sx d . Вершине 2 присваиваем метку s +, так как (s, 2) – прямая дуга и 2 2(7 8)s sx d  . 1.3. Теперь просматриваем все непомеченные вершины, соседние с вершиной 2. Это вершины 1 и 3. Вершине 1 нельзя присвоить метку 2–, так как дуга (2, 1) – обратная, но 21 0x  . Вершина 3 не может быть помечена, поскольку (2, 3) – прямая насыщенная дуга 23 23( )x d . 38 2. Так как мы не можем пометить сток t, то увеличивающего пути нет и поток в сети является максимальным: max 14v  . Построим минимальный разрез. Пусть R – множество помеченных вершин в сети, т.е.  , 2R s , а R – множество непомеченных вершин, т.е.  1, 3,R t . Тогда по определению минимальный разрез ( , )R R состоит из дуг  ( , ) ( ,1); (2,3)R R s (дуга (1, 2) в разрез не входит, так как ее начало – непомеченная вершина, а конец – помеченная). На рис. 4.6 насыщенные дуги отмечены жирной линией, минимальный разрез, отделяющий источник s от стока t, показан пунктирной линией. 1 9,7 t 7,7 4,0 5,0 7,7 3 s 8,7 2 7,7 Рис. 4.6 Найдем пропускную способность минимального разреза: 1 23( , ) 7 7 14sC R R d d     , что совпадает с величиной максимального потока в сети. Проведем анализ сети. Проверим условие сохранения потока на примере 2-й вершины. Известно, что в промежуточных вершинах пути потоки не создаются и не исчезают, т.е. 2 2 0i j i j x x   . Действительно: 2 12 23( ) (7 0) 7 0sx x x      . Покажем, что общее количество потока, вытекающего из источника s, совпадает с общим количеством потока, втекающего в сток. Имеем: 39 1 2 4 5 6 3 is sj it tj i j i j x x x x      1 2 1 30 0 7 7 7 7 14s s t tx x x x          . Контрольные задания для самостоятельного решения Задание 4 На сети указанные пропускные способности дуг и начальный поток. Требуется: 1) Найти максимальный поток из источника s в сток t; 2) Построить минимальный разрез; 3) Провести анализ полученной сети. Вариант 1 Вариант 2 4 4 8 5 s 10 4 t 5 12 11 Вариант 3 4 5 2 3 6 7 1 4,2 2,1 4,0 10,5 5,2 8,3 4,3 7,2 2,1 7,0 t s s S 3 4 1 2 5 6 5,3 7,3 6,3 9,1 7,1 8,4 4,2 8,2 t 40 1 2 4 5 3 6 1 3 2 5 4 6 Вариант 4 5 11 s 12 8 4 13 5 7 6 t Вариант 5 Вариант 6 s 13 5 18 12 15 10 20 10 15 t Вариант 7 t s 4 5 2 3 6 7 1 5,1 5,3 8,4 4,1 9,3 6,2 3,2 7,1 2,0 3,1 s 4 5 2 3 6 1 3,3 2,2 11,4 8,2 8,1 10,3 5,1 4,0 3,2 t 41 1 3 4 2 5 6 7 1 2 3 4 5 6 Вариант 8 15 12 20 7 8 s 8 t 13 11 18 10 4 Вариант 9 Вариант 10 s 11 23 15 5 6 12 t 8 4 18 10 Вариант 11 4 5 2 3 6 7 1 6,0 4,1 7,0 8,3 4,2 9,1 3,3 3,2 6,1 2,2 t s t s 4 5 2 3 6 7 1 4,2 3,2 5,1 9,2 6,2 5,2 3,0 2,1 4,3 7,2 42 1 2 5 4 7 3 6 1 2 4 3 5 6 7 Вариант 12 11 20 8 12 15 s 13 17 t 22 15 8 22 16 Вариант 13 Вариант 14 s 15 5 16 11 14 12 18 t 17 8 13 Вариант 15 2,2 3 4 1 2 5 6 s t 6,2 9,4 2,1 8,5 6,3 9,1 9,7 3,2 t s 4 5 2 3 6 7 1 9,3 7,1 6,4 8,2 7,5 8,1 6,2 5,2 2,1 43 1 2 3 4 5 6 7 1 3 5 7 2 4 6 Вариант 16 15 12 11 13 15 s 15 12 t 7 18 14 18 7 Вариант 17 Вариант 18 s 12 12 15 14 11 11 15 13 t 16 16 12 Вариант 19 t s 4 5 2 3 6 7 1 6,4 4,3 7,3 8,4 7,1 5,3 4,3 5,0 6,2 8,5 t s 4 5 2 3 6 1 6,2 6,6 14,5 12,4 6,3 3,1 9,2 5,2 4,0 44 1 2 4 3 5 7 6 1 2 5 3 4 6 7 Вариант 20 s 14 12 t 11 18 12 13 14 8 5 16 15 17 10 Вариант 21 Вариант 22 10 15 s 15 10 12 10 t 8 10 18 12 7 14 13 Вариант 23 4 5 2 3 6 7 1 5,0 5,1 4,0 9,3 4,2 8,1 3,3 3,2 5,1 2,2 t s s t 4,2 6,2 5,2 5,1 8,1 5,5 3,1 9,4 3 4 1 2 5 6 2,0 45 1 4 2 3 7 6 5 Вариант 24 s 10 8 15 14 12 12 12 18 13 14 20 t 16 V. Сетевое планирование Основой методов сетевого планирования является сетевая модель (сете- вой график), отражающая логическую взаимосвязь работ, входящий в некото- рый комплекс, что позволяет осуществлять управление ходом выполнения этих работ. Для построения сетевой модели необходимо, прежде всего, разбить весь комплекс на отдельные работы или операции и составить очередность выпол- нения этих работ. Для этого составляется список работ, которые непосредст- венно предшествуют каждой работе, а так же планируется время, необходимое для их выполнения. Полученные данные удобно заносить в таблицу. В таблице 5.1 приведены данные для проекта, состоящего из девяти работ. Таблица 5.1 № работы 1 2 3 4 5 6 7 8 9 Предшествующие работы - - 1 1, 2 1, 2 3, 4 3, 4 6 7, 5 Продолжительность работы 10 15 5 20 15 6 8 10 15 На основании данных, приведенных в таблице, строится график комплек- са работ, входящих в проект. Каждая работа изображается в виде ориентиро- ванного отрезка (дуги). Связи между работами изображаются пунктирными линиями (дуги-связи). В результате получается сетевой график (начальная вершина дуги – начало, а конечная – завершение соответствующей работы): 46 3 1 6 8 4 2 7 9 5 Рис. 5.1 Предварительно следует упростить полученную сеть. Можно удалить некоторые дуги-связи, а начало и конец удаляемой дуги объединить в одну вер- шину. На рис. 5.2 изображена сеть, полученная после упрощения сети, изобра- женной на рис. 5.1. 3 6 1 8 2 4 7 9 5 Рис. 5.2 В сетевом графике каждая вершина является конечной для некоторых дуг(операций), входящих в нее или начальной для дуг (операций) из нее выхо- дящих. Поэтому каждая вершина может трактоваться как событие, означающее завершение всех операций (дуг), для которых она является конечной и как возможность начала выполнения всех операций (дуг), для которых она является начальной. Начальной вершине соответствует событие, под которым подразумевается начало осуществления проекта, а конечной вершине соответствует событие – завершение выполнения всего комплекса работ. После построения сетевого графика все его вершины нумеруются так, что нумерация является правильной. 47 Алгоритм правильной нумерации. Шаг 1. Нумеруем начальную вершину номером 1. Переходим к шагу 2. Шаг 2. Удаляем из сети все выходящие из пронумерованных вершин дуги. Нумеруем в произвольном порядке вершины, в которые не входит ни одна дуга, произвольным образом возрастающими по порядку номерами. Шаг 2 проделываем до тех пор, пока не дойдем до конечной вершины, которой при- сваиваем следующий по порядку номер. В результате правильной нумерации вершин сетевой график, приведен- ный на рис. 5.3 примет вид 5 6 2 4 6 10 0 8 10 1 20 7 15 15 3 15 5 Рис. 5.3 Номера работ на дугах соответственно заменены продолжительностью их выполнения (продолжительность фиктивной работы соответствующей дуги- связи полагаем равной 0). Рассмотрим основные временные параметры сетевого графика. Пусть tij – продолжительность работы, для которой соответствующая дуга (i, j) в сетевом графике имеет в качестве начальной – вершину с номером i , а в качестве конечной – вершину с номером j. Ранним сроком начала работы (i, j) называется наименьшее допустимое время tijPH , когда может быть начато ее выполнение. Если работа начата в ранний срок, то время ее окончания tijP0 называется ранним сроком окончания 48 tij PН = tij PО-tij Ранний срок начала всех работ, для которых вершина i – начальная, называется ранним сроком наступления события i и обозначается TiP. Ранний срок наступления конечного события называется критическим временем и обозначается Ткр. Таким образом, критическое время – это минимальный срок, за который может быть выполнен весь комплекс работ. Каждый путь из начальной вершины в конечную, состоящий из дуг (работ) и дуг-связей продолжительностью Ткр, называется критическим путем, а работы, составляющие такие пути – критическими работами. Поздними сроками начала и окончания работы (i, j) называется наиболь- шее допустимое время начала (tijПН) и окончания (tijПO) этой работы без нарушения сроков выполнения всего комплекса работ. Очевидно: tij ПН = tij ПО-tij. Наиболее поздний из поздних сроков окончания работ, входящих в вершину j, называется поздним сроком наступления события j и обозначается ТjП. Рассмотрим работу (i, j). Плановая продолжительность этой работы равна tij. Максимально допустимое время, на которое можно увеличить продолжительность работы (i, j) или задержать начало ее выполнения, при котором не изменится время выполнения всего проекта, называется полным резервом Rij времени этой работы. Он равен: Rij = Tj П - Ti P – tij. Резерв времени для работы (i, j), использование которого не изменит ранние сроки наступления всех событий (т.е. все работы смогут начать выполняться в минимально возможные сроки), называется свободным и может быть вычислен по формуле rij = Tj P - Ti P – tij. Очевидно, полный и свободный резерв времени любой работы, лежащей на критическом пути, равен нулю. 49 Алгоритм нахождения ранних сроков наступления событий 1. Полагаем T1P = 0. 2. Для j = 2, 3, . . . , n вычисляем TjP = )(),( max jIjk  (Tk P + tkj) Здесь I(j) – множество всех дуг, входящих в вершину j. Критическое время Тkp = TnP. Алгоритм нахождения поздних сроков наступления событий 1. Полагаем ТnП = Т (как правило Т = Тkp.). 2. Для i = n-1, n-2, . . . 1, вычисляем TПi = )(min )(0 ij П j ij tT   . Здесь 0(i) – множество вершин, которые являются конечным для дуг, выходящих из вершины i. Рассмотрим сетевой график, описанный в таблице 5.1. События (вершины) сетевого графика изображены следующим образом: В верхней четверти записан номер события (вершины) в соответствии с правильной нумерацией. Номер вершины ki , при движении из которой получено значение TiP , заносится в нижнюю четверть. В левой четверти записывается ранний срок наступления события TiP, а в правой четверти – его поздний срок наступления TiП . Найдем ранние сроки наступления каждого события для сетевого графика, изображенного на рис. 5.3. Полагаем T1P = 0, k1 = 0. Рассматриваем вершины в порядке возрастания их номеров. T2 P = T1 P + t12 = 0 + 10 = 10, k2 = 1; T3 P = max (T1 P + t13; T2 P + t23) = max (0 + 15; 10 + 0) = T1 P + t13 = 15, k3 = 1; T4 P = max (T2 P + t24; T3 P + t34) = max (10 + 5; 15 + 20) = T3 P + t34 = 35, k4=3; Ti p Ti П кi i 50 T5 P = max (T3 P + t35, T4 P + t45) = max (15 + 15; 35 + 8) = T4 P + t45 = 43, k5=4; T6 P = T4 P+ t46 = 35 + 6 = 41, k6 = 4; TkP = max (T5 P + t57; T6 P + t67) = max (43 + 15; 41 + 10) = T5 P + t57 = 58, k7=5. Построим критический путь, начиная с конечной вершины, двигаясь по номерам вершин ki,, стоящих в нижней четверти. В результате получим 1 – 3 – 4 – 5 – 7. Найдем поздние сроки наступле- ния событий. Полагаем время окончания всего проекта T = T7П = Tkp. = 58. Поставим это значение в правую четверть конечной вершины 7. T6 П = T7 П – t67 = 58 – 10 = 48; T5 П = T7 П – t57 = 58 – 15 = 43; П4П = min (T6П – t46; T5П – t45) = min (48 - 6; 43 - 8) = 35; T3 П = min (T5 П - t35; T4 П - t34) = min (43 - 15; 35 - 20) = 15; T2 П = min (T4 П - t24; T3 П – t23) = min (35 - 5; 15 - 0) = 15; T1 П = min (TП 3 - t13; T2 П – t1П ) = (15 – 15; 15 – 10) = 0. В результате получаем следующую сетевую модель, содержащую под- робную информацию о ранних, поздних сроках наступления событий, крити- ческом времени и критическом пути. Критический путь отмечен двойными линиями. 2 5 4 6 6 10 15 35 35 41 48 1 3 4 10 10 0 20 8 7 1 58 58 0 0 5 0 15 15 3 5 15 15 43 43 1 15 4 Рис. 5.4 51 Контрольные задания для самостоятельного решения Задание 5 Информация о строительстве комплекса задана нумерацией работ, их продолжительностью (в ед. времени), последовательностью выполнения и оформлена в виде таблицы. За какое минимальное время может быть завершен весь комплекс работ. Требуется: 1) по данным таблицы построить сетевой график комплекса работ и найти правильную нумерацию его вершин; 2) рассчитать на сетевом графике ранние и поздние сроки наступления событий, а также резервы времени событий; 3) выделить на сетевом графике критические пути; 4) для некритических работ найти полные и свободные резервы времени; 5) выполнить анализ сетевого графика. № ра- бот № ва- риан- та 1 2 3 4 5 6 7 8 9 1 Каким работам предшествует 2,4, 5 3,9 - 8 6 7 - - 8 Продолжитель- ности работ 12 15 12 12 14 18 17 12 15 2 Каким работам предшествует 6 4,5 7,8 7,8 6 9 6 9 - Продолжитель- ности работ 20 12 18 14 16 17 17 12 10 3 Каким работам предшествует 7 4,5, 8 6 6 7 9 9 9 - Продолжитель- ности работ 12 13 21 11 13 14 17 12 22 4 Каким работам предшествует 4 6 7,8 5 - 9 5 9 - Продолжитель- ности работ 10 13 18 17 14 17 10 15 13 5 Каким работам предшествует 2,3, 4 6,8 7 5 9 7 - - - Продолжитель- ности работ 17 17 18 10 13 12 14 15 16 6 Каким работам предшествует 7 4,5, 8 6 6 7 9 9 9 - Продолжитель- ности работ 10 11 13 17 12 14 14 18 17 7 Каким работам прешествует 2,9 3 - 5,8 3 7 3 7 - Продолжитель- ности работ 12 12 13 14 10 11 18 16 17 52 № ра- бот № ва- риан- та 1 2 3 4 5 6 7 8 9 8 Каким работам предшествует 2 3 - 5,9 3 - 8, 9 5 - Продолжитель- ности работ 12 10 18 15 12 14 18 14 13 9 Каким работам предшествует 7 6,8 4,5 6,8 7 7 9 9 - Продолжитель- ности работ 13 14 12 19 14 15 12 13 12 10 Каким работам предшествует 2 3 - 5,6 3 - 8, 9 5 6 Продолжитель- ности работ 15 5 5 30 50 30 10 20 10 11 Каким работам предшествует 4,5, 6 3,7 5,6 8 8 9 9 - - Продолжитель- ности работ 12 11 13 15 14 30 20 10 20 12 Каким работам предшествует 2 3 - 6,9 6,7, 9 8 8 - 3 Продолжитель- ности работ 16 17 13 14 10 14 30 20 19 13 Каким работам предшествует 4 8,7 5,6 9 8,7 7 - 9 - Продолжитель- ности работ 13 17 14 30 30 20 20 18 13 14 Каким работам предшествует 2,3 8 6,7 6,7 9 8 - - - Продолжитель- ности работ 10 12 10 13 40 17 20 12 15 15 Каким работам предшествует 2,7 5,6 5,6 8 8 9 9 - - Продолжитель- ности работ 14 16 14 12 10 24 10 30 15 16 Каким работам предшествует 6,7 5 4 9 9 5 8 - - Продолжитель- ности работ 20 20 18 10 10 18 15 13 12 17 Каким работам прешествует 8,6 4,5 7 6,8 7 7 9 9 - Продолжитель- ности работ 14 13 17 10 17 16 15 20 13 18 Каким работам предшествует 7 6,8 4,5 6,8 7 7 9 9 - Продолжитель- ности работ 20 11 14 15 10 20 20 30 14 19 Каким работам предшествует 5 6,7 4,8 6,7 9 8, 9 7, 9 9 - Продолжитель- ности работ 20 16 14 10 17 14 30 14 20 53 № ра- бот № ва- риан- та 1 2 3 4 5 6 7 8 9 20 Каким работам предшествует 2,6 5 5 7 8 7 9 - - Продолжитель- ности работ 15 30 20 10 20 20 15 15 30 21 Каким работам предшествует 4 8,7 5,6 9 8,7 9, 7 9 - - Продолжитель- ности работ 30 17 14 30 13 20 15 18 30 22 Каким работам предшествует 4 5,7 6 8 4 8, 9 9 - - Продолжитель- ности работ 10 20 30 20 13 14 18 10 30 23 Каким работам предшествует 4,5, 6 4,5, 6 5,6 8 8 7 8 - - Продолжитель- ности работ 17 30 10 17 30 20 12 14 18 24 Каким работам предшествует 6 4,5 8 7,8 6 9 8 9 - Продолжитель- ности работ 18 17 17 15 13 40 30 20 30 54 ЛИТЕРАТУРА 1. Кузнецов, А.В. Математическое программирование / А.В. Кузнецов, Н.И. Холод. – Минск : Вышэйшая школа, 1984. 2. Балашевич, В.А. Математические методы в управление производством / В.А/ Балашевич. – Минск : Вышэйшая школа, 1976. 3. Банди, Б. Основы линейного программирования / Б. Банди. – М. : Радио и связь, 1988. 4. Банди, Б. Методы оптимизации. Вводный курс / Б. Банди. – М. : Радио и связь, 1989. 5. Калихман, И.Л. Сборник задач по математическому программированию / И.Л. Калихман. – М. : Высшая школа, 1975. 6. Сборник задач и методические указания к решению задач по мате- матическому программированию / Е.В. Емеличева [и др.]. – Минск : ротапринт БГПА, 1996. 7. Математические методы в технико-экономических задачах / Н.Е. Гай- ков [и др.]. – Минск : ротапринт БПИ, 1991. 55 СОДЕРЖАНИЕ I. Решение задачи линейного программирования симплекс-методом .......... 3 Контрольные задания для самостоятельного решения. ................................... 9 II. Двойственность в линейном программировании. ...................................... 11 Экономический смысл двойственных переменных ......................................... 11 Контрольные задания для самостоятельного решения. ................................. 17 III. Транспортная задача ....................................................................................... 21 Контрольные задания для самостоятельного решения .................................. 28 IV. Задача о максимальном потоке в сети ......................................................... 31 Контрольные задания для самостоятельного решения .................................. 39 V. Сетевое планирование ....................................................................................... 45 Контрольные задания для самостоятельного решения .................................. 51 ЛИТЕРАТУРА ......................................................................................................... 54 СОДЕРЖАНИЕ ....................................................................................................... 55 56 Учебное издание МЕТОДЫ ЛИНЕЙНОЙ И СЕТЕВОЙ ОПТИМИЗАЦИИ Методические указания и контрольные задания для студентов заочной формы обучения С о с т а в и т е л и : КОРЗНИКОВ Александр Дмитриевич МАТВЕЕВА Людмила Дмитриевна Подписано в печать 01.11.2012. Формат 6084 1/8. Бумага офсетная. Ризография. Усл. печ. л. 6,51. Уч.-изд. л. 2,54. Тираж 200. Заказ 846. Издатель и полиграфическое исполнение: Белорусский национальный технический университет. ЛИ № 02330/0494349 от 16.03.2009. Пр. Независимости, 65. 220013, г. Минск.