Линейное программирование.

Введение Моделирование в научных исследованиях применялось еще в глубокой древности и постепенно захватывало все новые области научных знаний: техническое конструирование, строительство и архитектуру, астрономию, физику, химию, биологию и, наконец, общественные и экономические науки. Большие успехи и признание практически во всех отраслях современной науки принес методу моделирования XX век. Создание электронно-вычислительных машин обрабатывающих большой объем информации позволило решать задачи, требующие огромного объема вычислений, разработать численные методы решения новых задач. Появились новые математические дисциплины, одной из которых является математическое программирование. Математическое программирование – это раздел математики, занимающийся решением задач нахождения экстремумов функции нескольких переменных с ограничениями на область допустимых значений этих переменных. Термин «программирование» появился в связи с тем, что в английском языке слово «programming» означает планирование, составление планов или программ. Наиболее разработанным разделом математического программирования является линейное программирование. В 1931 г. венгерский математик Б. Эгервари решил задачу линейного программирования, имеющую название «проблема выбора». Этот метод решения получил название «венгерский метод». В 1939 г. советский академик Л.В. Канторович, лауреат Нобелевской премии, нашел общий метод решения задач (метод разрешающих множителей), связанных с составлением оптимального плана при организации производственных процессов. В 1949 г. Л.В. Канторович и М.К. Гавурин разработали метод потенциалов, используемый при решении транспортных задач. В 1947 г. американский математик Дж. Данциг предложил основной метод решения задач линейного программирования – симплекс-метод. Сам термин линейное программирование впервые появился в 1951 г. Одновременно с разработкой методов решения задач линейного программирования, уделялось большое внимание задачам нелинейного программирования, квадратичного программирования, динамического программирования, теории игр и т.д. Организация современного производства требует не только наличия современных станков и оборудования, но и разработки новых технологических процессов и современных методов управления производством. Для решения поставленных задач разрабатываются математические модели, позволяющие найти наилучшее решение поставленной задачи. Составители: Балашов А.Н. Термин модель широко используется в различных сферах человеческой деятельности и имеет множество смысловых значений. В роли модели может выступать совокупность формул, макет реального объекта, рисунок и т.д. Для каждого объекта можно создать несколько моделей. Модель – это такой материальный или мысленно представляемый объект, который в процессе исследования замещает объект – оригинал так, что его непосредственное изучение дает новые знания об объекте – оригинале. Под моделированием понимается процесс построения, изучения и применения моделей. Необходимость использования метода моделирования определяется тем, что многие объекты непосредственно исследовать или вовсе невозможно, или же это исследование требует много времени и средств. Математическое моделирование можно разбить на этапы [1]: На первом этапе конструируется модель исходного объекта. Построение модели предполагает наличие определенных сведений об объекте. Любая модель воспроизводит оригинал в ограниченном виде, отображая лишь некоторые существенные характеристики исходного объекта. На втором этапе процесса моделирования модель выступает как самостоятельный объект исследования. В частности, производят модельные эксперименты. На третьем этапе осуществляют перенос знаний с модели на оригинал, в результате чего формируются новые знания об исходном объекте. На четвертом этапе осуществляется проверка полученных с помощью модели знаний на практике и их использование как для улучшения построенной теории реального объекта, так и для его целенаправленного преобразования или управления им. Моделирование представляет собой циклический процесс, за первым четырехэтапным циклом может последовать второй, третий и т.д. При этом знания об исследуемом объекте расширяются и упорядочиваются, а первоначально построенная модель постепенно совершенствуется. Составители: Балашов А.Н. Глава 1. Математическое программирование §1. Линейное программирование 1.1. Математическая модель общей задачи линейного программирования Математические методы и модели применяются для отыскания оптимальных решений в управлении. Всякое управление предполагает наличие цели, ради реализации которой осуществляется управление. Развитие достаточно мощной вычислительной техники, способной за короткое время переработать значительные массивы информации, а также развитие математических моделей способствовало преобразованию искусства принятия решения в науку, доступную каждому, кто овладел ее принципами и методологией. Общая схема составления моделей задач принятия решений состоит в следующем: 1. Необходимо выделить набор параметров, которые описывают процесс принятия решения. Выбор тех или иных численных значений для параметров набора эквивалентен принятию того или иного решения. Параметры эти принято называть параметрами управления, число их может быть весьма значительным. 2. Следует выделить и четко сформулировать цель, ради достижения которой принимается то или иное решение. Как правило, целевую установку процесса принятия решения представляют в виде некоторой функции, зависящей от параметров управления, значения которой дают оценку качества принятого решения. Эту функцию называют целевой функцией задачи или показателем качества ее решения. Целевая функция дает возможность сравнивать два различных решения: если при одном наборе параметров значение целевой функции меньше, чем при другом (или больше, в зависимости от задачи), то одно решение будет предпочтительнее другого. 3. В задачах принятия решений не любой набор параметров управления может быть практически реализован. Выделение среди всех решений множества возможных решений также является важным этапом составления математической модели для исследуемой задачи. Допустим, что предметом нашего исследования является некоторое предприятие, производящее продукцию одного вида. Назовем эту продукцию конечной. Производство конечной продукции осуществляется с помощью одного из заранее отработанных технологических способов. Каждый технологический способ характеризуется количеством конечной продукции, выпускаемой в единицу времени, и всех расходуемых при этом ресурсов. Составители: Балашов А.Н. Сформулируем условие задачи. Необходимо составить такой план использования различных технологических способов, при котором предприятие выпускало бы максимально возможное количество конечной продукции в пределах имеющихся исходных запасов. Формализуем условия задачи в общем виде. Пусть n – число отработанных технологических способов производства; j – это j-й технологический способ производства ( j  1, n) ; m – число исходных ресурсов, необходимых для производства; i – это i-й ресурс (i  1, m) ; c j – количество продукции, производимое по j-му технологическому способу в течение единицы времени; aij – расход i-го исходного ресурса за единицу времени при использовании j-го технологического способа; bi – запас i-го исходного ресурса, которым располагает предприятие. Составим математическую модель задачи. Для этого необходимо выполнить три пункта: 1. Выберем параметры управления (то, что мы можем менять в процессе производства в рамках поставленной задачи). В рамках поставленной задачи bi , aij , c j , m и n (см. выше) мы не можем менять. В процессе производства мы можем менять только время, в течение которого предприятие выпускало продукцию, используя определенный j-й технологический способ производства. Поэтому, пусть x j – это время, в течение которого предприятие выпускало продукцию, используя определенный j-й технологический способ производства. Следовательно, x1 , x2 , ..., xn – искомый набор параметров управления, а составленный план производства эквивалентен выбору конкретных значений параметров xj. 2. Найдем целевую функцию. По условию задачи необходимо составить такой план производства, при котором предприятие выпускало бы максимально возможное количество конечной продукции. Следовательно, целевая функция должна отражать количество выпускаемой продукции n f ( x)   c j x j  c1 x1  c 2 x 2  ...  c n x n . j 1 Для нахождения оптимального решения необходимо максимизировать целевую функцию f ( x)  max . 3. Поскольку запасы ресурсов ограничены, то на параметры управления накладываются ограничения. Найдем множество допустимых решений. Расход i-го исходного ресурса при работе предприятия по плану ( x1 , x2 , ..., xn ) можно найти по формуле ai1 x1  ai 2 x2  ...  ain xn . Расход i-го Составители: Балашов А.Н. ресурса не должен превышать n ai1 x1  ai 2 x2  ...  ain xn   aij x j  bi . имеющихся Необходимо запасов bi , добавить т. е. еще j 1 ограничения x j  0 , т. к. время использования технологических способов не может быть отрицательным. В результате мы имеем математическую модель задачи: n f ( x)   c j x j  max , j 1 n n n a x  b , a x  b , ...,  am j x j  bm ,  1 j j 1  2j j 2  j 1 j 1 j 1  x j  0, j  1, n.  Целевая функция модели и ограничения линейно зависят от параметров управления. Подобные модели принято называть задачами линейного программирования (ЗЛП). Обычно зависимости редко бывают строго линейными, однако предположение о линейности дает возможность разрабатывать эффективные методы, использование которых для ряда задач нелинейного программирования вполне оправдано. Линейные модели могут содержать в качестве ограничений не только неравенства, но и уравнения. Общая задача линейного программирования – это определение оптимального значения целевой функции n f ( x)   c j x j  max (min) j 1 при ограничениях: n  aij x j  bi , i  1, k ,  j 1n    aij x j  bi , i  k  1, l ,  j 1  n   aij x j  bi , i  l  1, m,  j 1  d j  x j  D j , j  1, n,  где d j и D j – соответственно нижняя и верхняя граница переменной x j . Стандартная задача линейного программирования – это определение максимального значения целевой функции n f ( x)   c j x j  max j 1 при ограничениях в виде неравенств: Составители: Балашов А.Н.  n   aij x j  bi , i  1, k ,  n j 1   aij x j  bi , i  k  1, m,  j 1  x j  0, j  1, n.  Каноническая задача линейного программирования – это определение максимального значения целевой функции n f ( x)   c j x j  max j 1 при ограничениях в виде равенств: n  aij x j  bi , i  1, m,  j 1  x  0, j  1, n. j  Совокупность значений переменных x1 , x2 , ..., xn , удовлетворяющих всем линейным ограничениям, называется допустимым (опорным) планом. Переход от стандартной модели ЗЛП к канонической осуществляется добавлением новых неотрицательных переменных со знаком «+» для неравенств типа  и со знаком «–» для неравенств типа  . Само неравенство заменяется на равенство. Если в ЗЛП на некоторую переменную xk не накладывается условие неотрицательности, то добавляются две неотрицательные переменные и делают замену переменных xk  xk2  xk1 , xk2  0, xk1  0 . При переходе от задачи на минимум к задаче на максимум изменяется знак целевой функции. ЗЛП может принимать оптимальное значение в нескольких точках, такие решения называются альтернативными оптимальными решениями или альтернативным оптимумом, причем в каждой из этих точек целевая функция имеет одно и то же оптимальное значение. Если в ЗЛП с двумя параметрами управления нормальный вектор целевой функции параллелен нормальному вектору прямой одного из ограничений, то ЗЛП может иметь множество оптимальных решений. Например, f ( x)  2 x1  3x2  max ,  4 x1  6 x2  15,  7 x1  5 x2  20,  x  0, x  0. 2  1 Составители: Балашов А.Н. Вектор целевой функции N (2; 3) параллелен нормальному вектору N1 (4; 6) прямой первого ограничения: N1  2N . В этом случае возможно множество оптимальных решений. Если в ЗЛП с тремя параметрами управления нормальный вектор целевой функции параллелен нормальному вектору плоскости одного из ограничений, или перпендикулярен прямой пересечения двух плоскостей ограничений, то ЗЛП может иметь множество оптимальных решений. Для ЗЛП с большим количеством параметром управления определить имеется ли множество оптимумов по виду составленной математической модели является сложной задачей. Пример 1.1. Составить математическую модель задачи, привести ее к каноническому виду. Предприятие при выпуске однотипной продукции может использовать три технологических способа производства (ТСП). Расходы, связанные с каждым технологическим способом, определяются количеством трудозатрат (человеко-часов), электроэнергии (киловаттчасов) и потребляемого материала (кг). Исходные данные задачи представлены в виде табл. 1.1. Расходы ресурсов Количество человеко-часов Количество киловатт-часов Количество материала, кг Доход с единицы продукции, руб. На единицу продукции ТСП1 ТСП2 ТСП3 10 15 10 18 16 20 70 50 60 50 60 70 Таблица 1.1 Имеется в наличии 320 500 2000 max Определить объем выпускаемой продукции, обеспечивающий наибольший доход. Решение. 1. В процессе производства можно менять количество выпускаемой продукции по определенному ТСП. Поэтому в качестве параметров управления x1, x2 и x3 выберем количество выпускаемой продукции по соответствующему технологическому способу производства ТСП1, ТСП2 и ТСП3. 2. Целевая функция должна максимизировать доход от выпускаемой продукции: f(x) = 50x1 + 60x2 + 70x3  max. 3. Ограничивает количество выпускаемой продукции запасы ресурсов. В процессе производства мы не должны превысить количество имеющихся человеко-часов: 10x1  15x2  10x3  320 . Аналогично для двух других ресурсов: 18x1  16x2  20x3  500 , 70x1  50x2  60x3  2000. Необходимо добавить условие неотрицательности переменных: x1  0, x2  0, x3  0 . В результате имеем математическую модель: Составители: Балашов А.Н. f ( x)  50x1  60x2  70x3  max,  10x1  15x2  10x3  320,  18x  16x  20x  500,  1 2 3  70x1  50x2  60x3  2000,  x j  0, j  1, 3. Решение с помощью MS Excel [2, Лист 1]: f(x) = 1790 руб., x1 = 0, x2 = 10, x3 = 17. Это стандартная ЗЛП. Из нее получим каноническую ЗЛП, добавив в 1-е, 2-е и 3-е неравенства неотрицательные переменные x4 , x5 , x6 . f ( x)  50x1  60x2  80x3  max,  10x1  15x2  10x3  x4  320,  18x  16x  20x  x  500,  1 2 3 5  70x1  50x2  60x3  x6  2000,  x j  0, j  1, 6. Пример 1.2. Для изготовления изделий двух видов имеется 400 кг металла. На одно изделие 1-го вида расходуется 2 кг металла, а на изделие 2-го вида – 5 кг. Составить план производства, обеспечивающий наибольшую стоимость выпускаемых изделий, если отпускная цена одного изделия 1-го вида составляет 4 ден. ед., а изделие 2-го вида 3 ден. ед., причем изделий каждого вида требуется изготовить соответственно не менее 50 и 20. Решение. 1. В качестве параметров управления x1 и x2 выберем соответственно количество изготовленных изделий 1-го и 2-го вида. 2. Целевая функция должна максимизировать прибыль, получаемую от реализации изделий. Поэтому, f(x) = 4x1 + 3x2  max. 3. Ограничивают количество выпускаемых изделий в первую очередь 400 кг металла. В процессе производства мы не должны превысить запасы имеющегося металла 2 x1  5x2  400 . Наличие плана также накладывает ограничение. Изделий 1-го и 2-го вида необходимо изготовить соответственно не менее 50 и 20, т.е. x1  50, x2  20 . Количество изготовленных изделия принадлежит множеству неотрицательных целых чисел. Необходимо добавить условие неотрицательности и целочисленности переменных x1, 2  N 0 , N 0 – множество целых неотрицательных чисел. Хотя в данной задаче ограничение неотрицательности излишне, так как ограничения x1  50, x2  20 являются более строгими, чем условие неотрицательности переменных. В итоге мы имеем математическую модель задачи: Составители: Балашов А.Н. f ( x)  4 x1  3 x2  max, 2 x1  5 x2  400,  x1  50,   x2  20,   x1, 2  N 0 . Решение с помощью MS Excel [2, Лист 2]: f(x) = 660 ден. eд., x1 = 150, x2 = 20. 1.2. Графический метод решения Графические методы решения более наглядны, но имеют ограниченный круг использования – число неизвестных переменных должно быть не более трех. Только в этом случае решение задачи можно наглядно представить на бумаге. Рассмотрим графическое решение примера 1.2. Определим множество решения первого линейного неравенства 2 x1  5x2  400 . На плоскости оно отображается полуплоскостью, ограниченной прямой 2 x1  5x2  400 . Для построения прямой необходимо найти две точки, принадлежащие прямой. Обычно их находят путем последовательного обнуления каждой из переменных. Если x1 = 0, то x2 = 400/5 = 80. Если x2 = 0, то x1 = 400/2 = 200. Часто именно точки пересечения прямой с координатными прямыми и являются оптимальными решениями. В системе координат Ox1 x2 построим прямую по двум точкам (0; 80) и (200; 0). Построенная прямая делит координатную плоскость на две полуплоскости. Для определения искомой полуплоскости достаточно выбрать одну точка, не лежащую на прямой. Пусть это будет начало координат (0; 0). Подставим координаты выбранной точки в неравенство, получим: 0  400 . Неравенство верное, следовательно, нижняя полуплоскость которой принадлежит начало координат и является искомой. На рис. 1.1(а) эта полуплоскость изображена заштрихованными линиями. Аналогичная процедура выполняется для второго неравенства. Выберем точку (0; 0) и подставим во второе неравенство, получим: 0  50 . Неравенство неверное, следовательно, выберем правую полуплоскость которой не принадлежит начало координат. На рис. 1.1(б) эта полуплоскость изображена заштрихованными линиями. Для третьего неравенства выберем точку (0; 0) и подставим в третье неравенство, получим: 0  20 . Неравенство неверное, следовательно, выберем верхнюю полуплоскость которой не принадлежит начало координат. На рис. 1.1(в) эта полуплоскость изображена заштрихованными линиями. Составители: Балашов А.Н. В итоге выбираем общую заштрихованную область, точки которой удовлетворяют всем неравенствам задачи (рис. 1.1(г)). Область допустимых решений или область Парето изображается в виде замкнутого или незамкнутого многоугольника. Оптимальное решение ЗЛП находится в одной из вершин многоугольника области Парето. x2 x2 80 80 40 40 100 200 x1 x1 50 Рис. 1.1(а) Рис. 1.1(б) x2 x2 100 100 50 50 100 Рис. 1.1(в) 200 x1 50 100 150 200 x1 Рис. 1.1(г) Для нахождения оптимального решения графическим способом пользуются одним из двух способов: 1. Находят координаты всех вершин многоугольника области Парето и подставляют их в целевую функцию, после чего выбирают оптимальное значение (наибольшее или наименьшее); 2. Строят нормальный вектор прямой целевой функции. Проецируют область Парето на вектор или его продолжение (см. рис. 1.1(г)). Наиболее или наименее удаленная от начала координат проекция вершины области Парето на вектор или его продолжение и будет являться оптимальным решением. Для нахождения трех вершин необходимо решить три системы уравнений: x1  50, x2  20,  x1  50,       x2  20, 2 x1  5 x2  400, 2 x1  5x2  400. В итоге имеем: А(50; 20), В(50; 60), С(150; 20). Находим значения целевой функции в найденных вершинах: Составители: Балашов А.Н. F(50, 20) = 260, F(50, 60) = 380, F(150, 20) = 660. Наибольшая стоимость выпускаемой продукции составит 660 у.е. при изготовлении 150 изделий первого и 20 изделий второго вида. При решении вторым способом находим координаты только одной вершины С(150; 20), поскольку проекция этой вершины на продолжение вектора целевой функции N (4; 3) будет наибольшей (см. рис. 1.1(г)). Второй способ применяется при использовании одинаковых масштабов на осях координат. В противном случае линия проекции на вектор целевой функции визуально не будет составлять 90о. Если не удается наглядно изобразить область Парето в системе координат с одинаковым масштабом осей координат, то поступают следующим способом. В системе координат с разным масштабом координатных осей рисуют линию уровня целевой функции f ( x)  0 или f ( x)  const и ее перемещают параллельно в направлении вектора целевой функции до пересечения с областью Парето. Пример 1.3. Для изготовления изделий двух видов А и В используется токарное и фрезерное оборудование. Затраты времени на обработку одного изделия для каждого из типов оборудования, общий фонд рабочего времени каждого из типов используемого оборудования, а также прибыль от реализации одного изделия каждого вида указаны в табл. 1.2: Таблица 1.2 Затраты времени на обработку одного изделия вида А В Фрезерное, час 2 5 Токарное, час 4 2 Прибыль, руб. 10 24 Тип оборудования Общий фонд рабочего времени оборудования, час 200 160 max Требуется определить, сколько изделий следует изготовить предприятию, чтобы прибыль от их реализации была максимальной. Решение. 1. В качестве параметров управления x1 и x2 выберем соответственно количество изготовленных изделий 1-го и 2-го вида. 2. Целевая функция должна максимизировать прибыль, получаемую от реализации изделий. Поэтому, f(x) = 10x1 + 24x2  max. 3. Ограничивают количество выпускаемых изделий общий фонд рабочего времени. В процессе производства мы не должны превысить общий фонд рабочего времени фрезерного оборудования 2 x1  5x2  200 и общий фонд рабочего времени токарного оборудования 4 x1  2 x2  160 . Необходимо добавить условие неотрицательности и целочисленности переменных: x1, 2  N 0 , N 0 – множество целых неотрицательных чисел. В итоге мы имеем математическую модель задачи: Составители: Балашов А.Н. f(x) = 10x1 + 24x2  max, (1) 2 x1  5 x2  200,  (2)  4 x1  2 x2  160,  x N . 1, 2  Рассмотрим графический метод решения. Изобразим область допустимых решений в системе координат Ox1x2. Найдем две точки, лежащие на прямой 2 x1  5x2  200 . Пусть x1 = 0, тогда из данного уравнения имеем x2 = 200/5 = 40. Пусть x2 = 0, тогда из уравнения имеем x1 = 200/2 = 100. В итоге имеем координаты двух точек прямой (1) – A(0; 40) и B(100; 0). В системе координат Ox1 x2 построим прямую по двум точкам A и B (рис. 1.2). Аналогично для другой прямой 4 x1  2 x2  160 . Пусть x1 = 0, тогда x2 = 160/2 = 80. Пусть x2 = 0, тогда x1 = 160/4 = 40. В итоге имеем координаты двух точек прямой (2) – C(0; 80) и D(40; 0). В системе координат Ox1 x2 построим прямую по двум точкам C и D (рис. 1.2). В результате получили три замкнутые и одну незамкнутую области. Для определения области допустимых решений возьмем контрольную точку с координатами (0; 0), принадлежащую только четырехугольнику OAED, рис. 1.2. Координаты этой точки удовлетворяют всем ограничениям. Следовательно, выбранный четырехугольник OAED является искомой областью Парето. Контрольной точкой может быть не только вершина многоугольника, но и любая внутренняя точка полученных многоугольников. x2 80 C(0; 80) 60 A(0; 40) 40 5 20 E(25; 30) D(40; 0) 20 40 60 80 B(100; 0) 100 x1 Рис. 1.2 Найдем координаты точки пересечения прямых (1) и (2) из систему уравнений: 2 x1  5 x2  200,   4 x1  2 x2  160. Разделим второе уравнение системы на 2 и вычтем из второго уравнения первое уравнение: Составители: Балашов А.Н. 2 x1  5 x2  200,    4 x2  120. Разделим второе уравнение на (–4): 2 x1  5 x2  200,  x2  30.  Подставим в первое уравнение численное значение x2  30 . Получим координаты точки E(25; 30) пересечения прямых AB и CD. Координаты точек пересечения построенных прямых с осями координат найдены при построении прямых. Найдем значения целевой функции в вершинах четырехугольника O(0; 0), A(0; 40), E(25; 30) и D(40; 0): F(0, 0) = 0, F(0, 40) = 960, E(25, 30) = 970, F(40, 0) = 400. Наибольшая прибыль составит 970 руб. при изготовлении 25 изделий типа А и 30 изделий типа В. Проекции точек A и E на продолжение вектора целевой функции находятся очень близко друг от друга. При решении вторым способом (см. стр. 14) необходимо найти значение целевой функции в обеих точках A и E. Составители: Балашов А.Н. 1.5. Решение задач линейного программирования с помощью электронных таблиц MS Excel Рассмотрим решение примера 1.3 с помощью MS Excel 2007/10 [2, Лист 5]. Решение задачи линейного программирования с помощью Excel состоит из следующих этапов: - ввод условий задачи; - решение; - анализ оптимального решения. I. Ввод условий задачи. Ввод условий задачи состоит из следующих шагов: - создание экранной формы для ввода условий задачи; - ввод исходных данных; - ввод зависимостей из математической модели; - назначение целевой функции и переменных; - ввод граничных условий и ограничений. 1. Создаем экранную форму на рабочем листе MS Excel и вводим данные задачи (табл. 1.10). A 1 2 3 4 5 6 7 8 Имя Значение Коэф. ЦФ 1-ое 2-ое B C Переменные x1 x2 10 D E ЦФ Направление max Левая часть Знак ≤ ≤ 24 Ограничения 2 5 4 2 Таблица 1.10 F Правая часть 200 160 2. Вводим зависимости из математической модели в ячейки D4, D7, D8 используя: окно диалога Мастер функций (fx Вставить функцию), категория Математические, в алфавитном списке Выберите функцию выбираем функцию СУММПРОИЗВ. Функция может быть введена непосредственно с клавиатуры. Содержимое ячеек: D4=СУММПРОИЗВ($B$3:$С$3;B4:С4). D7=СУММПРОИЗВ($B$3:$С$3;B7:С7). D8=СУММПРОИЗВ($B$3:$С$3;B8:С8). 3. Назначение целевой функции и переменных. Для назначения целевой функции используем команду Данные/Поиск решения. Если команда Поиск решения недоступна, то ее необходимо установить. Используем команду Настройка панели быстрого доступа, выбираем Другие команды…, в окне диалога Параметры Excel выделяем Составители: Балашов А.Н. Надстройки, в списке Надстройки выделяем Поиск решения, в алфавитном списке Управление выбираем Надстройки Excel, используем кнопку Перейти, в диалоговом окне Надстройки устанавливаем флажок Поиск решения. В диалоговом окне Поиск решения: В поле Установить целевую ячейку указываем ячейку целевой функции $D$4 (рис. 1.3). Если перед вызовом инструмента Поиск решения выделить ячейку с целевой функцией $D$4, то это поле уже будет заполнено. В элементе управления Равной выбираем максимальному значению (рис. 1.3). В элементе управления Изменяя ячейки указываем диапазон $B$3:$C$3 (рис. 1.3), в котором размещены численные значения переменных. Рис. 1.3 4. Ввод ограничений выполняется с помощью кнопки Добавить в списке Ограничения (см. рис. 1.3). На экране появится диалоговое окно Добавление ограничения (рис. 1.4). Поле Ссылка на ячейку предназначено для указания ссылки на ячейку, где хранятся переменные или формулы, используемые для ввода ограничений. В поле Ограничение можно вводить константу, ссылку на ячейки со значениями и формулами. Значения из полей Ссылка на ячейку и Ограничение сравниваются с помощью операций «>=, <=, =, цел, двоич», которые можно выбрать из списка, расположенного между этими двумя полями. Составители: Балашов А.Н. Кнопка Добавить позволяет добавить несколько ограничений, кнопка OK добавляет ограничение и закрывает диалоговое окно Добавление ограничения. Вводим условие целочисленности переменных: $B$3:$C$3 цел целое, Добавить (рис. 1.4). Рис. 1.4 Аналогично вводим ограничения: $D$7:$D$8 ≤ $F$7: F$8, OK. В результате на экране появится диалоговое окно (см. рис. 1.3). Условие неотрицательности переменных введем во второй части. На этом ввод условий задачи заканчивается. II. Решение. Для решения используем кнопку Параметры диалогового окна Поиск решения. Команды диалогового окна Параметры поиска решения: Максимальное время, Предельное число итераций, Относительная погрешность, Допустимое отклонение, используемые по умолчанию, подходят для решения большей части практических задач. Установим флажок Линейная модель, что обеспечит применение симплекс-метода, и установим флажок Неотрицательные значения, что обеспечит условие неотрицательности переменных, OK (рис. 1.5). Рис. 1.5 Составители: Балашов А.Н. В диалоговом окне Поиск решения воспользуемся кнопкой Выполнить. В диалоговом окне Результаты поиска решения приводятся результаты решения и даются типы отчета. Выбираем Сохранить найденное решение, OK. На рабочем листе отобразится найденный оптимальный план (табл. 1.10). A 1 2 3 4 5 6 7 8 D E Имя Значение Коэф. ЦФ B C Переменные x1 x2 25 30 10 24 ЦФ 970 Направление max 1-ое 2-ое Ограничения 2 5 4 2 Левая часть 200 160 Знак ≤ ≤ Таблица 1.10 F Правая часть 200 160 В результате решения, получили следующий оптимальный план: x = (25; 30), f(x) = 970. III. Анализ оптимального решения. Для анализа вызываются отчеты трех типов: Результаты; Устойчивость; Пределы. Вызов отчетов выполняется с помощью диалогового окна Результаты поиска решений (Поиск решения, Выполнить). Выбираем Результаты в диалоговом окне Тип отчета, OK. Открываем созданный лист Отчет по результатам 1 (табл. 1.11). Таблица 1.11 Microsoft Excel 12.0 Отчет по результатам Рабочий лист: [Optimus1.xlsx]Лист5 Отчет создан: 21.12.2015 9:39:11 Целевая ячейка (Максимум) Ячейка Имя $D$4 Коэф. в ЦФ ЦФ Изменяемые ячейки Ячейка $B$3 $C$3 Имя Значение x1 Значение x2 Исходное значение 970 Результат 970 Исходное значение 25 30 Результат 25 30 Составители: Балашов А.Н. Ограничения Ячейка Имя $D$7 1-ое Левая часть $D$9 2-ое Левая часть $B$3 Значение x1 $C$3 Значение x2 $B$3 Значение x1 $C$3 Значение x2 Значение 200 160 25 30 25 30 Формула $D$7<=$F$7 $D$9<=$F$9 $B$3=целое $C$3=целое $B$3=целое $C$3=целое Статус Разница связанное связанное связанное связанное не связан. 25 не связан. 30 Информация данного отчета означает, что предприятие может получить максимальную прибыль в размере 970 рублей при изготовлении 25 изделий типа А и 30 изделий типа В. При этом общий фонд рабочего времени токарного и фрезерного оборудования используется полностью. Отчет по устойчивости (применяется в случае отсутствия ограничения целочисленности). Отменим условие целочисленности. В диалоговом окне Поиска решения в списке Ограничения выделяем условие целочисленности и удаляем его. Выбираем кнопку Выполнить, в диалоговом окне Тип отчета выбираем Устойчивость, OK. Открываем созданный лист Отчет по устойчивости 1 (табл. 1.12). Таблица 1.12 Microsoft Excel 12.0 Отчет по устойчивости Рабочий лист:[Optimus1.xlsx ]Лист5 Отчет создан: 21.12.2015 10:05:25 Изменяемые ячейки Ячейка Имя Значение x1 Значение x2 $B$3 $C$3 Результ. значение Нормир. стоимость Целевой Коэффициент Допустимое Увеличение Допустимое Уменьшение 25 30 10 24 38 1 0,4 19 Результ. значение Теневая Цена Ограничение Правая часть Допустимое Увеличение Допустимое Уменьшение 200 160 4,75 0,125 200 160 200 240 120 80 Ограничения Ячейка $D$7 $D$8 Имя 1-ое Левая часть 2-ое Левая часть Отчет по устойчивости состоит из двух таблиц. В таблице «Изменяемые ячейки» приводятся следующие значения для переменных: результат решения исходной задачи; нормированная стоимость, которая означает следующее. Если продукт входит в оптимальный план, то в данной колонке отчета для этого продукта стоит 0; если продукт не входит в оптимальный план, то в этой колонке стоит отрицательное число, показывающее, насколько (по абсолютной величине) нужно увеличить прибыль от производства единицы этого продукта, чтобы он вошел в оптимальный план. Таким образом, нормированная стоимость показывает, насколько изменится Составители: Балашов А.Н. значение целевой функции в случае принудительного включения единицы этой продукции в оптимальное решение; коэффициенты целевой функции; предельные значения приращения коэффициентов ∆Cj целевой функции, при которых сохраняется первоначальное оптимальное решение. Информация данной таблицы означает, что для получения максимальной прибыли в размере 970 рублей предприятие должно изготавливать 25 изделий типа А и 30 изделий типа В, так как его нормированная стоимость равна 0. Интервалы изменения коэффициентов целевой функции, при которых сохраняется первоначальное оптимальное решение, следующие: 10  0,4  C1  10  38, 24  19  C2  24  1, 9,6  C1  48 , 5  C2  25 . В таблице «Ограничения» приводятся аналогичные значения для ограничений: теневая цена, т.е. двойственные оценки yi , которые показывают, как изменится целевая функция при изменении ресурсов на единицу. Информация данной таблицы отчета показывает, что общий фонд рабочего времени токарного и фрезерного оборудования используется полностью, оно являются дефицитным и для токарного и для фрезерного оборудования. Двойственная оценка (теневая цена) фонда рабочего времени токарного оборудования равна 4,75, а фрезерного – 0,125. Следовательно, рабочее время токарного оборудования боле дефицитно, чем фрезерного оборудования. Интервалы устойчивости двойственных оценок, при которых сохраняется оптимальное решение двойственной задачи, следующие: 200  120  b1  200  200 , 160  80  b2  160  240 . Следовательно, интервалы устойчивости двойственных оценок: 80  b1  400 , 80  b2  400 . Отчет по пределам не применим при ограничениях целочисленности. Выбираем диалоговое окно Поиск решения используем кнопку Выполнить, выбираем Пределы в диалоговом окне Тип отчета, OK. Открываем созданный лист Отчет по пределам 1 (табл. 1.13). Таблица 1.13 Microsoft Excel 12.0 Отчет по пределам Рабочий лист: [Optimus1.xlsx ]Отчет по пределам 1 Отчет создан: 21.12.2015 10:54:03 Ячейка $D$4 Ячейка $B$3 $C$3 Целевое Имя Коэф. в ЦФ ЦФ Изменяемое Имя Значение x1 Значение x2 Значение 970 Значение 25 30 Нижний предел Целевой результат 720 250 Верхний предел 25 30 Целевой результат 970 970 Составители: Балашов А.Н. Во второй таблице показаны значения целевой функции при нулевом значении одного из параметров управления при сохранении оптимальных значений других параметров управления. Если из оптимального плана исключить изделия типа A, то прибыль составит f(0, 30) = 24∙30 = 720. Если из оптимального плана исключить изделия типа B, то прибыль составит f(25, 0) = 10∙25 = 250. Аналогично для верхнего предела изменения одного из параметров управления при сохранении оптимальных значений других параметров управления. 1.6. Примеры типовых задач линейного программирования 1. Планирование производства (распределение ресурсов). Пример 1.5. При изготовлении трех видов продукции П1, П2 и П3 используют четыре вида ресурсов – Р1, Р2, Р3 и Р4. Расход ресурсов на производство единицы продукции, запасы ресурсов, прибыль, получаемая от единицы продукции, приведены в табл. 1.14. Таблица 1.14 Вид ресурса Р1 Р2 Р3 Р4 Прибыль, получаемая от одного изделия, ден. ед. Расход ресурсов на производство единицы продукции П1 П2 П3 10 20 30 12 13 9 2 5 1 7 4 5 12 15 Запас ресурса, ед. 500 600 100 200 10 Необходимо составить план производства продукции, при котором прибыль от ее реализации будет максимальной. Решение. 1. В качестве параметров управления выберем xi – количество выпущенной продукции i-го вида. 2. Целевая функция должна максимизировать стоимость выпускаемой 3 продукции f ( x)   ci xi  12x1  15x2  10x3  max . i 1 3. Ограничивает количество выпускаемой продукции запасы ресурсов четырех видов Р1, Р2, Р3 и Р4: 10x1  20x2  30x3  500 – для 1-го ресурса, 12x1  13x2  9 x3  600 – для 2-го ресурса, 2 x1  5x2  x3  100 – для 3-го ресурса, 7 x1  4 x2  5x3  200 – для 4-го ресурса. Необходимо добавить условие неотрицательности переменных xi. Составим математическую модель задачи. f ( x)  12x1  15x2  10x3  max , Составители: Балашов А.Н. 10x1  20x2  30x3  500,  12x  13x  9 x  600, 1 2 3   2 x1  5 x2  x3  100,  7 x  4 x  5 x  200, 1 2 3   xi  0, i  1, 3. Решение с помощью MS Excel [2, Лист 6]: f(x) = 438,(63) ден. ед., x1  20, (45), x2  11, (36), x3  2, (27) . Ответ: Следует выпускать продукцию 1-го вида в количестве 20,(45), 2-го вида в количестве 11,(36), 3-го вида в количестве 2,(27). Прибыль составит 438,(63) ден. ед. 2. Выбор оптимальных проектов для финансирования. Пример 1.6. Управляющему банка для выделения кредита были представлены 5 проектов. Доступная наличность банка bj, потребности проектов Cij в каждом квартале и прибыль по ним приведены в табл. 1.15. Квартал Проект П1 П2 П3 П4 П5 Ресурс банка, тыс. руб. Таблица 1.15 Прибыль, тыс. руб. I 100 120 80 90 130 410 II 90 80 70 100 90 420 III 60 70 60 50 30 460 IV 90 60 120 80 70 400 320 310 280 270 290 Какие проекты следует финансировать и какое количество наличности необходимо в течение каждого квартала, чтобы максимизировать прибыль? Решение. 1. В качестве параметров у правления выберем xi (i  1, 5) , каждый из которых принимает только два значения: 1, если i-й проект получит кредит; 0, если i-й проект не получит кредит. 2. Целевая функция должна максимизировать прибыль, получаемая банком. Поэтому f(x) = 320x1 + 310x2 + 280x3 + 270x4 + 290x5  max. 3. Ограничивают количество выбранных проектов только доступная 5  Cij xi  b j . i 1 xi  0; 1. наличность банка в каждом квартале: Необходимо добавить условие двоичности переменных В итоге мы имеем математическую модель задачи: f(x) = 320x1 + 310x2 + 280x3 + 270x4 + 290x5  max, Составители: Балашов А.Н. 100x1  120x 2  80x3  90x 4  130x5  410,  90x  80x  70x  100x  90x  420, 1 2 3 4 5   60x1  70x 2  60x3  50x 4  30x5  460,  90x  60x  120x  80x  70x  400, 1 2 3 4 5   xi  0; 1. Решение с помощью MS Excel [2, Лист 7]: f(x) = 1180 тыс. руб., x1  x2  x3  x4  1 , x5 = 0 . Ответ: Следует финансировать первые четыре проекта. В первом квартале необходимо 390 тыс. руб., во втором – 340 тыс. руб., в третьем – 240 тыс. руб., в четвертом – 350 тыс. руб. Прибыль составит 1180 тыс. руб. 3. Планирование финансового потока. Пример 1.7. В начале года фирма «Благодетель» решила профинансировать долгосрочный инвестиционный проект, располагая средствами в размере М = 2 млн. рублей. Необходимые расходы по проекту для каждого квартала приведены в табл. 1.16. Таблица 1.16 Квартал Δi (расходы, тыс. руб.) I II III IV 600 520 400 550 Всего за год необходимо инвестировать 2,07 млн. рублей. Поэтому было принято решение положить свободные деньги в банк на 3-месячные, 6-месячные и 12-месячные депозитные счета. Процентные ставки по указанным депозитам приведены ниже в табл. 1.17. Таблица 1.17 Вид депозита 1 (3-х месячный) 2 (6-и месячный) 3 (12-и месячный) Годовой доход 10% 12% 16% Необходимо составить поквартальный план размещения средств на депозитные счета, который обеспечил бы необходимое финансирование и максимальный доход от свободных средств к концу года. Решение. В качестве параметров управления выберем xij (руб.) – сумма, положенная в банк на i-й депозит (i = 1, 2, 3) в начале j-го квартала (j = 1, 2, 3, 4). 2. Целевая функция должна максимизировать доход, полученный от размещения свободных средств. Если в начале первого квартала положить в банк сумму x11 на 3-х месячный вид депозита, то в начале второго 10% 3 x11  0,025x11 . квартала прибыль от вложенной суммы составит 100% 12 Если в начале первого квартала положить в банк сумму x21 на 6-и Составители: Балашов А.Н. месячный вид депозита, то в начале третьего квартала прибыль от 12% 6 x21  0,06x21 . Если в начале первого вложенной суммы составит 100% 12 квартала положить в банк сумму x31 на 12-и месячный вид депозита, то в 16% 12 x31  0,16x31 . конце года прибыль от вложенной суммы составит 100% 12 Целевая функция имеет вид: f ( x)  0,025( x11  x12  x13  x14 )  0,06( x21  x22  x23 )  0,16x31  max . 3. Максимальный доход от свободных средств ограничивают обязательные инвестиции в каждом квартале. В первом квартале можно положить на депозиты всю сумму, за исключением расходов в первом квартале: x11  x21  x31  2 000000  600000. В начале второго квартала получим прибыль 0,025x11 от 3-х месячного депозита. В начале третьего квартала получим прибыль 0,025( x11  x12 )  0,06x21 от 3-х месячных депозитов 1-го и 2-го кварталов и 6-и месячного депозита 1-го квартала. В начале четвертого квартала получим прибыль 0,025( x11  x12  x13 )  0,06( x21  x22 ) от 3-х месячных депозитов 1-го, 2-го и 3-го кварталов и 6-х месячного депозита 1-го и 2-го кварталов. В начале второго квартала в банке мажет находиться сумма которая не должна превышать x12  x22  ( x21  x31) В начале 2 000000  600000  520000  0,025x11  880000  0,025x11 . третьего квартала в банке мажет находиться сумма x13  x23  ( x22  x31) которая не должна превышать 480000  0,025( x11  x21 )  0,06x21 . В начале четвертого квартала в банке мажет находиться сумма x14  ( x23  x31) которая не должна превышать  70000  0,025( x11  x12  x13 )   0,06( x21  x22 ) . Составим математическую модель задачи. f ( x)  0,025( x11  x12  x13  x14 )  0,06( x21  x22  x23 )  0,16x31  max , x11  x21  x31  1 400 000,   x12  x22  ( x21  x31 )  880 000  0,025x11 ,   x13  x23  ( x22  x31 )  480 000  0,025( x11  x12 )  0,06x21 ,  x  ( x  x )  70 000  0,025( x  x  x )  0,06( x  x ), 23 31 11 12 13 21 22  14 xij  0, i  1, 3, j  1, 4, xij  целые.  Задача имеет альтернативные оптимумы. Одно из решений найдено с помощью MS Excel ([2, Лист 8] при использовании линейной модели и нулевых начальных значениях переменных): f(x) = 80 569,64 руб., x11 = 1 013 480 руб., x13 = 53 руб., x21 = 377 409 руб., x22 = 518 817 руб., x31 = 9 111 руб. Составители: Балашов А.Н. Если xij (к.) , то получим оптимальное решение: f(x) = 80 569,71 руб., x11 = 1 013 529,60 руб., x13 = 0,09 руб., x21 = 377 358,58 руб., x22 = 518 867,84 руб., x31 = 9 111,82 руб. 4. Задача о ранце (рюкзаке). Имеется n видов предметов, которые турист хочет взять с собою в поход. В рюкзаке он может нести предметы, масса и объем которых соответственно не более M кг и V м3 . Известны вес mj и объем νj каждого предмета и его ценность (эффективность) Cj для туриста. Сколько предметов турист может положить в рюкзак, чтобы суммарная стоимость (эффективность) предметов была бы максимальной? Задача о ранце имеет и экономическую интерпретацию. В качестве «предметов» рассматриваются заказы, в качестве полезности – прибыль от выполнения заказа, а в качестве веса – себестоимость заказа. Составим математическую модель задачи. Введем булевы переменные xj, которые принимают два значения: ноль, если турист не взял j-й предмет и единицу, если он взял его. Тогда математическая модель задачи будет иметь вид: n f ( x)   C j x j  max, j 1 n n j 1 j 1  m j x j  M ,  j x j  V , x j  0; 1. Пример 1.8. Имеются 8 ценных предметов, которые должны быть вывезены в безопасное место в случае пожара. Стоимости предметов (млн руб.), их веса (в кг) и габариты (в м3) приведены в табл. 1.20. Грузоподъемность имеющегося транспортного средства 1,5 тонны, вместимость 5 м3. Какие предметы надо вывезти в первую очередь, чтобы стоимость вывозимых предметов была максимальной? Вес, кг Габариты, м3 Стоимость, млн руб. 150 0,5 2 200 0,6 3,5 250 1,1 4 100 0,8 3 400 0,7 5 450 0,4 7 Таблица 1.20 300 400 0,3 1,2 4,2 8 Решение. 1. В качестве параметров управления выберем xi (i  1, 8) , каждая из которых принимает только два значения: 1, если i-й предмет вошел в список первоочередных предметов; 0, если i-й предмет не вошел в список. 2. Целевая функция должна максимизировать ценность вывозимых предметов 8 f ( x)   ci xi  2 x1  3,5 x2  4 x3  3x4  5 x5  7 x6  4,2 x7  8 x8  max . i 1 Составители: Балашов А.Н. 3. Ограничивают количество вывозимых предметов грузоподьемность с вместимость транспортного средства: 8  mi xi  1500 , i 1 8  ni x i  5 . i 1 Необходимо добавить условие двоичности переменных xi  0; 1. Составим математическую модель задачи. f ( x)  2 x1  3,5x2  4 x3  3x4  5x5  7 x6  4,2 x7  8x8  max, 150x1  200x2  250x3  100x4  400x5  450x6  300x7  400x8  1500,   0,5 x1  0,6 x2  1,1x3  0,8 x4  0,7 x5  0,4 x6  0,3x7  1,2 x8  5,  x  0; 1, i  1, 8.  i Решение с помощью MS Excel [2, Лист 9]: f(x) = 26,2, x3  x4  x6  x7  x8  1 , x1  x2  x5  0 . Ответ: Оптимальная ценность предметов составит 25,5 млн руб., если в первую очередь вывозить 2-й, 3-й, 4-й, 6-й и 8-й предметы. 5. Задача составления смесей. Содержательная постановка задачи. Имеется некоторый набор первичных продуктов, из которых можно составлять различные смеси. Обязательное требование к составляемой смеси заключается в том, что в ней количество веществ определенного вида должно быть не ниже заданной нормы, а количество других веществ не выше заданной нормы. Требуется из имеющихся смесей выбрать оптимальную совокупность с минимальной стоимостью. К этой группе задач относятся задачи о выборе диеты, составлении кормового рациона в животноводстве, горючих и смазочных смесей в нефтеперерабатывающей промышленности, смесей для получения бетона в строительстве и т. д. Пример 1.9. Завод выпускает 3 вида полуфабрикатов в количествах: A1 – 300 т, A2 – 200 т и A3 – 400 т. В результате смешивания этих компонентов получают 2 вида продукции. Пропорции смешиваемых полуфабрикатов для продукции B1 – 2:1:2, для B2 – 1:1:2. Стоимость 1 т продукции B1 – 500 руб., B2 – 400 руб. Составить оптимальный план, обеспечивающий максимальную стоимость выпускаемой продукции. Решение. 1. В качестве параметров управления выберем xi – количество выпущенной продукции i-го вида. 2. Целевая функция должна максимизировать стоимость выпускаемой продукции f(x) = 500x1 + 400x2  max. 3. Ограничивает количество выпускаемой продукции запасы полуфабрикатов j-го вида: 2 x1  x2  300 – для полуфабриката A1, x1  x2  200 – для полуфабриката A2, 2 x1  22  400 – для полуфабриката A3. Необходимо добавить условие неотрицательности переменных xi. Составим математическую модель задачи. Составители: Балашов А.Н. f(x) = 500x1 + 400x2  max,  2 x1  x2  300,  x  x  200,  1 2  2 x1  2 x2  400,  x1 , x2  0. Решение с помощью MS Excel [2, Лист 10]: f(x) = 90 000 руб., x1  100, x2  100 . Ответ: Следует выпускать продукцию 1-го вида в количестве 100 т, 2-го вида в количестве 100 т, максимальная стоимость выпускаемой продукции составит 90 000 руб. 6. Рациональный раскрой промышленных материалов. Применение рационального раскроя промышленных материалов обеспечивает повышение коэффициента использования длинномерных материалов на 2 – 5%, а листовых – на 3 – 7%. Особенность рационального раскроя состоит в разработке и использовании таких допустимых раскройных планов, при которых получается необходимый ассортимент заготовок, а отходы по длине, площади или весу сводятся к минимуму. Данная задача особенно актуальна в условиях многономенклатурного производства. Сформулируем условие задачи в общем виде для одномерного материала. Необходимо раскроить одномерный материал (прутки стального проката, трубы, брусья, доски и т.д.) длины l. В соответствии с планом или заявками потребителей требуются заготовки i – видов длиной Δi каждая в соответствующих количествах ai. Необходимо найти план раскроя, обеспечивающий заявки потребителей, при минимальном количестве раскройных материалов (по количественному составу, остаткам по длине или весу). Для составления математической модели введем обозначения: l – длина исходного материала; i – виды заготовок (по длине), которые необходимо получить при раскрое (i = 1, 2, …, m); bi – необходимое количество заготовок i-го вида по плану; j – варианты раскроя единицы исходного материала (j = 1, 2, …, n); aij – количество заготовок i–го вида, получаемое при раскрое единицы исходного материала по j–му варианту; Cj – отход при раскрое единицы исходного материала по j-му варианту раскроя; xj – количество единиц исходного материала, которое будет раскраиваться по j-му варианту. Составители: Балашов А.Н. Целевая функция может минимизировать либо отходы по длине n f ( x)   C j x j , либо количество раскраиваемых единиц материала j 1 n f ( x)   x j . j 1 В результате мы имеем математическую модель: n f ( x)   C j x j  min , j 1 n  aij x j  bi j 1 (i = 1,2,…,m), x j  N 0 . Если ассортимент заявок потребителей является уникальным (редким), то ограничения записываются в виде равенств. Если же размеры заготовок являются стандартными, то ограничения можно записывать в виде неравенств. Обычно количество ограничений гораздо меньше количества раскройных планов (m < n). Поэтому задача может имеет альтернативные оптимумы, которые дают одно и то же значение целевой функции. На практике в случае отсутствия полной автоматизации при минимизации затрат необходимо учитывать и количество материала, раскроенного по каждому способу. Пример 1.10. На складе имеются бревна длиной 600 см. Согласно заявкам потребителей требуются заготовки трех видов в следующих количествах: Δ1 = 210 см в количестве 200 штук; Δ2 = 170 см в количестве 300 штук; Δ3 = 140 см в количестве 400 штук. Необходимо найти план раскроя, удовлетворяющий заявкам потребителей и обеспечивающий: а) минимальное количество отходов материала; б) минимальное количество распиленных бревен. Решение. Определим всевозможные способы распила бревен. Пусть xj – количество бревен, которые будут распилены по j-му варианту. Для первого варианта раскроя выбираем максимально возможное количество заготовок длиной Δ1 = 210, т.е. две единицы. Из остатка 600 – 2∙210 = 180 выбираем максимально возможное количество заготовок длиной Δ2 = 170, т.е. одну единицу. Из получившегося остатка 180 – 1∙170 = 10 выбираем максимально возможное количество заготовок длиной Δ3 = 140, т.е. ноль единиц. В итоге имеем первый вариант раскроя (2; 1; 0). В результате мы должны перебрать всевозможные варианты раскроя, которые приведены в табл. 1.21. Таблица 1.21 Составители: Балашов А.Н. Способ распила, j 1 2 3 4 5 6 7 8 9 Число заготовок i–го вида, получаемых при раскрое одного бревна Δ1 = 210 Δ2 = 170 Δ3 = 140 2 1 2 1 1 2 1 1 1 1 2 3 2 1 1 3 4 Остаток, Cj 10 40 50 80 110 90 120 10 40 Чтобы не допустить потери какого-либо способа раскроя, в таблице 1.21 длины заготовок расположены в порядке убывания. В результате мы имеем математическую модель для первой части задачи: n f ( x)   C j x j , j 1 f ( x)  10x1  40x2  50x3  80x4  110x5  90x6  120x7  10x8  40x9  min ,  2 x1  2 x2  x3  x4  x5  200,  x  2 x  x  3 x  2 x  x  300,  1 3 4 6 7 8   x2  x4  2 x5  x7  3 x8  4 x9  400,  x j  N0. Оценим возможность получения альтернативных оптимумов. Составим расширенную матрицу системы ограничений и приведем ее к ступенчатому виду:  2 2 1 1 1 0 0 0 0 200   1 2 1 3 2 1 300  .  0 1 0 1 2 0 1 3 4 400   Умножим вторую строку матрицы на 2 и из нее вычтем первую строку  2 2 1 1 1 0 0 0 0 200    0  2 3 1  1 6 4 2 0 400 .  0 1 0 1 2 0 1 3 4 400   Умножим третью строку на 2 и прибавим к ней вторую строку  2 2 1 1 1 0 0 0 0 200     2 3 1  1 6 4 2 400  .  0 0 3 3 3 6 6 8 8 1200   Составители: Балашов А.Н. Ранг матрицы равен 3, количество базисных переменных равно 3, количество свободных переменных равно 9 – 3 = 6. Поэтому задача может иметь альтернативные оптимумы. Решение с помощью MS Excel (файл Optimus1.xlsx Лист 11 при использовании нулевых начальных значениях переменных): f(x) = 4600 см, x1 = 99, x3 = x4 = x9 = 1, x6 = 21, x7 = 2, x8 = 131, x2 = x5 = 0. Всего необходимо распилить 256 бревен. Решение с помощью MS Excel ([2, Лист 11] при использовании линейной модели и нулевых начальных значениях переменных): f(x) = 4600 см, x1 = 86, x2 = 4, x3 = 20, x6 = 14, x8 = 132, x4 = x5 = x7 = x9 = 0. Всего необходимо распилить 256 бревен. Решение с помощью MS Excel для стандартных заявок (ограничения записаны в виде неравенств ≥): f(x) = 3000 см, x1 = 129, x8 = 171, x2 = x3 = x4 = x5 = x6 = x7 = x9 =0. Всего необходимо распилить 300 бревен, остается 300 заготовок длиной 10 см. Любой набор параметров x1 = 129 + z, x8 = 171 – z, где z ϵ [-29; 37], z ϵ Z также является оптимальным решением. Целевая функция второй части задачи имеет вид: f ( x)  x1  x2  x3  x4  x5  x6  x7  x8  x9  min . Ограничения остаются неизменными. Задача может иметь множество оптимумов. Решение с помощью MS Excel дает [2, Лист 12]: f(x) = 256, x1 = 90, x3 = 18, x5 = 2, x6 = 14, x8 = 132, x2 = x4 = x7 = x9 =0. Другая разновидность задачи о раскрое заключается в том, что из имеющегося ограниченного количества материала необходимо изготовить максимальное количество заготовок в количествах, пропорциональных определенным числам. Пример 1.11. Для изготовления оконных рам необходимы рейки длиной 40 см и 120 см в соотношении 8:8. Фирма имеет в наличии 400 реек длиной 250 см. Определить план распила, обеспечивающий максимальное число комплектов. Решение. Определим всевозможные способы распила реек (табл. 1.22). Способ распила, j 1 Таблица 1.22 Число заготовок i–го вида, получаемых при раскрое одной рейки Δ1 = 120 Δ2 = 40 2 Составители: Балашов А.Н. 2 3 1 3 6 Пусть xj – количество реек, которые будут распилены по j-му варианту, x – количество комплектов реек. Учитывая, что все рейки должны быть распилены, а число реек каждого размера должно соответствовать условию комплектности, составим математическую модель: f ( x)  x  max ,  x1  x2  x3  400,  2 x  x  8 x,  1 2   3 x 2  6 x3  8 x ,  x, x j  N 0 . Решение с помощью MS Excel дает [2, Лист 13]: f(x) = 75, x1 = 240, x2 = 120, x3 = 40, x = 75. Рассмотрим аналитическое решение задачи. Составим расширенную матрицу системы ограничений и приведем ее к ступенчатому виду: 1 400   1 1 1 400   1 1 1 400  1 1        2 1 0 8 x    0  1  2 8 x  800   0  1  2 8 x  800  .  0 3 6 8x   0 3 6 8 x   0 0 0 32x  2400    Умножили первую строку первой матрицы на 2 и результат вычли из второй строки. Умножили вторую строку второй матрицы на 3 и результат прибавили к третьей строке. Из последней строки имеем 32x  2400  0 , x  75 . Из второй строки имеем x2  2 x3  800  8x , x2  200  2 x3 . Из первого уравнения имеем x1  x2  x3  400 , x1  400  x2  x3 , x1  200  x3 . Оптимальным планом является любой набор x1  200  x3 , x2  200  2 x3 , x1, 2,3  N 0 . Составители: Балашов А.Н.