Езу9у. Учебное пособие Рекомендовано методическим советом Уральского федерального университета в качестве учебного пособия для студентов вуза, обучающихся по направлениям подготовки
 Скачать 5.85 Mb.
|
|
Пример 5.7. Найти решение следующей задачи линейного программиро- вания: 1 2 3 4 ( ) 4 3 2 min, Z X x x x x = + + + → 1 2 3 4 1 2 3 4 2 5 1, : 2 3 6 2 3, 0, 1,4. i x x x x L x x x x x j + + + ≥ + + − ≥ ≥ = 152 Решение. Приведем данную задачу в канонический вид, введя две допол- нительные переменные: 1 2 3 4 ( ) 4 3 2 min, Z X x x x x = + + + → 1 2 3 4 5 1 2 3 4 6 2 5 1, 2 3 6 2 3, 0, 1,6. j x x x x x x x x x x x j + + + − = + + − − = ≥ = Единичной подматрицы у системы ограничений нет, поэтому простой симплекс-метод неприменим. Составим двойственную задачу к исходной: 1 2 3 max, y y + → 1 2 1 2 1 2 1 2 1 2 2 1, 2 3 4, : 5 6 3, 2 2, 0, 0. y y y y L y y y y y y ∗ + ≤ + ≤ + ≤ − ≤ ≥ ≥ Введем дополнительные переменные и составим каноническую форму двойственной задачи: 1 2 3 max, y y + → 1 2 3 1 2 4 1 2 5 1 2 6 2 1, 2 3 4, 5 6 3, 2 2, 0, 1,6. i y y y y y y y y y y y y y i + + = + + = + + = − + = ≥ = Предлагаем читателю самостоятельно решить полученную задачу симплекс- методом и убедиться, что на последнем шаге симплекс-таблица будет выглядеть следующим образом (табл. 5.4). Таблица 5.4 Z * 1/2 0 3/2 0 0 0 3/2 y 2 1/2 1 1/2 0 0 0 1/2 y 4 1/2 0 –3/2 0 0 0 5/2 y 5 0 2 0 0 1 1 0 y 6 3 2 0 0 0 0 3 Из симплексной таблицы находим решение двойственной задачи: 1 y = 0; 2 y = 0,5; * Z = 1,5, а по сильной теореме двойственности * Z Z = = 1,5. Оптималь- 153 ные значения переменных в двойственной задаче находим в Z-строке в столбцах у 3 , у 4 , у 5 , у 6 : x 1 = 1,5; x 2 = x 3 = x 4 = 0. 5.4. Анализ чувствительности задачи линейного программирования Как было сказано выше, задача линейного программирования зависит от условий, которые задаются при составлении модели. При этом с течением времени эти условия могут поменяться, что может привести к недопустимости текущего оптимального решения. Например, подобная ситуация возможна при изменении правых частей ограничений или введением в множество огра- ничений задачи нового ограничения. В связи с этим очень важно исследовать влияние изменения доступности ресурсов (запасов сырья), что возможно сде- лать при помощи определения интервалов допустимости для правых частей ограничений. В этом нам поможет следующее утверждение. Теорема 5.5 (об оценках).Компоненты оптимального решения двойст- венной задачи равны значениям частных производных линейной функции Z(b 1 , b 2 , …, b m ) по соответствующим аргументам, то есть: , 1, . i i Z y i m b ∂ = = ∂ Равенство в теореме об оценках означает, что изменение значений, стоя- щих в правых частях ограничений, приводит к увеличению или уменьшению оптимального значения целевой функции. Это изменение определяется вели- чиной i y и может быть охарактеризовано лишь тогда, когда при изменении величин b i значения переменных i y в оптимальном плане соответствующей двойственной задачи остаются неизменными. Поэтому представляет интерес определить такие интервалы изменения каждого из свободных членов системы ограничений задачи линейного программирования, в которых оптимальный план двойственной задачи не меняется. Пример 5.8. Для следующей задачи из модели планирования производства 1 2 ( ) 2 3 max, Z X x x = + → 1 2 1 2 2 1 1 2 3 18, 2 16, : 5, 3 21, 0, 0 x x x x L x x x x + ≤ + ≤ ≤ ≤ ≥ ≥ 154 найти интервалы устойчивости двойственных оценок по отношению к изме- нениям запасов сырья каждого вида. Решение. Предположим, что запасы сырья, равные первоначально 18, 16, 5 и 21 ед., изменились на величины ∆b 1 , ∆ b 2 , ∆ b 3 , ∆ b 4 соответственно. Составим двойственную задачу к исходной: 1 2 3 4 ( ) 18 16 5 21 min, Z Y y y y y ∗ = + + + → 1 2 4 1 2 3 2 3 2, 3 3, 0, 1,4. i y x y y y y y i + + ≥ + + ≥ ≥ = Тогда затраты на сырье составят: 1 1 2 2 3 3 4 4 ( ) ( ) ( ) 18 16 5 21 ( ) . Z b y b y b y b y ∗ = + ∆ + + ∆ + + ∆ + + ∆ Заменяя переменные y 1 и y 2 их выражениями через небазисные переменные оптимального решения, имеем: 1 3 4 5 6 4 2 3 1 2 , 5 5 5 5 5 y y y y y = − + − + 2 3 4 5 6 3 1 9 3 1 . 5 5 5 5 5 y y y y y = + − + − После преобразований получим: 1 2 1 2 3 3 1 2 4 4 1 2 5 1 2 6 4 3 2 1 24 1 5 5 5 5 3 9 1 3 2 1 3 6 4 5 5 5 5 5 5 Z b b b b b y b b b y b b y b b y = + ∆ + ∆ + − ∆ + ∆ + ∆ + + + ∆ − ∆ + ∆ + − ∆ + ∆ + + ∆ − ∆ Для того чтобы оптимальные теневые цены сырья остались неизменными и при изменении запасов сырья, достаточно, чтобы коэффициенты при неба- зисных переменных оставались неотрицательными, то есть: 1 2 3 1 2 4 1 2 1 2 2 1 1 0, 5 5 3 9 3 0, 5 5 1 3 6 0, 5 5 2 1 4 0. 5 5 b b b b b b b b b b − ∆ + ∆ + ∆ ≥ + ∆ − ∆ + ∆ ≥ − ∆ + ∆ ≥ + ∆ − ∆ ≥ (5.9) 155 Предположим, что изменяется только запас первого вида сырья, а осталь- ные остаются неизменными: ∆b 2 = ∆b 3 = ∆b 4 = 0. Тогда вышеприведенная система примет вид: 1 1 1 1 1 0,4 0, 3 0,6 0, 6 0,2 0, 4 0,4 0. b b b b − ∆ ≥ + ∆ ≥ − ∆ ≥ + ∆ ≥ Преобразовав, имеем: 1 1 1 1 2,5, 5, 30, 10. b b b b ∆ ≤ ∆ ≥ − ∆ ≤ ∆ ≥ − Откуда получаем следующие ограничения: и или 1 1 1 1 1 5 2,5 18 5 18 2,5 13 20,5. b b b b b − ≤ ∆ ≤ − ≤ + ∆ ≤ + ≤ + ∆ ≤ Иными словами, при неизменности теневых цен сырья запас сырья пер- вого вида может изменяться в пределах от 13 до 20,5 ед. Аналогично можно получить, что 2 2 3 3 4 4 2 11 17 , 4 , 18 3 b b b b b b ≤ + ∆ ≤ ≤ + ∆ < +∞ ≤ + ∆ < +∞ Таким образом, при изменении запаса только одного первого вида сырья в пределах от 13 до 20,5 ед., или только второго вида в пределах от 11 до 17 2/3 ед., или только третьего вида в пределах не менее 4 ед., или четвертого — в пределах не менее 18 ед. оптимальное решение двойственной задачи остается прежним. Стоит отметить, что если запасы сырья изменяются одновременно, то ис- следование устойчивости теневых цен усложняется, поскольку в данном случае нужно найти решение системы неравенств (5.9). При этом всегда можно прове- рить, удовлетворяют ли конкретные изменения запасов ресурсов системе (5.9). Заметим, что решить задачу линейного программирования и проанали- зировать полученные оптимальные решения возможно в программе Microsoft Excel, используя надстройку «поиск решения», но заменить человека полностью не получится, так как экономическую интерпретацию решения может сделать только человек. Как правило, полученное решение и его анализ оформляются также человеком, им же делаются выводы и приводятся рекомендации. В боль- 156 ших компаниях решением подобного рода задач занимается много отделов: статистический, планирования, IT и т. п. Задачи для самостоятельного решения 5.1. Для данной задачи линейного программирования составить двойст- венную задачу и решить обе графически. 1 2 ( ) 2 7 max, Z X x x = + → 1 2 1 2 2 3 14, 8; 0, 1,2. j x x x x x j − + ≤ + ≤ ≥ = 5.2. Решить данную задачу графически. Составить для нее двойственную задачу и найти ее решение, используя условия дополняющей нежесткости. 1 2 ( ) 3 4 max, Z X x x = + → 1 2 1 2 4 2 20, 5 20, 4 16; 0, 1,2. j x x x x x j + ≤ ≤ ≤ ≥ = 5.3. Решить данную задачу симплексным методом. Составить для нее двой- ственную задачу и найти ее решение, используя теоремы двойственности. 1 2 ( ) 2 8 max, Z X x x = + → 1 2 1 2 2 1 2 12, 2 12, 5, 2 10; 0, 1,2. j x x x x x x x j + ≤ + ≤ ≤ ≤ ≥ = 5.4. Для данной задачи составить двойственную задачу и решить ее сим- плексным методом. Используя теоремы двойственности, получить решение исходной задачи. 1 2 ( ) 5 3 min, Z X x x = + → 157 1 2 1 2 1 2 6 5 17, 2 34, 4 9 17; 0, 1,2. j x x x x x x x j − ≥ + ≤ − + = ≥ = 5.5. Решить данную задачу симплексным методом. Составить для нее двой- ственную задачу и найти ее решение, используя теоремы двойственности. 1 2 4 ( ) 2 max, Z X x x x = + + → 1 2 3 4 1 2 3 2 3 4 2, 2 1, 2 2 2; 0, 1,4. j x x x x x x x x x x x j + + + = + + = + + = ≥ = 5.6. Для данной задачи составить двойственную задачу и проверить опти- мальность заданных векторов для этих задач. 1 2 3 ( ) 10 8 max, Z X x x x = + + → 1 2 3 1 2 3 4 2, 2 0; 0, 1,3. j x x x x x x x j + + = + − = ≥ = 9 7 (1, 0,1), , 2 2 X Y ∗ ∗ = = − 5.7. Для данной задачи составить двойственную задачу. Решить одну из них и получить решение второй, используя теоремы двойственности. 1 2 3 4 ( ) 12 12 max, Z X x x x x = + − + → 1 2 4 1 2 3 4 3 3 2, 3 2 4; 0, 1,4. j x x x x x x x x j − + = + + + = ≥ = 5.8. Для данной задачи составить двойственную задачу. Решить одну из них и получить решение второй, используя теоремы двойственности. 1 2 3 4 ( ) 10 5 6 12 min, Z X x x x x = + + + → 158 1 2 3 4 1 2 3 4 2 2 2 2, 5 3 3 4; 0, 1,4. j x x x x x x x x x j + − + = − + + = ≥ = 5.9. Для производства настольных ламп и светильников используют сырье четырех видов. Запас материалов, технологические коэффициенты и прибыль от продажи одной лампы и одного светильника заданы в таблице. Вид материала Вид товара Объем ресурсов Лампа Светильник Металл 0 4 120 Пластик 4 0 180 Стекло 2 2 120 Латунь 1 2 80 Прибыль на ед. товара, ден. ед. 200 300 max Решить следующие задачи: а) найти план выпуска изделий, при котором прибыль от реализации из- делий будет максимальной; б) определить цены, по которым выгодно продать сырье, чтобы при этом получить выручку не меньше, чем от реализации готовых изделий. 5.10. Для изготовления четырех видов продукции используется три вида сырья. Расход сырья на единицу каждого вида продукции и запас сырья заданы в таблице. Вид сырья Вид продукции Объем ресурсов I II III IV S 1 1 0 2 1 180 S 2 0 1 3 2 210 S 3 4 2 0 4 800 Прибыль на ед. товара, ден. ед. 9 6 4 7 max Решить следующие задачи: а) найти план выпуска изделий, при котором прибыль от реализации про- дукции будет максимальной; б) определить цены, по которым выгодно продать сырье, чтобы при этом получить выручку не меньше, чем от реализации готовых изделий; в) как изменится общая стоимость изготовляемой продукции, определенной оптимальным планом при уменьшении сырья S 1 на 60 ед., увеличении сырья S 2 на 120 ед. и увеличении сырья S 3 на 160 ед. Ответы к задачам для самостоятельного решения 5.1. max min 46 Z Z ∗ = = при X * = (2, 6), Y * = (1, 4). 5.2. max min 25 Z Z ∗ = = при X * = (3, 4), 3 5 , 0, 4 8 Y ∗ = 5.3. max min 44 Z Z ∗ = = при X * = (2, 5), Y * = (0, 2, 4, 0). 5.4. max min 50 Z Z ∗ = = при X * = (7, 5), 57 43 , 0, 34 34 Y ∗ = 5.5. max min 5 2 Z Z ∗ = = при 1 1 , , 0,1 , 2 2 X ∗ = 3 1 1 , , 2 2 2 Y ∗ = − 5.6. Решения оптимальные, max min 9. Z Z ∗ = = 5.7. max min 10 Z Z ∗ = = при 2 ,2,0,0 , 3 X ∗ = Y * = (3, 1). 5.8. max min 15 Z Z ∗ = = при 1 7 3 0, 0, , , , 3 . 6 6 2 X Y ∗ ∗ = = 5.9. а) x 1 = 40, x 2 = 20, Z max = 14 000 (ден. ед.); б) y 1 = 0, y 2 = 0, 3 1 , 2 y = y 4 = 1, min 14 000 Z ∗ = (ден. ед.). 5.10. а) x 1 = 95, x 2 = 210, x 3 = 0, x 4 = 0, Z max = 2 115 (ден. ед.); б) y 1 = 0, 2 3 , 2 y = 3 9 , 4 y = min 2115 Z ∗ = (ден. ед.); в) указанное изменение запасов ресурсов приведет к построению нового оптимального плана производства, при котором прибыль увеличится на 540 (ден. ед.). 160 6. ТРАНСПОРТНАЯ ЗАДАЧА 6.1. Постановка модели транспортной задачи Транспортной задачей называется разновидность задач линейного про- граммирования. Она была сформулирована с целью разработки наиболее рациональных способов транспортирования товаров, устранения повторных, неоптимальных, чрезмерно дальних перевозок, а также с целью определе- ния объемов перевозок с минимальной суммарной стоимостью. При этом должны учитываться ограничения, накладываемые на объемы грузов, име- ющихся в пунк те отправления (предложение), и ограничения, учитывающие потребность грузов в пунктах назначения (спрос). Благодаря полученному в транспортной задаче решению, экономится время продвижения товаров, уменьшаются затраты предприятий на процессы, связанные со снабжением сырья, материалов, оборудования и т. п. Приведем общую постановку транспортной задачи. Имеется m пунктов производства (отправления) однородного продукта с объемами производства a 1 , a 2 , …, a m и n пунктов потребления (назначения) с объемами потребления b 1 , b 2 , …, b n . Известна стоимость перевозки единицы продукта от каждого i-го пункта производства до каждого j-го пункта потребле- ния: c ij , 1, , i m = , . 1 j n = Каждый элемент c ij можно представить в виде матрицы, называемой матрицей перевозок (матрицей цен): 11 12 1 21 22 2 1 2 n n m m mn c c c c c c C c c c = Требуется составить план перевозок так, чтобы запасы груза у поставщиков были вывезены, потребности всех потребителей в грузе были удовлетворены 161 и суммарная стоимость перевозок была минимальной. Как правило, условия транспортной задачи оформляют в виде распределительной таблицы (табл. 6.1). Таблица 6.1 Пункты отправления Пункты назначения Объемы поставок 1 2 … j … n 1 c 11 c 12 … c 1j … c 1n a 1 2 c 21 c 22 … c 2j … c 2n a 2 … … … … … … … … i c i1 c i1 … c ij … c i1 a i … … … … … … … … m c m1 c m2 … c mj … c mn a m Объемы потребления b 1 b 2 … b j … b n Обозначим x ij — количество груза, перевозимого из каждого i-го пункта производства до каждого j-го пункта потребления, 1, , i m = , . 1 j n = Тогда, учи- тывая, что все грузы должны быть перевезены и все потребности должны быть удовлетворены, а стоимость перевозки можно выразить в виде двойной суммы, математическая модель транспортной задачи имеет вид: )= 1 1 ( min, m n ij ij i j Z X c x = = → ∑∑ 1 1 , , 0, 1, , 1, . n ij i j m ij j i ij x a x b x j m i n = = = = ≥ = = ∑ ∑ Различают два типа транспортных задач. Если суммарные запасы продукта поставщиков равны суммарным объемам потребления, то есть: 1 1 , m n i j i j a b = = = ∑ ∑ то это задача закрытого типа (замкнутая, сбалансированная). В противном случае задачу называют задачей открытого типа (несбалансированной). Очень важно отметить, что в большинстве учебников авторы, как правило, изначально задают матрицу цен, но в реальной жизни часто может встретиться ситуация, когда изначально дана не матрица цен, а матрица расстояний от каж- |