Основная задача линейного программирования; метод решения симплекс-метод

4. Основная задача линейного программирования Наиболее распространенный метод решения задачи линейного программирования – симплекс-метод. Для n переменных областью допустимых решений является многомерный многогранник, подобный симплексу. Оптимальное решение, как правило, это вершина (граничная точка) такого многогранника. Симплекс-метод заключается в последовательном целенаправленном обходе вершин симплекса. В каждой следующей граничной точке симплекса значение целевой функции, в общем случае, улучшается. Для применения симплекс-метода задачу следует записать в канонической форме: f=c1x1+c2x2+…+сnxnmax (4)  a11x1+a12x2+…+a1nxn=b1  a21x1+a22x2+…+a2nxn=b2  ……………………….. (5)  am1x1+am2x2+…+amnxn=bm  x10, x20,…, xn0 (6) В канонической форме записи все переменные неотрицательны, ограничениями являются уравнения, и требуется найти такие значения x1, х2,…, хn, при которых целевая функция имеет максимум. Задача (4), (5), (6) называется основной задачей линейного программирования. Задачу (4), (5), (6) имеет смысл решать, когда число уравнений в системе ограничений (5) меньше числа входящих в них неизвестных: mn, то система (5) переопределена и в общем случае не имеет решений. Правила перехода к канонической форме записи: 1 Если требуется найти минимум функции f, то заменяя функцию f на (-f), переходят к задаче максимизации. 2 Если ограничение содержит неравенство со знаком , то от него переходят к равенству, добавляя в левую часть ограничения дополнительную неотрицательную переменную. 3 Если ограничение содержит неравенство со знаком , то от него переходят к равенству, вычитая из левой части дополнительную неотрицательную переменную. 4 Если в задаче какая-либо из переменных произвольна, то от нее избавляются, заменяя ее разностью двух новых неотрицательных переменных. Пример. Записать в канонической форме задачу: f=5x1+2x2-3x3min  2x1-3x2+x310  x1-8x2-2x37  5x1+2x2+7x3=20  x10, x20 Решение: Во-первых, в целевой функции необходимо заменить знаки всех слагаемых на противоположные. Тем самым новая целевая функция f1=-5x1-2x2+3x3 исследуется на максимум. Во-вторых, из левой части первого ограничения системы необходимо вычесть дополнительную неотрицательную переменную х4. При этом ограничение переходит в равенство: 2x1-3x2+x3-x4=10. А к левой части второго ограничения системы необходимо добавить дополнительную неотрицательную переменную х5. При этом ограничение переходит в равенство: x1-8x2-2x3+x5=7. В-третьих, произвольная переменная х3 заменяется разностью двух дополнительных неотрицательных переменных х6 и х7: х3=х6-х7, х60, х70. Тогда окончательно задача примет следующий вид: f1=-5x1-2x2+3x6-3x7max  2x1-3x2+x6-x7-x4=10  x1-8x2-2x6+2x7+x5=7  5x1+2x2+7x6-7x7=20  x10, x20, x30, x40, х50, х60, х70. 5. Симплекс-метод Симплекс-метод позволяет решать задачу линейного программирования любой размерности, т.е. с любым количеством управляющих переменных. По этой причине симплекс-метод можно назвать универсальным для решения подобных задач. Симплекс-метод включает два этапа: I. Определение начального решения, удовлетворяющего ограничениям (5), (6) II. Последовательное улучшение начального решения и получение оптимального решения задачи (4), (5), (6). Алгоритм решения задачи (4), (5), (6) симплекс-методом рассмотрим на конкретном примере: Пример. Предприятие рекламирует свою продукцию с использованием 4-х источников массовой информации: телевидения, радио, газет и расклейки объявлений. Анализ рекламной деятельности в прошлом показал, что эти средства приводят к увеличению прибыли соответственно на 10, 5, 7 и 4 у.е., в расчете на 1 у.е., затраченную на рекламу. На рекламу выделено 50000 у.е. Администрация предприятия не намерена тратить на телевидение более 40%, а на радио и газеты – более 50% от общей суммы выделенных средств. Как следует предприятию организовать рекламу, чтобы получить максимальную прибыль, и какова при этом максимальная прибыль? Решение: Пусть x1 – количество средств, вложенных в рекламу на телевидение; x2 – количество средств, вложенных в рекламу на радио; x3 – количество средств, вложенных в рекламу в газетах; x4 – количество средств, вложенных в расклейку объявлений. P=10x1+5x2+7x3+4x4max (Целевая функция задачи – функция прибыли) x1+x2+x3+x450000  x120000  x2+x325000  x10, x20, x30, x40. Ограничения задачи – это ограничения по общей сумме выделенных средств, по количеству средств, предусмотренных на рекламу по телевидению, на радио и в газетах, и условия неотрицательности управляющих переменных. Для того чтобы иметь возможность решить задачу симплекс-методом, необходимо переписать математическую модель в канонической форме. В данной задаче целевая функция уже исследуется на максимум, и в ней не предполагается никаких изменений. Чтобы специальные ограничения (неравенства со знаком ) переписать в виде равенств, нужно в левую часть каждого из ограничений добавить некоторую неотрицательную переменную величину (соответственно х5, х6, х7): Переход к канонической форме: P=10x1+5x2+7x3+4x4max  x1+x2+x3+x4+х5=50000  x1+х6=20000  x2+x3+х7=25000  x10, x20, x30, x40, x50, x60, x70. Таким образом, количество переменных в задаче возросло до семи. Решение симплекс-методом: 1 Получение начального решения. Первый этап решения задачи симплекс-методом предполагает распределение всех переменных на две категории: базисные и свободные переменные. Базисной называется переменная, которая входит с коэффициентом 1 только в одно уравнение системы ограничений и не входит в остальные уравнения системы. Из каждого уравнения необходимо выбрать одну базисную переменную. Таким образом, количество базисных переменных в задаче равно числу уравнений в системе ограничений. Остальные переменные задачи называются свободными. В рассматриваемой задаче из первого уравнения можно выбрать в качестве базисной переменной х4 или х5, так как этих переменных нет в двух других уравнениях, а в первом уравнении эти переменные записаны с коэффициентами 1. Выберем, например, х5. Аналогично, из второго и третьего уравнений выбираем х6 и х7. Итак, x5, x6, x7 – базисные переменные Тогда x1, x2, x3, x4 – свободные переменные Все свободные переменные полагаются равными 0, а базисные переменные равны правым частям соответствующих ограничений (уравнений). С учетом последнего начальное решение задачи будет иметь вид: X0=x1=0, x2=0, x3=0, x4=0, x5=50000, x6=20000, x7=25000 – начальное решение. 2 Выражение целевой функции Р только через свободные переменные. Другими словами, целевая функция не должна содержать ни одной базисной переменной. Если она содержит базисную переменную, эту базисную переменную необходимо выразить из соответствующего уравнения системы через свободные переменные и подставить это выражение в целевую функцию вместо этой базисной переменной. В рассматриваемой задаче целевая функция Р изначально не содержит базисных, т.е. уже выражена через свободные переменные. 3 Проверка решения на оптимальность. Составляется симплекс-таблица. В левой колонке симплекс-таблицы указываются базисные переменные, в верхней строке таблицы перечисляются все переменные задачи по порядку, в колонке свободных членов – правые части соответствующих ограничений. В i-й строке j-м столбце стоит коэффициент при j-й переменной в i-м ограничении. В последней строке стоит коэффициент с противоположным знаком при j-й переменной в целевой функции Р. В последнем столбце последней строки стоит значение свободного члена, входящего в целевую функцию. базисные переменные коэффициенты при переменных свободные члены х1 x2 х3 x4 х5 х6 х7 х5 1 1 1 1 1 50000 х6 1 1 20000 х7 1 1 1 25000 Р -10 -5 -7 -4 Для проверки решения на оптимальность просматривается последняя строка:  Если коэффициенты, стоящие при свободных переменных, неотрицательны, то полученное решение оптимально. При этом если эти коэффициенты строго положительны, то полученное решение единственно. Если среди неотрицательных коэффициентов встречается хотя бы один нулевой, то задача имеет бесконечное множество решений.  Если в последней строке имеется хотя бы один отрицательный коэффициент, а в соответствующем этому коэффициенту столбце нет ни одного положительного элемента, то задача не имеет решений.  Если в последней строке имеется хотя бы один отрицательный коэффициент (из коэффициентов при свободных переменных), а в соответствующем этому коэффициенту столбце имеется хотя бы один положительный элемент, то полученное решение может быть улучшено. Переходят к шагу 4. В нашем случае в последней строке имеются четыре отрицательных коэффициента, а в соответствующих столбцах есть положительные числа. Значит, начальное решение может быть улучшено. 4 Получение нового решения. Получение нового решения связано с изменением состава базисных переменных. По определенному правилу в список базисных вводится переменная, ранее считавшаяся свободной. Взамен одна из «старых» базисных переменных должна стать свободной (также по определенному правилу). Напомним, что количество базисных переменных в задаче неизменно. 1) Выбор переменной, вводимой в список базисных переменных: Просматривается последняя строка. Среди элементов этой строки выбирается максимальный по абсолютной величине (т.е. без учета знака) отрицательный элемент. Столбец, в котором стоит этот элемент, называется разрешающим. Переменная, стоящая в этом столбце, вводится в список базисных переменных. Замечание: Если возникает неопределенность в выборе разрешающего столбца, т.е. оказывается несколько равных максимальных по абсолютной величине отрицательных элементов в последней строке, то в качестве разрешающего можно выбирать любой столбец, в котором стоит этот элемент. 2) Выбор переменной, выводимой из списка базисных переменных: Находят отношение элементов столбца свободных членов к элементам разрешающего столбца. При делении на отрицательный элемент или на 0 результат полагают равным +. Среди этих отношений находят минимальное. Строка, соответствующая минимальному отношению, называется разрешающей. Базисная переменная, стоящая в этой строке, выводится из списка базисных переменных. Замечание: Если возникает неопределенность в выборе разрешающей строки, т.е. оказывается несколько равных минимальных отношений элементов столбца свободных членов к элементам разрешающего столбца, то следует выбирать ту строку, для которой отношение элементов следующего столбца к элементам разрешающего столбца является минимальным. Если при этом снова оказываются равные минимальные отношения, то составляют отношения элементов следующего столбца, и так до тех пор, пока разрешающая строка не определится однозначно. Элемент симплекс-таблицы, стоящий на пересечении разрешающей строки и разрешающего столбца, называется разрешающим элементом. В нашей задаче разрешающим столбцом является первый столбец, так как из чисел –10, –5, –7 и –4 последней строки наибольшее число без учета знака (10) стоит в первом столбце. Выделим разрешающий столбец серым цветом. Разделим свободные члены на элементы выделенного (разрешающего) столбца. Результаты оформим дополнительным столбцом справа, как продолжение симплекс-таблицы. Из трех полученных значений 50000, 20000 и + выбираем наименьшее – 20000 и выделяем серым цветом разрешающую (вторую) строку. Элемент на пересечении выделенных столбца и строки (равен 1) – разрешающий элемент таблицы. базисные переменные коэффициенты при переменных свободные члены х1 x2 х3 x4 х5 х6 х7 х5 1 1 1 1 1 50000 50000/1=50000 х6 1 1 20000 20000/1=20000 х7 1 1 1 25000 25000/0=+ Р -10 -5 -7 -4 Таким образом, переменную х1 надо ввести в состав базисных переменных, а х6 – вывести из состава базисных. 3) Выполнение симплекс-преобразования и переход к новой симплекс-таблице. После того как новый список базисных переменных определен, составляется новая симплекс-таблица по следующим правилам: «Шапка» таблицы, количество строк и столбцов сохраняются. В списке базисных переменных вместо х6 указывается х1. Заполнение таблицы начинается с заполнения выделенной строки по правилу: все элементы выделенной строки делятся на разрешающий элемент. В нашем случае новая таблица заполняется, начиная со второй строки: 1/1=1, 0/1=0, 0/1=0, 0/1=0, 0/1=0, 1/1=1, 0/1=0, 20000/1=20000 (делим всегда на 1, так как это – разрешающий элемент таблицы!) Следующим шагом заполняем нулями выделенный столбец (кроме клетки второй строки, в которой уже записана 1) Промежуточный результат: базисные переменные коэффициенты при переменных свободные члены х1 x2 х3 x4 х5 х6 х7 х5 х1 1 1 20000 х7 Р Все остальные элементы симплекс-таблицы, включая коэффициенты целевой функции и свободные члены, пересчитываются по правилу треугольника: Для получения элемента новой симплекс-таблицы надо от элемента предыдущей симплекс-таблицы, стоящего на том же месте, отнять следующее выражение: произведение элемента разрешающего столбца, стоящего в одной строке с данным элементом, на элемент разрешающей строки, стоящий в одном столбце с данным элементом, деленное на разрешающий элемент. Для этого преобразования можно предложить следующую логическую формулу: новый элемент =старый элемент - выделенный элемент, стоящий в одной строке со старым элементом  выделенный элемент, стоящий в одном столбце со старым элементом разрешающий элемент Например, элемент на пересечении первой строки и второго столбца: а12 =1-(10)/1=1. Аналогично рассчитываются другие элементы: а13 =1-(10)/1=1 а14 =1-(10)/1=1 а15 =1-(10)/1=1 а16 =0-(11)/1=-1 а17 =0-(10)/1=0 b1=50000-(120000)/1=30000 а32 =1-(00)/1=1 а33 =1-(00)/1=1 а34 =0-(00)/1=0 а35 =0-(00)/1=0 а36 =0-(01)/1=0 а37 =1-(00)/1=1 b3=25000-(020000)/1=25000 а42 =-5-(-100)/1=-5 а43 =-7-(-100)/1=-7 а44 =-4-(-100)/1=-4 а45 =0-(-100)/1=0 а46 =0-(-101)/1=10 а47 =0-(-100)/1=0 b4=0-(-1020000)/1=200000 Итак, получаем новую таблицу: базисные переменные коэффициенты при переменных свободные члены х1 x2 х3 x4 х5 х6 х7 х5 1 1 1 1 -1 30000 х1 1 1 20000 х7 1 1 1 25000 Р -5 -7 -4 10 200000 Новое решение имеет вид: все свободные переменные полагаются равными 0, а все базисные переменные равны свободным членам, стоящим в одной строке с ними. После построения новой симплекс-таблицы необходимо вернуться к шагу 3. Новое решение задачи: X1=x1=20000, x2=0, x3=0, x4=0, x5=30000, x6=0, x7=25000. Р1=200000 Новое решение не оптимально, так как последняя строка содержит отрицательные числа. Продолжаем оптимизацию. базисные переменные коэффициенты при переменных свободные члены х1 x2 х3 x4 х5 х6 х7 х5 1 1 1 1 -1 30000 30000/1=30000 х1 1 1 20000 20000/0=+ х7 1 1 1 25000 25000/1=25000 Р -5 -7 -4 10 200000 х3 надо ввести в состав базисных переменных; х7 надо вывести из состава базисных переменных; а33=1 – разрешающий элемент. Пересчитывая по формулам симплекс-преобразований все коэффициенты таблицы, получаем новую таблицу: базисные переменные коэффициенты при переменных свободные члены х1 x2 х3 x4 х5 х6 х7 х5 1 1 -1 -1 5000 х1 1 1 20000 х3 1 1 1 25000 Р 2 -4 10 7 375000 X2=x1=20000, x2=0, x3=25000, x4=0, x5=5000, x6=0, x7=0 – новое решение. Р2=375000 Новое решение не оптимально, так как в последней строке среди коэффициентов при свободных переменных есть отрицательное число. Продолжаем оптимизацию. базисные переменные коэффициенты при переменных свободные члены х1 x2 х3 x4 х5 х6 х7 х5 1 1 -1 -1 5000 5000/1=5000 х1 1 1 20000 20000/0=+ х3 1 1 1 25000 25000/0=+ Р 2 -4 10 7 375000 х4 надо ввести в состав базисных переменных; х5 надо вывести из состава базисных переменных; а14=1 – разрешающий элемент. Пересчитывая по формулам симплекс-преобразований все коэффициенты таблицы, получаем новую таблицу: базисные переменные коэффициенты при переменных свободные члены х1 x2 х3 х4 х5 х6 х7 х4 1 1 -1 -1 5000 х1 1 1 20000 х3 1 1 1 25000 Р 2 4 6 3 395000 X=x1=20000, x2=0, x3=25000, x4=5000, x5=0, x6=0, x7=0 – оптимальное решение, т.к. все числа в последней строке неотрицательны. Это решение единственно, так как все коэффициенты при свободных переменных строго положительны. Р=395000. Ответ: Для получения максимальной прибыли в размере 395000 у.е. надо распределить средства следующим образом: 20000 у.е. вложить в рекламу на телевидении; 25000 у.е. вложить в рекламу в газетах и 5000 у.е. вложить в рекламу, организованную с помощью расклейки объявлений. Рекламу на радио организовывать не следует.