Министерство образования Республики Беларусь « щшш ШУШ БЕЛОРУССКИЙ НАЦИОНАЛЬНЫЙ ^ S i l r ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра высшей математики № 2 ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ Методические указания и контрольные задания для студентов экономических специальностей БИТУ Минск 2006 Министерство образования Республики Беларусь БЕЛОРУССКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра высшей математики №2 ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ Методические указания и контрольные задания для студентов экономических специальностей БНТУ П о д р е д а к ц и е й А.Д. КОРЗНИКОВА М и н с к 2 0 0 6 УДК 519.85 (075.8) Э 45 С о с т а в и т е л и : А.Д. Корзников, Л.Д. Матвеева, М.Б. Смирнов Р е ц е н з е н т ы : В.Ф. Бубнов, А.Н. Рудый Методические указания включают в себя изложение теоретиче- ских методов решения основных задач математического програм- мирования, а также контрольные задания по каждой теме для само- стоятельного решения. Указания состоят из восьми разделов, по каждому из которых предлагается 10 задач. В каждом разделе опи- сывается теоретическое обоснование метода, формальный алгоритм и пример решения типовой задачи. Указания предназначены для студентов экономических специ- альностей заочного отделения БНТУ, они могут быть также полез- ны преподавателям, ведущим практические занятия по курсу мате- матического программирования. © БНТУ, 2006 РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ МЕТОДОМ ЖОРДАНА-ГАУССА Системой линейных алгебраических уравнений называется сово- купность формальных равенств вида: апхj + апх2 + . . . + аХпхп - Ьь «21*1 + «22*2 + • • • + а2пх„ = ь2, ат\х\ + ат2х2 + • • • + атпхп = Ьт, (1) где al}, b, е й - заданные числа, х, - неизвестные, 1 х3 { j = 1, ..., п ) обращают каждое уравнение системы (1) в верное равенство. Сис- тема, имеющая хотя бы одно решение, называется совместной, иначе - несовместной. Решить систему - означает найти все ее ре- шения. Две системы называются эквивалентными или равносиль- ными, если они имеют одинаковые множества решений. Аналогич- но, расширенные матрицы эквивалентных систем будем называть эквивалентными. Например, системы S:- |2х, + х2 = 4 ) [5Х! - 2х2 = 1,J, [ 2xj + x2 [9x, = 9, 4,] v - 2,1 x, с расширенными матрицами А = \ Г 2 1 4Л Н - 2 1 / У У 9 О 9 1 4^ 1 Г о 1 2^ у являются эквивалентными, так как все они имеют единственное решение Х=(1,2). Элементарными преобразованиями матрицы называются: пере- становка местами любых двух строк; умножение строки на любое, от- личное от нуля число; прибавление к одной строке матрицы любой другой строки, умноженной на любое число; удаление нулевой строки. Решение системы методом Гаусса и его модификацией - мето- дом Жордана-Гаусса основано на следующем утверждении: матри- ца, полученная элементарными преобразованиями расширенной матрицы системы эквивалентна исходной матрице, т.е. элементар- ные преобразования расширенной матрицы системы не изменяют множества решений системы. Суть обоих методов состоит в том, чтобы при помощи элемен- тарных преобразований привести расширенную матрицу системы к наиболее простому виду, т.е. к такому виду, когда решение найти достаточно легко. Например, ясно, что систему Sj с матрицей Ах решить легче, чем исходную систему S с матрицей А, а решение системы S2 вообще очевидно. Переход от матрицы А к матрице Ах можно осуществить, например, прибавляя ко второй строке матри- цы А, первой строки, умноженной на 2. Чтобы из матрицы А\ по- лучить А2 , можно поступить следующим образом: сначала вторую строку А] умножим на 1/9, а затем к первой строке прибавим вто- рую, умноженную на -2. Переменная х, называется базисной в i-м уравнении системы (1) если fly = 1 и akj = 0 при к f- i, к = 1, 2, . . . , т. 4 Другими словами, переменная х, вляется базисной в /-м уравнении, если коэффициент при ней в этом уравнении равен 1, а в остальных уравнениях - 0, т.е. в других уравнениях этой переменной нет. Говорят, что матрица системы приведена к базисному виду (или имеет базис) если в каждом ее уравнении имеется базисная пере- менная. Например, матрица А системы S не имеет ни одной базис- ной переменной, матрица Ах имеет базисную переменную х2 в пер- вом уравнении, а матрица А2 приведена к базисному виду. Справедливо следующее утверждение: При помощи элементар- ных преобразований расширенную матрицу любой совместной сис- темы можно привести к базисному виду. Если матрица системы приведена к базисному виду, то перемен- ные, не являющиеся базисными, называются свободными. Напри- мер, в матрице А2 все переменные - базисные, свободных нет. Решение системы, полученное после приравнивания нулю всех свободных переменных, называется базисным. Алгоритм приведения матрицы к базисному виду Каждая итерация алгоритма состоит из трех шагов: Ш а г 1. В первой строке матрицы находим ненулевой элемент aV] Ф О , (желательно, aVj = 1) . Если таких нет, то в случае Ъ\ = 0 вы- черкиваем нулевую строку; если Ь\ ф 0 , то, очевидно, система несо- вместна. Найденный элемент назовем разрешающим (или ведущим). Если а\\ — 1, то переходим к шагу 3, иначе к шагу 2. Ш а г 2. Делим первую строку на разрешающий элемент ац ф 0. (После этого шага коэффициент при Xj в первом уравнении будет Ш а г 3. Ко всем остальным строкам, кроме первой, прибавляем первую строку, умноженную на {-ац ), где / - номер изменяемой строки (i =• 2,3,..., in J. После этого шага коэффициент при х, в осталь- ных уравнениях будет 0 , и неременная Xj станет базисной в первом уравнении. Затем применяем шаги 1 , 2 и 3 ко второму уравнению по- лученной матрицы и т.д. Так как число уравнений системы конечно, то этот процесс завершится не более чем за m итераций. Решение системы по этому алгоритму называется методом Жордана-Гаусса. 5 После того, как система приведена к базисному виду, находят ба- зисное решение, соответствующее выбранному базису. Для этого пе- ременные, не вошедшие в базис, приравнивают нулю, а остальные переменные (базисные) находят по правым частям соответствующих уравнений. Приведем решение типового примера задания 1: Найти базисное решение системы с расширенной матрицей ' 2 1 3 1 2 2 1 5 .4 5 0 14 4 ^ 12 32, . Применим алгоритм приведения матрицы к базисному виду: В первой строке элемент ai2 =1, поэтому выберем его в качестве раз- решающего. Теперь изменяем вторую и третью строки следующим образом: ко второй строке прибавляем первую, умноженную на (-2), к третьей прибавляем первую, умноженную на (-5). В результате получим матрицу 2 1 3 - 2 0 - 5 - 6 0 -15 в которой переменная х2 стала базисной в первом уравнении. Теперь применяем шаги 1-3 ко второй строке полученной матрицы. Нахо- дим ненулевой элемент, например, а24 = 3, и делим вторую строку на этот элемент. Получим матрицу ( 1 О / 3 - 6 О % 1 -15 9 4 / / 3 12 Теперь делаем нули в остальных строках четвертого столбца этой матрицы, для чего к первой строке прибавляем вторую, умно- женную на -1, к третьей прибавляем вторую, умноженную на -9. В результате расширенная матрица системы примет вид: б 'Уз 1 % 0 -Уз 0 -Я 1 0 0 0 0 J Вычеркивая нулевую третью строку, получим матрицу, в базис- ном виде: Г к 14/ К-Уз J • В первой строке базисной является переменная х2 , а во второй - переменная х4. Переменные X; и Xj являются свободными. Прирав- нивая их нулю, получаем базисное решение, соответствующее это- му базису: х/ = xj = 0, =8/3, х4 - 4/3 или Xi = (0, 8/3, 0, 4/3). Най- дем другое базисное решение, т.е. решение, в котором базисными являются другие переменные. В базис можно включить переменные xi или xj , которые сейчас являются свободными. Выберем, напри- мер, переменную х/ для включения в базис. Ее можно сделать ба- зисной в первой строке, т.к. элемент ап = 8/3 Ф 0 (при этом из бази- са выйдет переменная х2), или во второй строке ац = -2/3 Ф 0 (при этом из базиса выйдет х4 ). Будем делать X/ базисной, например, в первой строке, т.е. в качестве разрешающего выберем элемент аи = 8/3 Ф 0 (помечен в последней матрице). Как и раньше, разделив пер- вую строку на разрешающий элемент и прибавив ко второй строке полученную первую, умноженную на 2/3, приведем матрицу к но- вому базису: Полагая свободные переменные х2 и х3 равными нулю, получим новое базисное решение Х2 = (1, 0, 0, 2). 7 Контрольные задания для самостоятельного решения Задание 1. Найти целочисленное базисное решение системы с заданной расширенной матрицей: Варианты: г 0 1 0 - 1 1 1 - О f 2 2 0 1 1 1 ( 8 1 . -3 3 - 2 4 1 1 1 2. 3 0 3 - 2 1 1 1 12 к 0 1 0 3 ' "О 5 V" - 3 4 0 - 1 ( 1 2 f 4 - 3 3 2 9 Л ( 1 3 1 з - 2 ^ 3. 3 3 - 4 1 12 4. 0 3 3 1 0 V 11 - 3 2 5 30 / ? V 2 9 5 7 1 - / 1 0 1 1 3^ г 4 - -3 1 1 : 3 1 5. 0 1 3 2 6 6. 1 1 г — г ; 1 3 V 1 0 - 1 1 - 3J 3 1 -2 - 1 : -13) f - 2 2 - 3 4 12ч \ ( 0 3 4 2 1 ю ^ 7. 3 - 1 1 - 7 8. 0 2 - 3 2 1 К 2 - 2 - 3 2 к 3 4 - 1 3 ; ioJ г 0 2 0 1 1 1 - f 2 - 2 з - Г. J 81 9. - 3 4 4 0 • < 1 - 2 0 10. -1 1 1 2 6 V 2 - 3 1 - 4 1 j 1 ? V 2 4 - 3 0 ; 2J РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ГЕОМЕТРИЧЕСКИМ МЕТОДОМ Общей задачей линейного программирования называется задача нахождения минимума (максимума) линейной функции Z = с/ X/ + с2 х2 + . . . + с„ хп —>• min (max) (1) при ограничениях : "" аи х/ + а, ? х2 + .. Л а!п х„ <(=,>)&,, а2/ х/ + а22 х2 + . . . + а2п х„ < ( = , > ) Ь2, (2) ^ ат/ х/ + ат2 х2 + . . . + ат„ х„ <(=,>) Ът , Х;>0 , j = 1, . . . , П, (3) где ср аи, bj - заданные числа, х} - неизвестные, i = 1, ...,m,j = 1, ...,п и в любом из ограничений вида (2) может встречаться любой из зна- ков <, = или > . Если число неизвестных п = 2, то задача (1) - (3) примет вид Z = с/ х + с2 у —» min (max), (4) ^ аи х + а 12 у < ( = > ) £ / . а2,х + а22у <{=,>) Ь2, (5) ^amjx + ат2у<{=, >)Ь„,, х > 0 , у > 0, (6) и ее можно решить геометрическим методом, так как каждая пара неизвестных (х, у) может быть представлена точкой на координат- ной плоскости хОу. При решении задачи (4) - (6) сначала строят так называемую до- пустимую область, т.е. множество точек (х, у) плоскости, координаты 9 которых удовлетворяют всем ограничениям (5) и лежат в первой четверти координатной плоскости (ограничение (6)). Поскольку все ограничения (5) - линейные, то допустимая область будет пред- ставлять собой выпуклый многоугольник (конечный или бесконеч- ный) или пустое множество. Затем среди точек допустимой области находят оптимальную, т.е. такую точку Мп координаты которой (х0, у0) доставляют мини- мум (максимум) целевой функции Z. Для этого по виду целевой функции (4) строят линию уровня функции Z, соответствующую Z=0, т.е. прямую L0: ct х + с2 у = 0 и находят градиент функции f dZ дгл Z - вектор gradZ-VZ = —,— -fcl,c2J, который показывает 1,ах ду) направление наибыстрейшего возрастания функции Z. Вектор анти- градиента (-С/, -с2) будет показывать направление наибыстрейшего убывания целевой функции Z. Вектор градиента перпендикулярен линии уровня L(, . Перемещая линию уровня L0 параллельно самой себе в направ- лении градиента (с/, с2) , находим последнюю точку допустимой области, которую она пересекает при таком движении. Очевидно, что это будет точка максимума. Перемещая линию уровня в проти- воположном направлении (-clt -с2) , находим точку минимума. По- ясним этот метод на конкретном примере. Геометрическим методом найти максимум и минимум функции Z для х, у > 0 при заданных ограничениях Z = х - Зу, -х + у <4, j 5х + 4у <34, х + 8у > 14. Р е ш е н и е . Построим допустимую область. Для этого в системе координат хОу строим прямую -х + у= 4 - границу первого ограничения. Затем определяем, в какой полуплоскости находятся точки (х, у), для которых -х + у < 4. Для этого выбираем любую точку, например (0, 0), и проверяем, удовлетворяет ли она этому неравенству. Поскольку -0 + 0 = 0 < 4, то точки, для которых -х+у<4 лежат в той же полуплос- кости, что и точка 0(0,0), т.е. справа (ниже) от границы -х + у = 4. 10 Аналогично строятся остальные полуплоскости, соответствую- щие ограничениям 5х + 4у < 34 и х + 8>> > 14 (ниже прямой 5х + 4у = 34 и выше прямой х + 8у = 14 ). Множество точек, удовлетворяющих всем трем неравенствам, образуют треугольник ECD. Учитывая ог- раничение х > 0 и у > 0, получаем допустимую область - четырех- угольник ABCD. Проведем линию уровня Lq, соответствующую значению Z =0, т.е. прямую х - Зу = 0 (для точек, лежащих на этой прямой, значе- ние Z =0). Она будет проходить через точку 0(0, 0) перпендикуляр- но вектору п = VZ = (1,~3) . Перемещая линию уровня в направле- нии градиента п , т.е. в направлении возрастания Z, находим по- следнюю точку допустимой области, которую линия уровня пересе- кает при этом движении (линия Li). Это будет точка максимума. В нашем случае - это точка D(6, 1), координаты которой можно най- ти, решив систему линейных уравнений 5х + 4у = 34 и х + 8>> = 14. Аналогично, двигая линию уровня в противоположном направле- нии до линии Ь2, находим точку минимума - точку С(2, 6). Таким образом, ZMAX= Z(6,l)= 6 - 3-1=3, Zffl/n=Z(2,6)=2-3-6—16 . Задача решена полностью. Контрольные задания для самостоятельного решения Задание 2. Геометрическим методом найти максимум и мини- мум функции Z для х, у > 0 при заданных ограничениях. 11 Варианты 1. Z = 2х + у , [Зх - 4у < 4, ^ -х + 6у < 8, I х + у > 1 , 3. Z = 2х - у, Г2х + у < 3, 1 х + у > 6, Lx - Зу < 3, 5. Z = 4х + у, Гх - 2у > О, < 4 х - у < 14, 13х + у > 7, 7. Z = 2x + y, Г X > 2, ^ 4х - у < 8, I X - у > -1, 9. Z = 5х + у, Г х - 4у > -3, -j 4х - Зу < 14, [_ Зх + у > 4, 2. Z = Зх + у. Г У ^ ') л х - 2у < 3, l2x + у > 1, 4. Z = х + у, Г У - 2, 1 х + у < 7 , 1-х + 2у < 2, 6. Z = 3 x - y , Г2х + 3у< 13, ^ х > 2, L 5х - Зу < 22, 8. Z = х + 5у, Г Зх - у > 3, 1 х - у < 4 , t х + у > 6, 10. Z = Зх, Гх + у < 7, -i 2 х - у < 11, [_4х + у > 19. РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМПЛЕКС-МЕТОДОМ Задача линейного программирования (ЗЛП) (1) - (3) (см. задание 2) называется канонической, если все ограничения вида (2) являются уравнениями (равенствами), т.е. задачей линейного программиро- вания в канонической форме называется задача: Z = с; Xj + с2х2 + . . Л с„ х„ -> min (max) (1) при ограничениях : а,, х, + а12х2 + . . .+ а!п х„ = bh J а2, х, + а22х2 + . . . + а2п х„ = Ь2, (2) ат, хI + ат2 х2 + . . . + ат„ х„ = Ь„,, Xj20,j = l,...,n. (3) Симплекс-метод является вычислительной процедурой, которая позволяет решить любую каноническую ЗЛП алгебраическим мето- дом. Теоретической основой метода являются следующие два ут- верждения: Теорема 1. Если ЗЛП имеет допустимые решения, то существует хотя бы одно базисное допустимое решение задачи. Теорема 2. Если ЗЛП имеет конечное оптимальное решение, то хотя бы одно из оптимальных решений является базисным. Напомним, что решение системы (2) называется допустимым, если оно удовлетворяет ограничениям (3). Таким образом, из теоремы 1 следует, что если не существует ни одного базисного допустимого ре- шения системы (2), то эта система вообще не имеет допустимых реше- ний, т.е. ограничения (2) - (3) являются несовместными. В случае если имеются допустимые решения системы 2, то теорема 2 утверждает, что оптимальное решение ЗЛП можно найти среди базисных допус- тимых решений этой системы, которых, как мы знаем, конечное число. Суть симплекс-метода и состоит в последовательном переборе базис- ных допустимых решений системы (2), начиная с некоторого началь- ного, которое еще называют первоначальным опорным планом. Пе- 13 ребор осуществляется таким образом, чтобы каждое новое решение было лучше предыдущего (в смысле приближения к максимуму или минимуму целевой функции Z). Итак, для применения метода необходимо, чтобы задача была в канонической форме, и чтобы существовало начальное базисное допустимое решение (опорный план), наличие которого гарантиру- ет непротиворечивость ограничений задачи. Чтобы преобразовать ЗЛП к каноническому виду к правой части каждого ограничения-неравенства прибавляют или вычитают неот- рицательную дополнительную переменную, например, ограничение Зх] + 5Х2 - 2х3 <7 преобразуется в уравнение 3xj + 5х2 - 2х3 + х4 = 7 прибавлением дополнительной переменной х4 > 0, а неравенство вида X] - 2х2 + х3 >5 заменяется на уравнение х, - 2х2 + xj - xs = 5, гдех 5>0. Заметим, что знак неравенства > можно заменить на < умножением всего неравенства на -1, например, неравенство Х\ - Зх2 > -6 эквивалент- но неравенству -х, + Зх2 <6. Отметим также, что максимизацию це- левой функции Z можно заменить на минимизацию функции - Z и наоборот, так как максимум функции Z = с/ х/ + с2 х2 + . . .+ с„х„ достигается в тех же точках, что и минимум функции -Z = -С/ Х] - С2 х2 -. . .- с„ х„ . Мы приведем алгоритм симплекс-метода для минимизации це- левой функции (1) Z = с/ х/ + с2х2 + . . . + с„ х„ . Поясним суть мето- да на следующем примере: Пусть требуется решить следующую ЗЛП: Найти максимум функции Z = Зх/ +4 х2 —max ^ при ограничениях: [Зх, + х2 < 9, [х, + 2х2 < 8, х1, х2 > 0. Приведем задачу к каноническому виду и заменим максимиза- цию целевой функции Z на минимизацию функции Z' = -Z. Полу- чим следующую задачу: 14 Z'~ -3xi - 4x2 + Охз + 0x4 —> min, (4) ГЗХ/ + Х2 + x3 = 9, [xi + 2X2 + X4 = S, (5) x, , x2, x3 , x4 > 0. (6) Ясно, что переменные xj и x4 являются базисными в системе (5) и соответствующее базисное решение Хо = ( 0, 0, 9, 8) является допус- тимым, т.к. все Xj > 0. При этом Z0 = 0. Начнем с того, что проверим опорный план Х0 на оптимальность. Поскольку целевая функция Z'= -3xi - 4 х2 + 0х2 + 0х4 выражена че- рез свободные переменные Х/ и х2, коэффициенты при которых от- рицательны, то, очевидно, увеличение этих переменных приведет к уменьшению значения целевой функции на 3 ед. при увеличении х/ на одну единицу и на 4 ед. при увеличении на одну единицу х2 (сей- час X/ и х2 равны 0 ). Поэтому делаем вывод, что опорный план Хо не является оптимальным (т.к. введение в базис переменных xt и х2 приведёт к уменьшению значения целевой функции). Итак, для того, чтобы получить лучшее базисное решение, мы должны включить в базис переменные X/ и х2 . Будем вводить их в базис по очереди. Поскольку увеличение переменной х2 быстрее уменьшает Z, то выбираем переменную х2 для включения ее в базис (это разумно, но не обязательно). Теперь надо выяснить в какой строке системы (5) переменная х2 будет базисной, чтобы получен- ное новое базисное решение было допустимым. Анализируя первое уравнение системы Зх/ + х2 + х3 = 9, замеча- ем, что поскольку х/ = 0, то увеличение х2 влечет уменьшение х2. Так как xj > 0 ввиду (6), то увеличение х2 возможно лишь до тех пор, пока х2 не уменьшится до нуля, т.е. до значения 9/1 = 9. По- скольку переменная есть также и во втором уравнении, то рассу- ждая аналогично, заключаем, что в этом случае переменную можно увеличивать максимум до значения 8/2 = 4 при котором пе- ременная х4 уменьшится до нуля. Новое базисное решение будет допустимым, если мы будем уве- личивать переменную х2до значения, равного min{9/l, 8/2} = 4, кото- рое достигается во второй строке системы. Поэтому переменная х? 15 должна быть базисной во втором уравнении, элемент а.22 ~ 4 системы будет разрешающим и, проводя преобразования Жордана-Гаусса, получаем новое (улучшенное) базисное допустимое решение: 3 1 1 1 [2] О 0 1 О Уг Xj = (0, 4, 5, 0), Zj = -3-0 - 4 - 4 + 0-5 + 0 0 = -16 < Z0. Теперь повторим эту процедуру для нового опорного плана X, . Для того, чтобы проверить его на оптимальность, нужно выразить целевую функцию через свободные переменные х, и х4 этого плана, поскольку их нужно будет изменять, чтобы получить другое (луч- шее) базисное решение. Для этого из второго уравнения последней системы выражаем базисную переменную х2 = 4 - У2 Х) - Уг х4 и под- ставляем ее в целевую функцию Z = -Зх, - 4 х2 + 0х3 + 0х4 = -Зх, - 4 (4 - V2X1 - Уг х4 ) + 0х2 + 0х4 = -16 — Xj + 0х2 + Охз + 2х4 . Проводимые вычисления удобно оформлять в виде так называемых симплекс-таблиц, которые являются, фактически, расширенными мат- рицами системы ограничений (5) с добавленной Z - строкой. Исходная симплекс-таблица. Базис X1 Х2 ^з Х4 Значение (Ь) х3 х4 3 1 1 0 1 \2\ 0 1 9 8 - Z - 3 - 4 0 0 0 Опорный план Х0 = ( 0, 0, 9, 8) , значение Z равно Z0 = 0. Т а б л и ц а 1 Базис X, х3 х4 Значение (Ь,) х3 5/2 0 1 -Уг 5 х2 У2 1 0 Уг 4 - Z -1 0 0 2 16 16 План Xj = (0, 4, 5, 0) , значение Z равно Z/ = -16 . Последняя строка симплекс-таблицы называется Z - строкой по- скольку в ней расположены коэффициенты целевой функции Z. За- метим, что для того, чтобы выразить коэффициенты целевой функ- ции через свободные переменные, достаточно преобразованиями Жордана - Гаусса сделать нули в базисных столбцах Z - строки. При этом новое значение Z автоматически появится в столбце "Зна- чение" с противоположным знаком. Поскольку в Z - строке есть отрицательный коэффициент в пер- вом столбце, то план X) не оптимален, так как введение в базис сво- бодной переменной х/ уменьшает Z (введение в базис свободной переменной х4 увеличивает Z). Поэтому вводим в базис х ь и первый столбец таблицы будет разрешающим. Чтобы выбрать разрешаю- щую строку, как и раньше делим элементы столбца "Значение" на положительные элементы разрешающего столбца и находим мини- • I 5 4 1 о мальное частное: mln]TJ^< j / 2 ) к о т о Р о е Д ° с т и г а е т с я в первой строке, которая и будет разрешающей. Значит разрешающим эле- ментом табл. 1 будет элемент аи ~ 5/2 (выделим его прямоугольни- ком). Теперь проведем обычные преобразования Жордана - Гаусса относительно этого элемента, т.е. сначала делим разрешающую строку на разрешающий элемент, Базис X1 Х2 Х4 Значение (Ь) • 0 2/5 -1/5 2 '/2 1 0 4 - Z -1 0 0 2 16 а затем делаем нули на месте всех остальных элементов разрешаю- щего столбца, для чего: ко второй строке прибавляем первую, ум- ноженную на -'/4 , к Z - строке прибавляем первую. В результате получим новую таблицу 17 Т а б л и ц а 2 Базис X, х4 Значение (Ъ,) X, 1 0 2/5 -1/5 2 х2 0 1 -1/5 3/5 3 - Z 0 0 2/5 9/5 18 Новое базисное решение (план)Х2 = (2, 3, 0, 0) , значение Z рав- но Z2 = -18. Просматривая Z - строку, замечаем, что в ней нет отрицатель- ных элементов. Это означает, что при попытке ввести в базис сво- бодные переменные х3 или х4 целевая функция будет увеличиваться (на 2/5 и 9/5 единиц при увеличении на 1 единицу переменных х3 и х4 соответственно). Таким образом, других базисных решений, луч- ших чем Х2, (т.е. с меньшим, чем -18 значением Z) не существует. Решение^ = (2,3, 0, 0) является оптимальным и Zmm = Z(X2) = -18. Решение исходной задачи: Zmax = 18 при х/ = 2, х2 = 3, х3, х4 = 0. Обобщая приведенные выше рассуждения, сформулируем Алгоритм Симплекс-метода Исходные данные: задача в канонической форме; целевая функ- ция минимизируется; найдено начальное базисное допустимое ре- шение (опорный план), то есть система уравнений (2) имеет базис и все правые части уравнений bt 0 - неотрицательны; целевая функ- ция выражена через свободные переменные. При выполнении этих условий каждая итерация метода состоит из трех шагов: Ш а г 1. Имеющийся план проверяется на оптимальность. Если в Z - строке нет отрицательных элементов, то имеющийся план опти- мален и задача решена. Если отрицательные элементы есть, то план не оптимален. Выбираем любой отрицательный элемент Z - строки (как правило, максимальный по модулю) и считаем столбец, в кото- ром он находится в качестве разрешающего. Пусть для определен- ности это столбец переменной л .^ Ш а г 2. Выбор разрешающей строки. Пусть разрешающий столбец, выбранный на предыдущем шаге, это столбец переменной xs. Для 18 каждой /'-й строки (i = 1,...,т) делим элементы столбца свободных членов "Значение" (напомним, что все они неотрицательные) на положителъные_эпем.&яты разрешающего столбца, стоящие в этой строке, и находим минимальное из полученных частных, т.е. нахо- • ъг дим mm —L- . i,ajs>о ais ars Пусть этот минимум достигается в строке г . Тогда г-ая строка яв- ляется разрешающей, элемент ars - разрешающий элемент таблицы. Ш а г 3. Пересчет таблицы. Преобразованиями Жордана-Гаусса пересчитываем таблицу относительно разрешающего элемента ап , найденного на предыдущем шаге, для чего: 3.1. Делим разрешающую строку на разрешающий элемент. В результате, на месте элемента ars будет стоять а '„ = 1. 3.2. Ко всем остальным строкам таблицы (включая Z - строку) при- бавляем полученную разрешающую, умноженную на элемент (-а„), где i - номер изменяемой строки i =l,2,...,r-l,r+l,...,m. К Z - строке при- бавляем разрешающую строку, умноженную на (~cs). Иначе говоря, эле- менты новой таблицы (со штрихом) вычисляются по формулам: а= arj!ars; - новые элементы разрешающей строки (/' = 1, 2, .... п)- b'r — Ъг!ап', а 'у = atj - a'rj- ais; - новые элементы i-й строки (i =1, 2, ...,m;j = 1, 2, .... п); b', = br b'r-ais, c'j = сj - a'rj-c,y; - новые элементы Z - строки (j = 1, 2, ..., л); Z' = Z-b'r-cs. В результате этих преобразований в столбце xs везде будут сто- ять нули кроме /"-строки, где будет 1, т.е. будет новой базисной переменной, целевая функция будет выражена через новые свобод- ные переменные, новый план X ' находится в столбце "Значение" и лучше предыдущего, так как значение целевой функции для нового плана равно -Z '< Z. Переходим к ш а г у 1 и повторяем всю проце- дуру для нового плана X'. 19 Поскольку базисных решений системы (2) конечное число, а ка- ждое новое базисное решение лучше предыдущего, то этот процесс завершится за конечное число шагов. Решение задачи линейного программирования в общем слу- чае. Рассмотрим следующую задачу ЛП: Z = - 3xi + х2 —> min, Г 2хi —х2 >2, S -xi + 2х2 £5, L XL + Х2 <10, Я/ >0. Приведем ее к каноническому виду введением трех неотрица- тельных переменных х3, Х4, х5. Получим задачу: Z = - 3xj + х2 —> min, C2xi -х2 - х3 = 2, -j -XI + 2х2 - x 4 - 5, (7) [_х/ + х2 + xs = 10, Xl,X2, Х3, Х4, Х5 >0. При попытке решить эту задачу симплекс-методом возникает определенная трудность, связанная с тем, что нет очевидного на- чального базисного допустимого решения (опорного плана), так как переменные х3 и х4 не являются базисными. Умножение первых двух уравнений на -1 также ничего не дает, поскольку соответст- вующее базисное решение (0, 0, -2, -5, 10) не будет допустимым. Пытаться просто перебирать базисные решения в попытке отыскать допустимое, нецелесообразно, так как неясно, имеет ли эта задача вообще допустимые решения. Для решения проблемы применим метод искусственного бази- са. Введем в первые два уравнения (третье не создает проблем) ис- кусственные переменные х6 > 0 и х7 > 0. В результате получим базис из переменных хй, х-,, х5 . 20 2x i — х2 - х3 + хй = 2, -X/ + 2Х2 - Х4 + XJ — 5, X, + X2 + хJ = 10. (18) Соответствующее базисное решение^ = (0, 0, 0, 0, 10, 2, 5) является допустимым для ограничений (8). Однако ограничения (7) и (8) не являются эквивалентными в том смысле, что любому до- пустимому решению системы ограничений (8), в котором хотя бы одна искусственная переменная отлична от нуля, нельзя поставить в соответствие допустимое решение системы ограничений (7). С це- лью исключения искусственных переменных из базисного решения системы ограничений (8), т.е. для получения допустимого базисно- го решения системы ограничений (7), используем алгоритм сим- плекс-метода. Для того, чтобы искусственные переменные стали свободными, необходимо, чтобы они были равны нулю (сейчас ХБ = 2 , = 5 ). Поэтому введем искусственную целевую функцию W = х6 + х7 и будем ее минимизировать при ограничениях (8). Если удастся найти базисное допустимое решение при котором W = О (сейчас W = 7), то тогда х6 и Х7 будут равны нулю, поскольку они неотрицательны, и мы получим базис из основных и дополнительных переменных. Таким образом, задача разбивается на два этапа. На первом этапе минимизируется искусственная целевая функция W. Этот этап за- кончится либо нахождением опорного плана исходной задачи (7), либо тем, что минимизировать функцию W до нуля не удастся, т.е. допустимых планов нет, а значит (ввиду теоремы 1) и нет вообще допустимых решений задачи. Если опорный план найдется, то на втором этапе решаем задачу симплекс-методом. Проиллюстрируем описанный выше метод ис- кусственного базиса, применив его к решению задачи (7). Э т а п 1. Составим исходную симплекс-таблицу для задачи (8). Все вычисления будем проводить также и для целевой функции Z. Тогда после завершения первого этапа получим целевую функцию Z , выраженную через свободные переменные. 21 Базис X , x2 X j x4 XJ Xg X 7 Значение (bj) Xg 2 - 1 - I 0 0 1 0 2 X- - 1 2 0 - 1 0 0 1 5 X j 1 1 0 0 1 0 0 1 0 -Z - 3 1 0 0 0 0 0 0 - W 0 0 0 0 0 1 1 0 Для того, чтобы начать минимизацию функции W, ее надо выра- зить через свободные переменные. Для этого, из W - строки вычтем первую и вторую строки. Получим Т а б л и ц а 1 Базис x, X j x4 XJ Xg X 7 Значение, (bj) Xg Ш - 1 - 1 0 0 1 0 2 x7 - 1 2 0 - 1 0 0 1 5 *5 1 1 0 0 1 0 0 1 0 -Z - 3 1 0 0 0 0 0 0 - w - 1 -1 1 1 0 0 0 - 7 Так как в W - строке есть отрицательные элементы, то выбираем в качестве разрешающего любой из первых двух столбцов, напри- мер первый. Поскольку min{2/2, 10/1} = 1 достигается в первой строке, то разрешающая строка - первая и разрешающий элемент а п = 2. Пересчитывая таблицу относительно этого элемента, полу- чим новую таблицу: Т а б л и ц а 2 Базис X, x3 x4 Xj X 7 Значение (bj) X, 1 -Vi -Vi 0 0 0 1 x7 0 V? -V2 -1 0 1 6 x5 0 3 / 2 У2 0 1 0 9 -Z 0 - 3 / 2 0 0 0 3 - W 0 - 3 / 2 '/2 1 0 0 - 6 22 Так как переменная х6 вышла из базиса, то в дальнейшем ее не используем (вычеркиваем столбец х6). Теперь разрешающим столб- цом будет второй, разрешающей строкой - вторая и после пересчета получим (поскольку искусственная переменная х7 выйдет из базиса, столбец х7 также вычеркиваем): Т а б л и ц а 3 Базис х, Х2 х3 х4 х5 Значение (bt) X, 1 0 -2/3 -1/3 0 3 Х2 0 1 1/3 -2/3 0 4 Х5 0 0 1 1 1 3 -Z 0 0 -5/3 -1/3 0 5 Этап 1 успешно завершен, так как искусственные переменные выве- дены из базиса и мы получили опорный план Х0 = (3, 4, 0, 0, 3) исход- ной задачи (7), к которому можно применить алгоритм симплекс- метода. На втором этапе W - строка уже не нужна и мы ее вычеркиваем. Э т а п 2. Т а б л и ц а 3 Базис X, х2 х4 х3 Значениефj) Xl 1 0 -2/3 -1/3 0 3 х2 0 1 -1/3 -2/3 0 4 х5 0 0 Ш 1 1 3 -Z 0 0 -5/3 -1/3 0 5 Целевую функцию Z можно уменьшить (сейчас Z = -5) если вве- сти в базис х3 или х4. Выбираем третий столбец в качестве разрешающего, т.к. -5/3 < -1/3. Разрешающей строкой будет третья, т.к. только в ней есть положитель- ный элемент разрешающего столбца. Разрешающий элемент а33 = 1. Пересчитывая таблицу, получим: 23 Т а б л и ц а 4 Базис X, хз х4 Х5 Значениеф) X, 1 0 0 1/3 2/3 5 х2 0 1 0 -1/3 1/3 5 х3 0 0 1 1 1 3 -Z 0 0 0 4/3 5/3 10 Поскольку в Z - строке таблицы 4 нет отрицательных элементов, то новый план Xi = (5, 5, 3, 0, 0) является оптимальным и Zmm = 2(5,5) = -10 . Задача решена полностью. Контрольные задания для самостоятельного решения Задание 3. Решить задачу линейного программирования сим- плекс-методом (х, у > 0). Варианты 1. Z = x - 2у -» min, 2. Z = -х + у min, Зх + у > 8, ГЗх - 2у > 7, j 4х + 5у < 29, -s х + 2у < 13, х + 4у > 10, I х - 2 у < 1, 3. Z = 2х + у —> max, 5. Z = 2х + у ->• max, х - у < О, Зх - 2у < 3, _5х - 4у > 1, 4. Z = х - у —> max, Г-2х + Зу < 5, -< х + 2у > 8, L Зх - у < 10, 6. Z = х + у —> max, х - у > 0 , -х + 2у < 4, .-Зх + 4у > 2, 24 7. Z = 5x + 2y max, Г Зх + у > 9, i 2x + у > 7, l5x + 2y < 17, 9. Z = 2x + у -» max, Г-х + 5y < 4, J X - у < 4, L x + y > 2 , 8. Z = 2x + 4y -> max, Г Зх + у > 8, -i -x + Зу > 4, L x + 2y < 11, 10. Z = x - у —> min, fx + Зу < 7, « Ь х - у < 7, [_5x + y > 7 . ДВОЙСТВЕННОСТЬ В ЛИНЕИНОМ ПРОГРАММИРОВАНИИ. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД Рассмотрим задачу линейного программирования в общей форме: Z = с/ xi + с2х2 + . . . + с„ х„ —> max (1) при ограничениях : у |>0, а а X/ + а 12 х2 -+ . . . + а!п х„ , 0, <221 X1 + а.22 Х2 + . . . + й2„ Х„ , < Ь2, •'••• (2) ак, х, + ак2 х2 + . . . + акп х„ , < Ьк, Ук+\ , Як+! 1 XL + АК+1 2 Х2 + . . . + АК ,-1 „ Х„ = ЬК+1 , .Ут > X/ + U.m2 X? + . . . + Clmn Хп ~ Ът , X/ > 0, j - 1 1 ; 1<п. (3) Каждому г-му ограничению из (2) соответствует переменная у\ так называемой двойственной задачи к задаче (1) - (3) (показана слева от соответствующего ограничения). Двойственная задача имеет вид: W = Ь/>'/ + Ъ2 у2 + . . . + b,„ х„, min (4) при ограничениях : xi > 0, а,, у, + а2,у2 + . . Л ат, ут , >с,, х2>0, anyi + а22у2 + . . .+ ат2ут , >с2 , х,>0, a„yi + a2ty2 + . . .+ ат,ут, >с/, Xi I, an i Уi + a2h!У2 + •• - + аmi i У„, = О / (5) ai„yi + а2пу2 + • • .+ а т „у т - сп, у: >0, i = 1, . . • , к; к <п. (6) 26 Задачи (1) - (3) и (4) - (6) образуют пару задач, называемую в линейном программировании двойственной парой. Сравнивая две задачи, видим, что двойственная задача по отно- шению к исходной (прямой) содержит те же самые коэффициенты а0, bh Cj и составляется согласно следующим правилам: 1. Целевая функция (1) исходной задачи задается на максимум, а целевая функция (4) двойственной задачи - на минимум. 2. Матрица АТ , составленная из коэффициентов при неизвестных в системе ограничений (5) двойственной задачи получается из матрицы А прямой задачи транспонированием (т.е. заменой строк столбцами): А = ^аи а/2 • • • а^ а21 а22 • • • а2п АТ = Г Л an a2i. . . amj ai2 а22 • • • am2 <*2„ • • • anwy . 3. Число переменных в двойственной задаче (4)-(6) равно числу ог- раничений в системе (2) прямой задачи, а число ограничений в системе (5) двойственной задачи равно числу переменных в прямой задаче. 4. Коэффициентами при неизвестных в целевой функции (4) двойственной задачи являются свободные члены в системе (2) пря- мой задачи и наоборот. 5. Если переменная Xj > 0, то /-е ограничение в системе (5) двой- ственной задачи является неравенством " > ". Если же переменная х} может иметь любой знак, то у'-е ограничение в системе (5) представ- ляет собой уравнение. Каждая из задач двойственной пары (1) - (3) и (4) - (6) фактически является самостоятельной задачей линейного программирования и может быть решена независимо одна от другой. Однако при определе- нии симплексным методом оптимального плана одной из задач, тем самым находится решение и другой задачи. Существующие зависимо- сти между решениями прямой и двойственной задач характеризуются сформулированными ниже теоремами двойственности. Теорема 1. (Основная теорема двойственности). Если одна из пары двойственных задач имеет оптимальный план, то и другая имеет оптимальный план причем значения целевых функций задач при их оптимальных планах совпадают, т.е. ZMAX = WMIN. 27 Если же целевая функция одной из задач не ог раничена (для ис- ходной (1) - (3) - сверху, для двойственной (4) - (6) - снизу), то другая задача вообще не имеет допустимых решений. Теорема 2. {Вторая теорема двойственности). Для того, чтобы два допустимых решения X* = (х\ :х*2,--.,х*п) и Y* ~ (У\ ,У*2,---,У*т) пары двойственных задач были их оптимальными решениями, необхо- димо и достаточно, чтобы они удовлетворяли системам уравнений: Д * * (=i С£аух]-Ь,Уу,= 0 / = 1,2,..„т. (7) У=1 Замечание. Соотношения (7) верны только для ограничений в виде неравенств и для неотрицательных переменных. Двойственный симплекс-метод, как и симплекс-метод, использу- ется при нахождении решения задачи линейного программирова- ния, записанной в канонической форме. Вместе с тем двойственный симплекс-метод можно применять при решении задачи ЛП, свобод- ные члены системы ограничений которой могут быть любыми чис- лами (при решении задачи симплексным методом эти числа пред- полагались неотрицательными). Опишем алгоритм двойственного симплекс-метода. Рассмотрим задачу линейного программирования в канонической форме. Z = с1х1 + ... + спхп -» min, (8) " «11*1 +- + аыхп =Ь{ , < (9) V X! >0,х2 >0,... хп >0. (10) 28 Пусть матрица ограничений А содержит единичную подматрицу по- рядка т и первые т переменных х},..., хт являются базисными. Среди чисел Ь,(( = 1,т) есть отрицательные. Вектор X = (& , - ,Ъ т , 0, ...0) есть решение системы (9). Однако, это решение не является планом задачи (8) - (10), поскольку среди его компонент есть отрицатель- ные числе (т.е. не выполняются ограничения (10)). Исключим ба- зисные переменные из целевой функции г. z = d0+dm+i •xm+l + ... + dnxn. Предположим, что dm4 >0,...,dn>Q. Ш а г 1. Составить исходную симплексную таблицу. № строки Базис X1 ... Хщ Хт + 1 Х/с Хп Ъ 1 Xl 1 ... 0 Qlm + l ак а,п ь, 1 Xl 0 ... 0 Olm +1 * Clin т хт 0 ... 1 атт+1 атк Ът т+1 -Z 0 0 d„u i ... I 4 1 ... d„ d0 Ш а г 2. Выяснить, имеется ли хотя бы одно отрицательное число среди элементов столбца Ъ. Если нет, то перейти к шагу 8. Иначе - к шагу 3. Ш а г 3. Если отрицательных чисел в столбце Ъ несколько, то выбрать наименьшее. Пусть, для определенности, это число ( \ Ь/ = minbi i: bj<0 . Строка с номером / - ведущая. Ш а г 4. Среди элементов alJt j = 1,п ведущей строки / находят отрицательные. Если таковых нет, то исходная задача не имеет ре- шения. В противном случае перейти к шагу 5. 29 Ш а г 5. Вычислить min j• a,j< 0 ——. Столбец с номером к - alk ведущий, Cllk - ведущий элемент. Ш а г 6. С помощью ведущего элемента а ^ провести одну ите- рацию метода Жордана-Гаусса. Ш а г 7. Построить новую симплексную таблицу и перейти к шагу 2. Ш а г 8. Задача линейного программирования (8) - (10) решена. По последней симплексной таблице выписать оптимальный план и минимальное значение целевой функции задачи (8) - (10). Замечание. Если среди чисел dm+^,...,dn есть отрицательные, то следует в системе ограничений (9) преобразовать свободные члены bj в неотрицательные, умножив на (-1) строки, содержащие отрицательные свободные члены и решать задачу (8) — (10) мето- дом искусственного базиса. Пример. Решить задачу линейного программирования: Z = 6х[ + 9x2 ~~ Зхз —>min, { -Xj + 2х2 + *з 3xi + х2 - Хз > 1, xj>0,j = 1,2,3. (П) Решение. Составим для задачи (11) двойственную: W - 2yi + у2 max, -у, + Зу2 <6, < 2у\ + у2 <9, V i -У2 VI ,У2^ 0. (12) 30 Для решения задачи (11) двойственным симплекс-методом при- ведем ее к каноническому виду. Для этого умножим первое и вто- рое ограничения на (-1) и добавим соответственно неотрицательные дополнительные переменные х4 > О , х5 > 0: Z = 6х, + 9Х2 + Зхз —> min, { X/ - 2Х2 ~ Хз х4 — -2, -Зх, - х2 + хз + Xs = -1, (13) XJ>0,j = 1, 2, ..., 5. Базисными переменными здесь являются переменные и х5 . Поскольку все коэффициенты Cj > О , то критерий оптимальности для этого базисного решения выполнен, однако само решение X = (О, 0, 0, -2, -1) содержит отрицательные переменные, то есть не яв- ляется допустимым. Естественно попытаться вывести отрицатель- ные (не являющиеся допустимыми) переменные из базиса, сохранив при этом неотрицательность коэффициентов целевой функции, так как в этом случае полученное допустимое решение будет являться и опти- мальным. Такой подход является содержанием двойственного сим- плекс-метода. Проиллюстрируем его на примере решения задачи (13). Составим исходную симплекс-таблицу. Базис X j X j хз х4 Значение (Ь,) Х4 1 -2 -1* 1 0 -2 х5 -3 -1 1 0 1 -1 -Z 6 9 3 0 0 0 Вычисляем min{bi} = min{-2;-\} = bx--2. Из базиса будем i:bt< О выводить переменную х4 . Следовательно, первая строка таблицы является разрешающей. Среди элементов разрешающей строки на- ходим отрицательные а\2 = -2; а13 = -1. Определяем тт{- - = mini—; --1 = —— = 3. Столбец, I «12 «13 J 12 1J а п в котором достигается этот минимум, соответствует переменной хъ. 31 Этот столбец является разрешающим и разрешающим элементом является элемент а ]3 = -1. Это делается для того, чтобы элементы последней строки остались неотрицательными. Проводим одну ите- рацию метода Жордана-Гаусса относительно этого элемента, т.е. из базиса исключаем переменную х4 и включаем в базис переменную х3. Новая симплекс-таблица имеет вид: Базис X, х2 ХЗ х4 Xj Значение (bj) -1 2 1 -1 0 2 -2 -3* 0 1 1 -3 - Z 9 3 0 3 0 -6 Элемент Ь2 — -3 < 0. Следовательно, разрешающей является вто- рая строка таблицы. Как и ранее, находим • I С1 с 2 1 . [ 9 3 ) . тт\ / — > = = тт\ —; — У = 1. I «21 «22 J U 3 J Следовательно второй столбец - разрешающий, переменную х2 включаем в базис, переменную х5 исключаем из базиса. Пересчитывая таблицу относительно элемента а22 = -3, получаем новую таблицу: Базис X/ х2 XJ х4 XJ Значение (bj) х3 -7/3 0 1 -1/3 2/3 0 х2 2/3 1 0 -1/3 -1/3 1 - Z 7 0 0 4 1 -9 Среди элементов столбца "Значение" нет отрицательных чисел. В Z - строке также нет отрицательных чисел. Следовательно, найден опти- мальный план: Х* = (0; 1; 0), при этом Z* = Zmm = 9. По последней сим- плекс-таблице находим решение двойственной задачи (12). Для этого выясняем, какие переменные задачи (11) входили в исходный базис. В первоначальной таблице ЭТО — Х4, х$. В последней симплекс-таблице находим элементы Z - строки, соответствующие этим базисным пере- менным (с4 = 4, с5 = 1) и прибавляем к ним соответствующие коэффи- циенты исходной целевой функции (с4 = с5 = 0). В результате получаем Г = (4; 1 ) , Г = Ж т а х = 9. 32 Контрольные задания для самостоятельного решения Задание 4. Решить задачу линейного программирования двойст- венным симплекс-методом. Варианты 1. z = х, + 2х2 min, 2. z — 2х, + 5х2 min, 2х, + Зх2 + х3 = 11, Зх, + 4Х2 < 25, Зх, + 2х2 > 11, 2х, - 2х2 < 1, x , > 0 J = L3. 2х[ - х2 > 1, Xj + х3 = 5, x , > 0 j = 13. 3. z - Х| + х2 — > min, х . > 0 , у = 1Д х, + 2Х 2 > 1 , Зх2 - х , <14, 2 Х [ + 2Х2 + х3 = 6, 4. г = Зх| + х2 —» min, Зх, + х2 > 1, 4Х2 - х, <15, 3xj + х2 + х3 = 16, х > 0 , y - U 5. z = 2х, + х2 -» шги, 6. z = х, + 2х2 —> /игл, х, + х2 < 5, - х, + 2х2 < 3, х, + 2х2 х3 = —3, ЗХ) + 2х2 >1, - Xj + х2 + х3 = 2, 2х, + 2х2 < 5, x,>0,j = W. 7. z - 2х, + х2 -» /игл, Зх, + 2х2 + х3 < 11, 8. z — 2х, + Зх2 /л/и, 2х, + 2Х2 > 1, 4Х2 - х , <15, Xj + Зх2 + х3 = 16, X, >0,y = U 2х, + Зх2 > 1, 2Х2 - 2х, < 7, х . > 0 , 7 = й 33 9. z = Xj + 5X2 ~> min, 3x, + 5x2 ^ 1, 2 X 2 - XJ ^ 9 , XJ + x2 + x3 = 7, x. > 0,y - 1Д 10. ^ = 8xj + 6x2 + 7x3 —> w/w, Xj - x2 + 3x3 > 1, X| - 2X2 - 3x3 < 1, x , > O J = U ТРАНСПОРТНАЯ ЗАДАЧА Общая постановка транспортной задачи состоит в определении оп- тимального плана перевозок некоторого однородного груза из т пунк- тов отправления А\, А2, ... , Ат в п пунктов назначения Bh В2, ... , Вп. При этом в качестве критерия оптимальности берется либо мини- мальная стоимость перевозок всего груза, либо минимальное время его доставки. Математическая модель транспортной задачи имеет вид: т п Z = £ ] Г c i j x i j min, (14) т lxy=bj ( j = \,...,n), (15) /=1 п Jjxij=aj (i = ],...,т), (16) ,x;;/>0, (i = \,...,m; j = \,...,n). (17) Здесь с - тарифы перевозки единицы груза из г-го пункта от- правления А\ в j-й пункт назначения В} , b - потребность в грузе в j-м пункте назначения, а,-запасы груза в г-м пункте отправления. Наличие линейных уравнений (15) и (16) обеспечивает доставку необходимого количества груза в каждый из пунктов назначения и вывоз всего имеющегося груза из всех пунктов отправления. При этом, ввиду (17), исключаются обратные перевозки. Задача (14) - (17) явля- ется частным случаем задачи линейного программирования, однако, в силу своей специфики решается специальным методом. Если выполняется так называемое условие баланса то такая транс- портная задача называется закрытой. Если условие баланса (18) не выполняется, то задача называется открытой. 35 m n /=1 y = l (18) Теорема 1. Для разрешимости транспортной задачи необходимо и достаточно, чтобы выполнялось условие баланса (18). т п Если > Yjbj . то вводится фиктивный (п + 1) - й пункт на- /=1 7 = 1 т п значения с потребностью bn+i = Х а ~ X и соответствующие / = 1 7 = 1 тарифы полагают равными нулю, т.е. = 0 (г = 1,2,..., т). Анало- ги п гично, при Y.a, < Yubj вводится фиктивный, (т+1) - й пункт от- /=1 7=1 п т правления с запасами груза am + l = J ^ b j - Y.ai > ПРИ э т о м тарифы на 7=1 /=1 перевозку из этого пункта также полагают равными нулю, ст+\, = 0. Для решения задачи (14) - (17) применяется метод потенциалов, который по существу, является другой формой симплекс-метода. Опишем алгоритм метода. Исходные данные транспортной зада- чи запишем в таблице bj а, Ьх Ь2 К <31 С\\ Cl2 с In а2 сг 1 Сгг C2n [ Cml Cm2 m^n 1. Построение начального опорного плана. Система ограничений (15)-(16) содержит т-п неизвестных и т+ п уравнений, связанных отношением (18). Невырожденный опорный план задачи содержит т + п - 1 положительных перевозок или компонент. Таким образом, 36 если каким-либо способом получен невырожденный опорный план задачи, то в матрице (ху) значений его компонент положительными являются только т + п - 1 , а остальные равны нулю. Клетки, в которых находятся отличные от нуля перевозки, назы- ваются занятыми, остальные - незанятыми. Занятые клетки соот- ветствуют базисным неизвестным, и для невырожденного опорного плана их количество равно т + п -1 . Для построения начального опорного плана применим метод минимальной стоимости. Выбираем клетку с минимальной стоимостью (если их несколь- ко, возьмем любую из них). Пусть, например, ctk = mine у. Тогда в i.J клетку (/, к) записывают число xlk = min{al:hk). При этом, если min(al, bk ) = al, то значение bk уменьшают на at и «закрывают» строку с номером /, так как ресурсы 1-го поставщика исчерпаны. Если min(al ,Ък)-Ък, то значение at уменьшают на Ьк и «закрывают» столбец с номером к, что означает удовлетворение спроса к-го потребителя. Если же ai = bk, то «закрывают» строку или столбец по выбору. Вышеописанную процедуру повторяют для оставшейся транспорт- ной таблицы до тех пор, пока не будут закрыты все строки и столбцы. 2. Построение системы потенциалов. Система потенциалов строится для невырожденного опорного плана и имеет вид: Ui+Uj =ctJ, где С- - стоимость перевозки единицы груза занятой (базисной) клетки в г - й строке и / - м столбце. Вычисление потенциалов удобно проводить по таблице, положив равным нулю один из потенциалов и затем последовательно находя все остальные потенциалы вычитанием из стоимостей базисных клеток уже известных потенциалов. Потенциалы поставщиков и, записывают справа, а потенциалы потребителей о ; - внизу транспортной таблицы. 3. Проверка опорного плана на оптимальность. Для каждой сво- бодной клетки вычисляют оценки = с,v - и, vr 37 Если sfJ > 0 , то опорный план оптимален и задача решена. В противном случае план не является оптимальным, следовательно, его нужно улучшить. 4. Построение цикла и нахождение нового опорного плана. Сре- ди отрицательных оценок выбираем наименьшую. Пусть sik = f f r В клетке (/, к) нарушено условие оптимальности. Для улучшения опорного плана необходимо в клетку (/, к) отправить некоторое ко- личество груза, превратив ее тем самым в базисную. Эта операция эквивалентна действию по замене базиса в симплекс-методе. Клетку (/, к) отмечают знаком «+» и затем строят цикл, расстав- ляя поочередно знаки «-» и «+» в базисных клетках так, чтобы в строках и столбцах стояло по одному знаку «+» иди «-». Цикл стро- ится единственным образом. Обозначим X-minxy, где Ху - перевозки, стоящие в вершинах цикла, отмеченных знаком «-». Величина X определяет количество груза, которое можно перераспределить по найденному циклу. Зна- чение X записывают в незанятую клетку (/, к). Двигаясь по циклу, вычитают или прибавляют X к объемам перевозок, расположенных в клетках, помеченными знаками «-» или «+» соответственно. Пере- возки в остальных базисных клетках остаются без изменения. Пере- ходим к построению системы потенциалов. т т Замечание. Если условие баланса нарушено, т.е. ^ Х^/ > то ;=1 у = 1 При Y j a , < \ М у=1 или потре-вводят фиктивного поставщика ^ т т ^ -п .т бителя при ^ а ; > ^ с потребностью am+l = У\bj - ^а, У / = ] 7=1 J 7 = 1 / = 1 т т или поставкой ат+\ = X а,- - J ] bj соответственно. Стоимости i=l 7=1 38 соответствующих перевозок полагаются равными нулю. При по- строении начального опорного плана в этом случае фиктивные клетки заполняются в последнюю очередь. Пример. Компания контролирует 3 фабрики, производительность которых в неделю (в тыс. изделий) задается вектором а = (30,25,45). Компания заключила договоры с четырьмя заказчи- ками, еженедельные потребности которых (в тыс.изделий) задаются вектором Ъ =(20,15, 25, 3 0 / Стоимость транспортировки 1 тыс. изделий с /-Й фабрикиу'-му заказчику задается матрицей тарифов С = V 3 5 2 6 7 5 3 8 6 4 9 j Требуется определить оптимальный план перевозок с целью ми- нимизации суммарных затрат на транспортировку. 3 4 Так как =100> ^ b j =90, то введем в рассмотрение фик- /=1 j=1 тивного 5-го заказчика с потребностью в = 100 - 90 = 10 (тыс. ед.) груза. При этом положим с^ = 0, i = 1, 2, 3. Исходные данные запи- шем в виде таблицы. Т а б л и ц а 1 а, 20 15 25 30 10 30 5 + 3 5 2: 2 8 0 25 6 7 5 25 3 0 45 15 8 15 6 J- 4 5 9 10 0 39 Построим начальный опорный план методом минимального элемен- та. Первой заполним клетку (1, 3) т. к. тариф этой клетки с\3 = 2 меньше других тарифов (фиктивный столбец заполняется в последнюю оче- редь). Поставка для клетки (1, 3) будет равна = min(3О, 25) = 25. Запи- сываем это число в верхний левый угол клетки. Это означает, что с пер- вой фабрики третьему заказчику планируется поставить 25 тыс. ед. гру- за. При этом требования 3-го заказчика будут полностью удовле- творены и мы закрываем 3-й столбец. Затем в оставшейся части таблицы (без 3-го столбца) ищем клетку с минимальным тарифом. Таких клеток две (1, 1) и (2, 4). Заполняем любую из них, например, клетку (1, 1). Остаток продукции 1-й фабрики равен 30 - 25 = 5. По- этому записать в клетку (1, 1) можно хи = min(5, 20) = 5. Поскольку с первой фабрики вывезен весь груз (30 тыс. ед.), то закрываем пер- вую строку. Далее поступаем аналогично, заполняя свободные клетки в порядке возрастания тарифов, закрывая каждый раз нуж- ные строку или столбец. В результате начальный план имеет вид (см. табл.1): Х° = ( 5 0 25 О О N 0 0 0 25 О ч15 15 0 5 10 Проверим этот план на оптимальность. Для этого найдем потен- циалы щ и vj поставщиков и потребителей. Для этого по занятым клеткам составим систему уравнений вида щ + v} = су : И\ + V] = 3, lh + V4 = 3, Щ + V| = 8, Щ + V3 = 2, Щ + V2 = 6, «з + v4 = 9, щ + v5 = 0. Поскольку уравнений в системе столько же, сколько занятых клеток, то есть 7, а неизвестных - 8, то система имеет бесконечное множество решений. Положим, например, щ = 0. Тогда остальные потенциалы находятся однозначно: v5 = 0; v4 = 9; v2 = 6; V] = 8; щ = -6; щ = -5; v3 = 7. 40 Теперь вычисляем оценки свободных клеток по формуле SIJ = с,J - (и-, + VJ ): s12 = 5~(6-5) = 4>0 , S2i = 6 - (-6 + 8) = 4 > О, S25 = 0-(6+0) = 6 > 0, •Ум = 6 — (-5+9) = 2 > 0, 522 = 7 - (-6+6) = 7 > 0, з^з ~ 4 ~ (0+7) = -3 < 0. 5,5 = 0 - (-5+0) = 5 > 0, 523 = 5 - (-6+7) = 4 > О, Среди оценок есть отрицательная (s33 = -3 < 0 ), следовательно план не является оптимальным. Необходимо улучшить план, загру- жая клетку с отрицательной оценкой. Дня этого построим для клетки (3, 3) цикл с вершинами в загружен- ных клетках (см. табл. 1), расставляя поочередно в вершинах, начиная с клетки (3,3), знаки «+» и « - ». Из поставок в клетках, помеченных зна- ком «минус», выбираем наименьшую: Л = min(15, 25) = J5. Для получения нового опорного плана изменим поставки в вер- шинах цикла: к поставкам в клетках, помеченных знаком «+», при- бавляем величину ^=15, в клетках, помеченных знаком «-», вычита- ем эту величину 15. Новый опорный план поместим в табл. 2. Т а б л и ц а 2 а, \ 20 15 25 30 10 30 20 3 1 5 10 2 1 8 2 0 25 7 6 7 7 7 5 25 3 6 0 45 3 8 15 6 15 4 5 9 10 0 - 2 - 6 0 5 6 4 9 0 Исследование этого плана на оптимальность аналогично преды- дущему. Вычисленные значения потенциалов записаны справа и 42 снизу таблицы, а оценки Sy свободных клеток поместим в левых нижних углах этих клеток. Поскольку среди оценок нет отрица- тельных, то найденный план является оптимальным. Выписываем матрицу X (без последнего столбца): X f 20 0 10 0 ^ 0 0 0 25 V 0 15 15 5 Минимальные суммарные затраты по оптимальному плану со- ставляют: Zmm = 20-3+10-2+25-3+15-6+15-4+15-9 = 430 ден. ед. Из таблицы 2 видно, что избыточная продукция в количестве 10 тыс. изд. оста- ется на третьей фабрике. Контрольные задания для самостоятельного решения Задание 5. Определить оптимальный план перевозок с целью минимизации общих затрат на транспортировку с заданными векто- рами а и b и матрицей стоимостей С. Варианты а Ь С 1 2 3 4 1 (1,24,2,13) (3,10,10,15,4) (10 4 3 6 10^ 10 2 7 10 3 7 10 10 2 3 ,10 3 2 10 1, 2 (28,9,1,2) (4,8,12,15,3) 10 8 10 1 Л 3 1010 6 1 10 9 10 8 3 V1 2 10 1 10, 42 Продолжение таблицы ] 2 3 4 3 (27,13,2,8) (7,12,16,1,4) Г10 2 3 10 2Л 10 8 7 10 1 10 1 6 10 8 v7 10 10 5 1, 4 (20,21,7,2) (2,15,10,7,6J ЛО 6 10 7 3 л 2 10 1 9 10 I 3 5 10 10 ч10 5 10 6 5 , 5 (П,7,8,14) ПЗ ,5,6,4,8) '10 10 5 1 5 N 4 10 2 10 2 10 8 10 5 2 v4 2 10 10 8У 6 (10,11,7,2) (2,15,10,7,6) г\0 6 10 7 Зл 2 10 1 9 10 1 3 5 10 10 ч10 5 10 6 5 , 7 (5,15,2,2) (21,2,11,1,5) У 1 9 10 10 2' 7 10 10 3 3 9 10 10 1 3 10 6 10 9 6, \ / 8 (10,1,14,5) (3,8,4,15,10) f 10 10 1 2 9 10 6 10 5 3 10 8 4 5 К ч9 10 2 6 1 \ V 43 Окончание таблицы 1 2 3 4 9 (6,25,2,1) (3,18,3,11,6) (2 4 10 10 3 ^ 9 10 7 7 10 9 8 10 8 10 ,2 10 2 6 10, 10 (15,10,2,6) (13,9,7,4,7) '10 6 7 6 10^ 6 10 9 10 2 10 9 10 2 7 v8 10 10 2 4у ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ В СЕТИ Рассмотрим сеть G(V, U), где V множество вершин, a U множество дуг их соединяющих, дуге (L j) е U поставлено в соответствие неотри- цательное число dtJ (d,j>0), называемое пропускной способностью этой дуги (если дуга (i, j) - неориентированная, то полагаем dl} = d;t). Выде- лим в сети две вершины. Одну из них назовем источником и обо- значим s, а другую - стоком и обозначим t , Каждой дуге (i, j) сети поставим в соответствие неотрицательное число Ху, которое назовем потоком на дуге (i, j). Потоком из источ- ника s в сток t в сети G (V,U) называется множество неотрицатель- ных чисел |хгу}, удовлетворяющих ограничениям: О9) 1 j Y,xit ~ lL x t j =v> (20) ' J (21) ' J v>0, 0<Ду 0. Ш а г К- Просматриваем все вершины, помеченные на {k-1)— м шаге. Для каждой такой вершины к, соответствующие им вершины /, для которых xki< dkp получают метку (к ), для всех дуг (/',£), вхо- дящих в вершину к, соответствующих им вершины i , для которых xik > 0, получают метку (к '). Алгоритм заканчивает работу одним из двух состояний: а) после некоторого шага мы не можем пометить ни одной вершины, и сток t 46 остался непомеченным. Это означает, что имеющийся поток явля- ется максимальным, a (R, R), где R -множество помеченных, R - множество непомеченных вершин, образует минимальный раз- рез; б) сток t оказался помеченным. Двигаясь от стока t к вершине, номер которой указан в ее метке и т.д., мы придем к источнику. Алгоритм Форда - построения максимального потока в сети Начальный. Выбираем некоторый поток \xIJ j в сети G (V,U) (на- пример х, Г 0 для всех дуг (i,j) е U). Общая итерация 1. Применяем алгоритм нахождения увеличи- вающего пути из источника $ в сток t. Если такого пути нет, то по- строенный поток является максимальным. Алгоритм заканчивает работу. Если увеличивающий путь найден, то переходим к 2. 2. В найденном увеличивающем пути обозначим через Р' множест- во прямых, а Р ' - множество обратных дуг пути и вычисляем величину с, = min (dy-xJ > 0 и £-, - min xt. >0. Полагаем £ = min ( f„ s1) . Увеличиваем поток вдоль пути Р на величину z, полагая xtj = ху+ е, если (i ,j) е Р , Ху = Xjj - s , если (7, j) е Р~, (23) ху = Ху. для остальных дуг пути. Переходим к \. Рассмотрим пример. На рис.1. изображена сеть. Первое число в скоб- ках указывает пропускную способность дуги, второе - дуговой поток. Рис. 1 47 Найдем увеличивающий путь. Общая итерация: Ш а г 1. Источник s получает пометку (s'). Ш а г 2. Так как Х^ = 1 < d = 2, то вершина 1 получает метку (s+). Вершина 2 получает метку (s), т.к. х2/ = 1 > 0. Вершина J не может быть помечена, т.к. xs5 = ds5 (дуга (s, 5) - насыщенная). Ш а г 3. Соседними вершинами с вновь помеченными являются вершины 3 и 4. Вершина 3 помечена не может быть, так как Х)3 = di3..Вершина 4 получает пометку (2~), т.к. хГ2 =1 > 0. Ш а г 4. Соседними с помеченной вершиной 4 являются верши- ны t и 5. Вершина t помечена не может быть, т.к. хы = 0. Вершина 5 получает пометку (4'), т.к. х54=1>0. Ш а г 5. Помечаем вершину t с меткой (5+), х51=1 < d5l=3. Увеличивающий путь: s — 2 - 4 — 5 - t , причем на этом пути дуга (5, t) является прямой, а дуги (2, s); (4, 2); (5, 4) обратными. Увеличим поток вдоль этого пути по формулам (23). Находим s 1 = min (d5t — x5t) = 2, (iJMP+ e2= min (xS2,X2^,x^)-min(\;\;\)-\, OJ)sP- т.е. s = minfs 1,82) = 1. Полагаем X+l2S =X2s-1 = 0, X+142 =x42-l =Q X+l54 =x54-l = 0, X+XSt =x5l+l = 2. Величина суммарного потока в сети равна 3. Общая итерация 1, Для нового потока ищем увеличивающий путь методом расстановки пометок. Пометить удается только вершины J> и 1. Следовательно, увеличивающего пути нет, и построенный поток является максимальным. Минимальный разрез (R,, R), где/? = {S; 1}, R = {2; 3; 4; 5; t} состоит из дуг (R, R ) = {(1, 3); (s, 5); (2,s); (2,1)} и обладает пропускной способностью С (R, R) - dI3 + dss = 3. На рис. 2 минимальный разрез показан пунктирной линией. 48 На рис. 2 минимальный разрез показан пунктирной линией (s4 Рис. 2 Контрольные задания для самостоятельного решения Задание 6. Сеть задана матрицей Z) = ||rf;yj| пропускных способ- ностей дуг {djj = 0 означает, что в сети отсутствует дуга, ведущая из вершины 1 в вершину j). Требуется по матрице D построить сеть и найти в ней максимальный поток из вершины 1 в вершину 10, опре- делив при этом минимальный разрез. Вариант 1 Вариант 2 0 10 4 13 0 0 0 0 0 f 0 2 8 0 0 0 0 0 0 10 0 0 0 6 0 15 0 0 0 2 0 7 0 15 0 5 0 0 0 4 5 0 7 2 5 0 0 0 0 0 7 0 0 8 3 0 0 0 0 13 0 7 0 0 1 0 0 6 0 6 0 6 0 0 10 0 0 2 0 0 6 0 0 0 10 п J 7 0 0 0 15 8 0 0 4 1 5 0 0 0 0 5 1 0 0 0 12 4 0 0 0 3 10 4 0 0 4 11 0 0 0 0 0 0 0 0 5 0 9 0 5 0 0 1 0 0 9 0 0 0 0 0 0 7 12 5 0 9 7 0 0 0 0 5 4 9 0 0 6 0 0 0 6 0 4 0 9 0 11 0 0 0 2 0 11 0 7 0 12 0 0 0 0 0 0 9 7 11 oj 0 0 0 0 0 4 6 12 0, 49 Вариант 3 ' 0 0 12 16 0 0 0 0 0 10 0 5 0 0 0 9 0 0 0 12 5 0 7 3 8 0 0 0 0 16 0 7 0 0 5 0 0 0 0 0 10 3 0 0 13 4 8 0 0 0 0 8 5 13 0 0 7 2 0 0 9 0 0 4 0 0 10 0 12 0 0 0 0 8 7 10 0 9 13 0 0 0 6 0 2 0 9 0 11 . 0 0 0 0 0 0 12 13 11 о , Вариант 5 ' 0 20 25 8 0 0 0 0 0 20 0 7 0 15 0 0 0 0 0 25 7 0 8 0 9 0 0 0 0 8 0 8 0 6 10 0 0 13 0 0 15 0 6 0 9 0 7 0 0 0 0 9 10 9 0 0 12 0 0 0 5 0 0 8 0 0 10 0 0 0 0 0 0 7 12 10 0 3 15 0 0 0 13 0 9 0 3 0 17 0 0 0 0 0 0 3 15 17 о , Вариант 7 ' 0 20 0 12 0 0 0 0 0 20 0 9 0 0 0 6 0 0 0 10 9 0 0 7 11 0 0 0 0 12 0 5 0 0 8 0 0 10 0 0 6 7 0 0 4 9 3 0 0 0 0 11 8 4 0 0 12 6 0 0 3 0 0 9 0 0 15 0 4 0 0 0 0 3 12 15 0 0 25 0 0 0 10 0 6 0 9 0 20 0 0 0 0 0 0 4 25 20 0 , Вариант 4 ' 0 20 15 7 0 0 0 0 0 20 0 0 0 7 0 9 0 0 0 15 5 0 11 3 6 0 0 0 0 7 0 11 0 0 12 0 0 8 0 0 7 3 0 0 4 9 6 0 0 0 0 6 12 4 0 0 10 12 0 0 9 0 0 9 0 0 5 0 10 0 0 0 0 6 7 5 0 9 0 0 0 0 8 0 2 0 9 0 20 0 0 0 0 0 0 10 15 20 о , Вариант 6 0 7 16 20 0 0 0 0 0 0 " 7 0 9 0 4 0 6 0 0 0 16 9 0 3 11 2 0 0 0 0 20 0 3 0 8 0 0 0 10 0 0 4 11 8 0 9 0 12 0 0 0 0 2 10 9 0 0 0 12 0 0 6 0 0 10 0 0 15 0 12 0 0 0 0 12 10 15 0 10 25 0 0 0 10 0 12 0 10 0 13 0 0 0 0 0 0 12 0 13 о , Вариант 8 0 0 19 13 0 0 0 0 0 7 0 10 0 8 0 0 0 0 0 19 10 0 3 10 0 0 0 0 0 13 0 3 0 0 9 0 0 0 0 0 8 10 0 0 15 0 10 6 0 0 0 6 9 15 0 0 12 2 0 0 7 0 0 7 0 0 12 0 9 0 0 0 0 10 12 12 0 10 20 0 0 0 8 0 0 0 10 0 15 0 0 0 0 0 0 9 20 15 0 ; Вариант 9 (О 12 19 О О О О О О 0N 12 О 10 О 4 О О О О О | 19 10 0 9 0 10 О О О О 6 0 9 0 0 12 0 0 10 О 0 4 6 0 0 10 2 9 0 0 О 0 10 12 10 О 0 12 10 О 0 9 0 0 9 0 0 5 0 10 0 0 0 0 2 0 0 9 0 0 О О 0 10 0 10 0 12 0 20 0 0 0 0 0 0 5 9 20 О, Вариант 10 'О 7 13 15 О О О О О О4 7 0 10 О О О 12 О О О 13 10 0 12 3 6 О О О О 15 0 12 0 0 7 0 0 8 О 0 0 3 0 0 4 8 2 0 0 0 0 6 7 4 0 0 10 3 0 О 12 0 0 8 0 0 9 0 2 0 0 0 0 2 10 9 0 7 12 0 0 0 8 0 3 0 7 0 25 О О О О О 0 2 12 25 О, СЕТЕВОЕ ПЛАНИРОВАНИЕ Основой методов сетевого планирования является сетевая мо- дель (сетевой график), отражающая логическую взаимосвязь работ, входящий в некоторый комплекс, что позволяет осуществлять управление ходом выполнения этих работ. Для построения сетевой модели необходимо, прежде всего, раз- бить весь комплекс на отдельные работы или операции и составить очередность выполнения этих работ. Для этого составляется список работ, которые непосредственно предшествуют каждой работе, а так же планируется время, необходимое для их выполнения. Полученные данные удобно заносить в таблицу. В табл. 1 приве- дены данные для проекта, состоящего из девяти работ. Т а б л и ц а 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 На основании данных, приведенных в таблице, строится график комплекса работ, входящих в проект. Каждая работа изображается в виде ориентированного отрезка (дуги). Связи между работами изо- бражаются пунктирными линиями (дуги-связи). В результате полу- чается сетевой график (начальная вершина дуги - начало, а конеч- ная - завершение соответствующей работы): о - с / 4 ^ ".г; V ^ ; --. . .Г \ 52 Рис. 1 Предварительно следует упростить полученную сеть. Можно у д а л и т ь некоторые дуги-связи, а начало и конец удаляемой дуги о б ъ е д и н и т ь в одну вершину. Н а рис. 2 изображена сеть, полученная после упрощения сети, изображенной на рис. 1. з 6 5 Рис. 2 В сетевом графике каждая вершина является конечной для неко- торых дуг(операций), входящих в нее или начальной для дуг (опера- ций) из нее выходящих. Поэтому каждая вершина может трактовать- ся как событие, означающее завершение всех операций (дуг), для ко- торых она является конечной и возможность начала выполнения всех операций (дуг), для которых она является начальной. Начальной вершине соответствует событие, под которым подразумевается нача- ло осуществления проекта, а конечной вершине соответствует собы- тие - завершения выполнения всего комплекса работ. После построения сетевого графика все его вершины нумеруют- ся так, что нумерация является правильной. Алгоритм правильной нумерации Ш а г 1. Нумеруем начальную вершину номером 1. Переходим к шагу 2. Ш а г 2. Удаляем из сети все выходящие из пронумерованных вершин дуги. Нумеруем в произвольном порядке вершины, в кото- рые не входит ни одна дуга, произвольным образом возрастающими по порядку номерами. Шаг 2 проделываем до тех пор, пока не дой- дем до конечной вершины, которой присваиваем следующий по по- рядку номер. В результате правильной нумерации вершин сетевой график, приведенный на рис. 2 примет вид 53 Рис. 3 Номера работ на дугах соответственно заменены продолжитель- ностью их выполнения (продолжительность фиктивной работы со- ответствующей дуги-связи полагаем равной 0). Рассмотрим основные временные параметры сетевого графика. Пусть t,j -продолжительность работы, для которой соответствую- щая дуга (г, j) в сетевом графике имеет в качестве начальной - вер- шину с номером i, а в качестве конечной - вершину с номером j. Ранним сроком начала работы (i, j) называется наименьшее до- пустимое время tjjPH, когда может быть начато ее выполнение. Если работа начата в ранний срок, то время ее окончания t,f" на- зывается ранним сроком окончания Ранний срок начала всех работ, для которых вершина i - начальная, называется ранним сроком наступления события / и обозначается i f . Ранний срок наступления конечного события называется крити- ческим временем и обозначается Ткр. Таким образом, критическое время - это минимальный срок, за который может быть выполнен весь комплекс работ. Каждый путь из начальной вершины в конечную, состоящий из дуг (работ) и дуг-связей продолжительностью Ткр, называется кри- тическим путем, а работы, составляющие такие пути - критически- ми работами. Поздними сроками начала и окончания работы (i, j) называется наи- большее допустимое время начала (t™) и окончания (tif10) этой работы без нарушения сроков выполнения всего комплекса работ. Очевидно: 54 ПН = I. по -к- Наиболее поздний из поздних сроков окончания работ, входя- щих в вершину j, называется поздним сроком наступления события j и обозначается 'Г!'. Рассмотрим работу (i, j). Плановая продолжительность этой рабо- ты равна ty. Максимально допустимое время, на которое можно уве- личить продолжительность работы (i, j) или задержать начало ее вы- полнения, при котором не изменится время выполнения всего проек- та, называется полным резервом R0 времени этой работы. Он равен: R,j = Tf - Тр - и, Резерв времени для работы (i, j), использование которого не из- менит ранние сроки наступления всех событий (т.е. все работы смо- гут начать выполняться в минимально возможные сроки), называет- ся свободным и может быть вычислен по формуле r ij 1 j 11 1ц- Очевидно, полный и свободный резерв времени любой работы, лежащей на критическом пути, равен нулю. Алгоритм нахождения ранних сроков наступления событий 1. Полагаем Т,р = 0. 2. Для j = 2, 3, . . . , п вычисляем Tf = max (ТР + tki). (kj)^i(j) Здесь I(j) - множество всех дуг, входящих в вершину j. Tkp Критическое время Ткр = Тпр. Алгоритм нахождения поздних сроков наступления событий 1. Полагаем ТпП = Г (как правило Т= Ткр.). 2. Для i = п-1, п-2, . . . 7, вычисляем 55 -f,= min (T 11 -ttJ). jeO( 0 Здесь 0 (i) - множество вершин, которые являются конечным для дуг, выходящих из вершины i. Рассмотрим сетевой график, описанный в табл. 1. События (вер- шины) сетевого графика изображены следующим образом: В верхней четверти записан номер события (вершины) в соответствии с правильной нумераци- ей. Номер вершины kj, при движении из которой получено значение Тр , заносится в нижнюю чет- верть. В левой четверти записывается ранний срок наступления события Тр, а в правой четверти - его поздний срок наступления Т,п. Найдем ранние сроки наступления каждого события для сетевого графика, изображенного на рис. 3. Полагаем Т,1' = 0, к, = 0. Рассматриваем вершины в порядке воз- растания их номеров. Т2Р = Т,р + t12 = 0 + 10 = 10, к2 = 1, Т/ = max (Т,р + tl3; Т2Р + t23) = = max (0 + 15; 10 + 0) = Т,р + tl3 = 15, к3 = 1, Т/ = max (Т/ + t24; Т3Р + t34) = = max (10 + 5; 15 + 20) = Т3Р \ t34 = 35, к4=3, Т/ = max (Т3Р + t35, Т4Р + t45) = = max (15 + 15; 35 + 8) = Т/ + t45 = 43, ks-4, Т/ = Т4Р+ t46 = 35 + 6 = 41, к6 = 4, TkF = max (Т5Р + tS7; Тр + t67) = = max (43 + 15; 41 + 10) = T5P + t57 = 58. k7=5. Построим критический путь, начиная с конечной вершины, дви- гаясь по номерам вершин кь, стоящих в нижней четверти. 56 В результате получим 1 - 3 - 4 - 5 - 7 . Найдем поздние сроки на- ступления событий. Полагаем время окончания всего проекта Т = Т7П = Ткр, = 58. Поставим это значение в правую четверть ко- нечной вершины 7. Т6П = Т7" -t67 = 58-10= 48, Г/7 = Т7П -157 = 58 - 15 = 43, П4п = min (Т" - t46; Т5П - t4S) = win - 6; 43-8)= 35, Т3П = min (T5n-t3s; T4"-t34) = min (43 - 15; 35 - 20) = 15, T2n = min (T4n -124; T3n -123) = min (35 - 5; 15-0) = 15, T,n = min (T„3 - tl3; Г / - tIn) = (15 - 75; / 5 - 10) = ft В результате получаем следующую сетевую модель, содержа- щую подробную информацию о ранних, поздних сроках наступле- ния событий, критическом времени и критическом пути. Критиче- ский путь отмечен двойными линиями. Рис. 5 57 Контрольные задания для самостоятельного решения Задание 7. В приведенных ниже таблицах комплекс работ задан их порядковыми номерами, отношением предшествования. Указаны про- должительности работ. Необходимо составить сетевой график вы- полнения работ и посчитать все его числовые характеристики. \ № ра- \ бот № \ вари- анга 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 11 12 1 Каким работам предшествует 4,10 10,5 5 8 9 8 9 - - 6 Продолжитель- ности работ 10 2 6 3 12 8 4 1 15 7 2 Каким работам предшествует 4 10,6 5,10 8 10,9 8 9 - - 4 Продолжитель- ности работ 12 6 1 12 5 7 9 10 4 2 3 Каким работам предшествует 4 10,4,7 5 8 9 8 9 - - 5 Продолжитель- ности работ 7 11 12 6 2 10 1 8 10 9 4 Каким работам предшествует 4,9,5 9,8 5 8 10 8 10 - 10 - Продолжитель- ности работ 7 3 10 12 4 5 9 4 8 11 5 Каким работам предшествует 4,9 9 5,9 8 10 8 10 - 6,7 - Продолжитель- ности работ 10 13 2 8 15 1 6 2 9 7 6 Каким работам предшествует 3,4 5 5 8 9,7 10 6 5 10 - Продолжитель- ности работ 10 1 15 6 7 4 12 3 10 2 7 Каким работам прешествует 3,4 5 5 8 7,9 10 6 7,9 10 - Продолжитель- ности работ 10 1 8 2 6 8 12 3 5 3 8 Каким работам предшествует 3,4 5,8 7,9 5,8 6 10 6 7,9 10 - 58 Окончание таблицы 1 2 3 4 5 6 7 8 9 10 Продолжитель- ности работ 9 3 4 12 6 5 7 10 7 4 9 Каким работам предшествует 3,4 7 6,8,9 7 7 5 10 10 " - Продолжитель- ности работ 9 5 12 8 7 6 6 4 3 8 10 Каким работам предшествует 3 5,7 8,9 10 4,6 8,9 10 10 " Продолжител ь- ности работ 5 10 6 7 9 12 10 8 9 7 ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ Рассмотрим ориентированный граф G(V, U). Каждой дуге иц е U поставлено в соответствие неотрицательное число Ц , которое мы будем называть длиной дуги щ (если граф содержит неориентиро- ванную дугу, мы заменим ее парой противоположно ориентирован- ных дуг, каждой из которых ставим в соответствие одно и то же число /у = Ij). Рассмотрим некоторый ориентированный (s - t) путь, соединяющий вершину s с вершиной t, и обозначим множество дуг входящих в него через P(s, t). Длиной пути P(s, t) называется сумма L[ P(s, t) ] = V / . (i,j)zP(s,t) длин всех дуг, входящих в путь P(s, t). Теперь может быть сформулирована следующая задача : для вы- деленных вершин sat сети G(V, U), среди всех путей их соединяю- щих, требуется найти путь P*(s, t) = L\P*(s,if[ = min L [P(s, t)], дли- P(s,t) на которого минимальна Если вершины сети трактовать как, напри- мер, города, а пути - как дороги между ними, протяженность кото- рых известна, то задача состоит в нахождении кратчайшего мар- шрута между выделенными городами. Прежде чем описать алгоритм нахождения кратчайших путей из выделенной вершины s е V сети G(V, U) во все остальные ее верши- ны, введем следующие обозначения. Для каждой вершины j сети G(V, U), l*( j ) будет обозначать длину кратчайшего (s - j) пути, a l(j ) - длину некоторого (не обязательно кратчайшего) пути (s - j) пути, а v*(j) - номер предпоследней вершины кратчайшего пути, a v(j) - номер предпоследней вершины рассматриваемого пути. В процессе работы алгоритма, на каждой его итерации очередной вершине j присваивается постоянная метка вида (l*(j), v*(j)), где v*(j) - номер предпоследней вер- шины в кратчайшем (s - j) пути. Эта вершина присоединяется к множе- ству вершин R, имеющих постоянную метку. Обозначим через arg(min l(j)) значение индекса j , при котором jeR достигается минимальное значение величин l ( j ) , то есть arg(minl(j)) = i, если => 1( i) = min l(j). JzR JeR 60 Алгоритм построения кратчайших путей в сети Начальный шаг. Полагаем l*(s ) : = О, R: = {s }, l ( j ) = lsj, если дуга (s,j) £ U и l(j) = 00 в противном случае. Для всех вершин v(j) = s. Общая итерация. III а г 1. Пусть arg( min К j )) — i и вершина i jzR имеет метку (l(i), к). Если l(k) = couR^V - алгоритм заканчива- ет работу. Если / ( к ) < со полагаем R : =R u{i} и l*(i)= l(i), v*(i)= k. Если R = V - алгоритм заканчивает работу. Если R - переходим к шагу 2. Ш а г 2. Для всех j 0 R, таких, что (i, j) е U полагаем l ( j ) : = min [t(i) + hp l(j)J. JzR Если 1*( i) + lу < l ( j ) , mo v(j ) : = /; в противном случае v(j ) не меняется. Переходим к шагу 1 следующей итерации. Рассмотрим итерацию, на которой алгоритм заканчивает работу. Это происходит на шаге 1, когда либо l( j ) = со для всех j g R и R * V, либо R=V. В первом случае ни одна дуга, начальной вершиной которой яв- ляются вершина множества R, не ведет в вершины, не принадлежа- щие этому множеству, а значит, не существует путей, ведущих из вершины s в вершины, не принадлежащие множеству R. Во втором случае все вершины получили постоянную метку (l*(i), v*( i)), т.е. найдены кратчайшие расстояния от вершины S ко всем остальным вершинам сети. Заметим, что алгоритм явно не указывает кратчайший путь к вер- шине, а только его длину. Но воспользовавшись второй частью метки: v*( i) - его легко восстановить. Действительно, v*(i) - номер предпо- следней вершины в кратчайшем пути из S в /; пусть v*(i) = i). Но v Y ii) = /"2 - номер предпоследней вершины в кратчайшем пу- ти из S в /'/. Продолжая, мы найдем последовательность вершин S, 4 , ik-i, ..., ii, ii, к, через которые проходит кратчайший путь. Рассмотрим работу алгоритма на следующем примере. Найти кратчайшие пути из вершины S во все остальные вершины сети, изображенной на рис.1 (числа над дугами равны их длинам). 61 tes) 2 ( $ ) 4 П у (oo,s) Рис. 1 На начальном плане вершина S получает постоянную метку (О*, ,S'*), R = {5}, соседние с ней вершины 2, 3 получают временные метки (1, iS"), (10, S) и (7, 5) соответственно, а остальные вершины получают временные метки (оо, (рис. 1). Рис.2 Итерация 1. 1) Минимальное значение первой части меток всех вершин равно 1 для первой вершины, т.е. arg(minl.) = 1. Метка первой вершины стано- jeR вится постоянной. Полагаемi?.= RKJ {1} = fS\ 1}, переходим к шагу 2. 62 2) Просматриваем все вершины, соседние с вершиной, получив- шей постоянную метку (вершиной 1). Для вершины 5 имеем 1*(1) + 115 -1 + 2 = 3 < 1(5) = со, поэтому полагаем 1(5) = 3, V(5) = 1. Для вершины 2 имеем min(l*(l) + lI2, l*(S) + I32 = min (1 + Щ 10) = 10. Так как 1(2) =10, то метка вершины 2 не меняется. Переходим ко второй итерации и т.д. Заметим, что на каждой итерации алгоритма одна очередная вершина i присоединяется к множеству R и получает постоянную метку (!*( i), v*( i) ), которая в дальнейшем не меняется, а для ос- тальных вершин j 0 R пересматриваются текущие значения величин / (j), некоторые из которых могут меняться и в дальнейшем. Резуль- таты вычислений на начальном шаге (итерация 0) и на всех после- дующих итерациях удобно заносить в табл. 1. Если пара чисел (/ f'i j, v( i)) помечается символом ( * ), это означает, что вершина i полу- чила постоянную метку (/*(*i), v *(i)), которая в дальнейшем не меняется. Т а б л и ц а 1 \ ите- \рация № шины \ 0 1 2 3 4 5 6 7 S 0* s* 1 1, s /*, 2 10. s 10, s 10, s 10, s 7; З 7 * j * 3 7, s 7, S 7, s 6, 4 6* 4* 4 со, s 00, S 4, 5 4*, 5* 5 °О, S 3, 1 3*, 1* 6 °О, S ОО, S СО, s ОО, s ОО, S ОО, S ОО, s ОС, S 7 СО, S 00, S 11, 5 8, 4 8, 4 8, 4 8*, 4* t СО, S <Х>, S 13, 5 13, 5 13, 5 13, 5 13, 5 13* 5* Алгоритм закончил работу на 7-й итерации случаем, когда R = fs, 1, 2, 3, 4, 5, 7, t /, {6} 0 R и R * V, а 1(6) = од Это означает, что не существует пути, ведущего из вершины s в вершину б. Для 63 всех остальных вершин сети длины кратчайших путей найдены, а сами пути могут быть построены, как описано выше. Например, для верши- ны 2 имеем: (l*(2), v*(2) ) = (7*, 3*); предыдущая вершина кратчайше- го пути - 3. Для вершины 3 (l*(3), v*(3) ) = (6*, 4*); для вершины 4 - ((l*(4), v*f4)) = (4* 5*),-для вершины 5 - ((l*(5), v*(5) ) = (3* 1*); а для вершины I - ( (l*(l), v*(l) ) = О* SV• Таким образом, кратчайший (s - 2) путь проходит через вершины s, 1, 5, 4, 3,2 и его длина равна 7. Все дуги сети, входящие в кратчайшие пути, изображены на рис. 3. Пары чисел около вершин (рис. 2, 3) - это найденные в результате работы алгоритма постоянные метки вершин, первая часть которых l*(i) - длина кратчайшего (s - i) пути P*(s, i), а вторая - предпослед- няя вершина этого пути (последней является вершина i). Кратчайшие пути образуют дерево, но не остов ное, так как вер- шина 6 не соединена ни с одной другой вершиной. Рис. 3 В заключение отметим, что поскольку на каждой итерации алго- ритма только одна новая вершина и соответствующая дуга добав- ляются к множеству дуг и вершин, образующих кратчайшие пути, то отсюда следует, что множество кратчайших путей в любой сети образует дерево (т.е. не содержит цикла). Контрольные задания для самостоятельного решения Задание 8. Дана матрица L -1ly | расстояний между каждой парой вершин сети. Если 1ц — оо, это означает, что в сети нет дуги, ведущей из вершины i в вершину j. Если ly - lJl, то вершины i и j соединены неориентированной дугой длины . Требуется по матрице L построить сеть и найти кратчайшие пути из вершины 1 во все остальные вершины сети. Вариант 1 Вариант 2 (оо 2 8 9 ОО CO со ОО 00 с о ) [со 10 9 10 00 ОО 00 00 00 2 00 7 6 10 6 5 ОО ОО ОО 10 00 СО ОО со 00 15 ОО 00 00 ОО 7 00 00 8 3 СО ОО ОО 00 ОО 5 00 8 2 6 00 00 00 00 00 00 6 00 ОО 10 9 со 2 ОО 10 со ОО 00 ОО 1 ОС' 00 8 00 00 10 8 00 ОО 4 1 5 оо 00 00 6 со ОО 00 10 5 7 ОС ОО 00 00 3 10 4 ОО со 4 11 00 00 00 6 1 00 ОО ОО 12 4 ОО ОО 5 00 00 ] СО СО 9 00 со 00 00 6 00 00 00 CO 6 СО ОО ОО ОО ОО 8 5 ОО 9 00 ОО 6 ОО ОО СО 8 5 00 9 ОО 00 6 00 ОО со 2 со 11 оо 7 со 12 00 00 00 00 17 12 6 00 9 00 чоо 00 СО со со ОО 4 6 12 00, V 0 0 ОО ОО 00 00 СО 8 7 11 Вариант 3 Вариант 4 со 2 0 00 10 00 00 СО ОО 00 Л со ' оо 12 10 00 СО 00 00 со ОО СО 2 0 0 9 оо 00 ОО оо со со со 12 00 10 6 4 оо 00 со 00 оо 10 9 ОС 6 7 11 со со СО ОО 10 10 00 9 00 ос 00 со СО 00 10 9 г/) СО 00 8 00 CO 10 ОО 6 со 9 00 ОО 12 00 оо 10 СО СО 6 7 ОО 00 4 9 3 00 00 00 4 6 00 ОО 10 2 9 00 00 со 8 11 8 4 со СО 12 6 00 CO оо 10 12 10 00 00 10 10 00 со 3 оо 3 ОО со 00 15 00 4 00 ОО 00 00 2 00 00 9 00 СО ОО ОО оо 4 3 оо 15 00 00 2 5 оо 00 00- 2 9 10 9 00 12 00 ОО 00 со 10 ао со 00 9 со 2 0 ОО 00 ОО 10 СО 10 со 12 'СО 2 0 со 00 со ОО ОО ОО 4 2 5 2 0 00 J 4 ю СО СО со 00 со 5 9 2 0 ОО 65 Вариант 5 00 00 10 13 00 00 00 00 ОО 001 7 00 00 00 8 со ОО ОО оо по 10 20 00 3 10 00 ОО оо ОО со 13 ОО 3 СО ОО 9 00 00 00 оо О0 8 10 00 00 10 00 10 6 00 00 СО 6 9 00 00 ОО 12 2 оо ОО 7 аэ 00 7 со СО 12 ОО 9 ОО ОО ОО 00 10 12 12 СО 10 20 со ОО со 8 00 00 00 10 СО 10 СО 00 00 00 00 00 ОО 20 10 оо У Вариант 6 8 13 5 ОО 00 ОО ОО оо оо 00 ОО 10 00 со 00 12 ОО 00 00 13 10 00 10 00 6 оо 00 O0 00 5 2 ОО 00 00 7 00 ОО 8 00 ОО ОО 3 00 00 4 8 2 00 00 00 СС 6 7 СО 00 00 10 3 00 00 12 оо 2 8 00 со 9 со 2 00 00 00 со 2 00 9 00 7 4 00 00 СО 00 СО 3 2 7 00 2 00 00 СО со 00 2 4 2 00 Вариант 7 00 10 5 00 00 00 00 10 00 7 00 10 00 00 00 7 ОО 00 ОО 9 00 8 2 8 00 6 оо оо 00 10 2 6 00 9 00 00 00 00 6 9 оо 00 00 5 00 00 8 00 00 00 00 2 со 7 12 10 00 00 00 3 оо 8 00 от 03 00 00 00 00 3 00 со С0Л 'оо 7 00 00 00 СО 7 00 9 00 оо 00 ОО 9 00 оо 00 оо 20 00 00 7 00 00 00 4 и 12 00 CO 00 оо 2 10 00 00 00 6 00 со 3 15 со 00 00 3 оо 17 00 00 00 15 17 00; 00 со Вариант 8 20 00 00 00 оо 00 ooN со 00 00 ОО оо 00 ОО 3 и 00 00 аз ОО 00 00 8 оо 00 00 10 00 8 00 00 00 оо 00 со 10 9 00 оо 00 12 оо 00 10 00 00 15 00 12 00 12 10 15 со 10 25 00 00 12 2 10 00 13 00 00 ОО 12 аэ 13 Вариант 9 оо 00 2 10 ОО 00 00 10 00 00 00 00 00 9 ОО 5 00 7 оо 00 00 10 2 00 00 00 00 00 со 10 3 00 оо 13 оо со 00 8 5 13 00 со 00 00 00 00 4 00 00 00 00 00 00 00 7 10 00 00 00 6 00 со 00 оо ОО ОО со ОО оо оо 66 00 00 00^ 00 2 15 00 оо 00 2 00 00 00 00 со 15 5 00 00 со 00 7 2 11 8 со 00 00 7 3 7 2 00 ОО 00 6 00 00 12 00 со 00 00 00 13 00 00 00 9 ОО 11 00 00 00 13 11 ^ОО ОО СО Вариант 10 7 00 оо 00 00 00 00 00 7 СЮ 9 00 00 00 11 ею 00 со 00 00 со со 00 12 00 00 8 00 00 00 со 9 оо СО 00 12 4 00 00 00 12 со 2 9 00 00 00 00 00 00 6 2 5 00 9 00 00 00 со 2 00 оо 2 ОО 00 оо 1 15 1 00 Содержание РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ МЕТОДОМ ЖОР ДАНА-ГАУССА 3 Контрольные задания для самостоятельного решения 8 РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ГЕОМЕТРИЧЕСКИМ МЕТОДОМ 9 Контрольные задания для самостоятельного решения 11 РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМПЛЕКС-МЕТОДОМ 13 Контрольные задания для самостоятельного решения 24 ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД 26 Контрольные задания для самостоятельного решения 33 ТРАНСПОРТНАЯ ЗАДАЧА 35 Контрольные задания для самостоятельного решения 42 ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ В СЕТИ 45 Контрольные задания для самостоятельного решения 49 СЕТЕВОЕ ПЛАНИРОВАНИЕ 52 Контрольные задания для самостоятельного решения 58 ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ 60 Контрольные задания для самостоятельного решения 65 ЛИТЕРАТУРА 67 Литература 1. Кузнецов, А.В., Холод, Н.И. Математическое программирова- ние. - Мн Выш. шк., 1984. 2. Балашевич, В.А. Математические методы в управление произ- водством. - Мн.:Выш. шк., 1976. 3. Банди, Б. Основы линейного программирования. - М. Радио и связь, 1988. 4. Банди, Б. Методы оптимизации. Вводный курс. - М.: Радио и связь, 1989. 5. Калихман, И.Л. Сборник задач по математическому програм- мированию. - М.:Высш. шк., 1975. 6. Сборник задач и методические указания к решению задач по ма- тематическому программированию/Е.В. Емеличева [и др.]. - Мн.: БГПА, 1996. 7. Математические методы в технико-экономических задачах / Н.Е. Гайков [и др.]. - Мн.: БПИ, 1991. Учебное издание ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ Методические указания и контрольные задания для студентов экономических специальностей БИТУ С о с т а в и т е л и : КОРЗНИКОВ Александр Дмитриевич МАТВЕЕВА Людмила Дмитриевна СМИРНОВ Михаил Борисович Технический редактор М.И. Гриневич Компьютерная верстка О.В. Дубовик Подписано в печать 29.05.2006. Формат 60x84 '/„,. Бумага офсетная. Отпечатано на ризографе. Гарнитура Тайме. Усл. печ. л. 3,95. Уч.-изд. л. 3,09. Тираж 300. Заказ 346. Издатель и полиграфическое исполнение: Белорусский национальный технический университет. ЛИ № 02330/0131627 от 01.04.2004. 220013, Минск, проспект Независимости, 65.