Введение в линейное программирование. Общая постановка задач линейного программирования.

Лекция №1. Введение в линейное программирование. Общая постановка задач линейного программирования. Линейное программирование зародилось как отдельная дисциплина в 1939-1940 гг. благодаря работам советского математика, экономиста, академика Леонида Витальевича Канторовича (6 (19) января 1912 – 7 апреля 1986). В 1975 году Леонид Витальевич стал лауреатом Нобелевской премии по экономике «за вклад в теорию оптимального распределения ресурсов». Л.В. Канторович вывел широко используемые в экономико-математическом моделировании понятия, как оптимальное распределение ресурсов, оптимальный план, объективно обоснованные оценки. Кроме того, Леонид Витальевич показал применение теории линейного программирования во множестве отраслей экономики. Методы линейного программирования активно разрабатываются зарубежными учеными. Больших успехов в деле разработки таких методов добились американские исследователи. Математик Джордж Бернард Данциг, один из основателей теории линейного программирования наряду с Л.В. Канторовичем, разработал и предложил в 1949 г. алгоритм решения задач линейного программирования симплекс-методом. Вклад в разработку методов линейного программирования внесли Ричард Эрнст Беллман, Джон фон Нейман, Оскар Моргенштерн и др. Нужно отметить, что существует несколько объяснений тому, как термин «программирование» появился в названии раздела прикладной математики «линейное программирование». Первое, термин «программирование» введен в связи с тем, что неизвестные переменные, которые находятся в процессе решения задачи, обычно определяют программу или план работы некоторого экономического объекта. Второе, термин «программирование» связан с тем, что методы задач линейного программирования связаны с выполнением определенных алгоритмов схожих с алгоритмами, выполняемыми на компьютере. В этом курсе нами будут рассмотрены задачи линейного и нелинейного программирования и методы их решения, в целом, этот класс задач можно объединить под общим для них термином «математическое программирование». Кроме рассматриваемых нами задач, в математическом программировании можно выделить дискретное, динамическое программирование. Широкое применение теории линейного программирования связно с тем, что множество задач управления могут быть представлены в качестве задачи линейного программирования, для решения которых существует большое разнообразие эффективных методов решения. По оценкам специалистов, примерно 80 – 85% всех решаемых задач оптимизации относиться к задачам линейного программирования [Красс, Чупрынов, с. 254, 2007]. Реализация методов решения задач математического программирования (линейного, динамического, дискретного и др.) на компьютере позволяет переложить трудоемкие и сложные вычисления на технику, и использовать результаты решения в экономической науке (в томе числе, на практике). У читателя может возникнуть вопрос, каким же образом линейные зависимости могут описывать преимущественно нелинейный мир экономики, который подвержен множеству разнородных случайных колебаний? В действительности, теория линейного программирования позволяет себе упрощение окружающей нас действительности. В некоторых ситуациях (экономических) это упрощение позволяет получить реалистичные результаты, в других – весьма несовершенные. Итоги исследования, проведенного среди 500 крупнейших компаний США, показали, что линейное программирование постоянно применяют 74,2% компаний, нелинейное – 46,8%, динамическое – 29,7% [Красс, Чупрынов, с. 255, 2007]. В ходе хозяйственной деятельности человек многократно сталкивается с принятием решением относительно выполнения тех или иных действий (операций). Например, распределить имеющиеся средства или ресурсы, определить маршруты доставки грузов менее затратным способом и др. Линейное программирование – это класс задач и методов их решения, который позволяет определить наилучший способ выполнения этих операций. В дальнейшем мы приведем 1 более строгое определение, но оно не будет противоречить изложенному утверждению. Фактически, решая задачи линейного программирования, мы занимаемся исследованием некоторой экономической операции. Такими же исследованиями занимается и нелинейное программирование, теория систем массового обслуживания, динамическое программирование. В целом, все эти математические подходы к исследованиям можно определить под одним термином «исследование операций». Под этим термином мы будем понимать применение математических, количественных методов для обоснования решений во всех областях целенаправленной человеческой деятельности. Отметим, что непродуманные, необоснованные решения, принимаемые в экономической деятельности, ведут к непредсказуемым затратам, которые могут поставить на грань банкротства агента экономики. Создавая математическую модель экономической ситуации (задачи, которая стоит перед лицом, принимающим решение) и, решая её, например, методами линейного программирования, мы имеем возможность заранее определить оптимальные соотношения параметров задачи и выгоду, которую получим от этого соотношения. Давайте приведем ряд типичных для исследования операций задач. 1. План снабжения предприятий. Имеется ряд предприятий, потребляющих известные виды сырья, и есть ряд сырьевых баз, которые могут поставлять это сырье предприятиям. Базы связаны с предприятиями сетью сообщений (железнодорожной, водной, автомобильной, воздушной) со своими тарифами (ценой перевозки груза). Требуется разработать такой план снабжения предприятий сырьем (с какой базы, в каком количестве, какое сырье доставляется), чтобы потребности в сырье были обеспечены при минимальных расходах на перевозки. 2. Постройка участка магистрали. Сооружается участок железнодорожной магистрали. В нашем распоряжении – определенное количество средств: людей, строительных машин, ремонтных мастерских, грузовых автомобилей и т.д. Требуется спланировать строительство (т.е. назначить очередность работ, распределить машины и людей по участкам пути, обеспечить ремонтные работы) так, чтобы оно было завершено в минимально возможный срок. 3. Выборочный контроль продукции. Завод выпускает определенного вида изделия. Для обеспечения их высокого качества организуется система выборочного контроля. Требуется разумно организовать контроль (т.е. выбрать размер контрольной партии, набор тестов, правил браковки и т.д.) так, чтобы обеспечить заданный уровень качества при минимальных расходах на контроль. В каждом из приведенных примеров хорошо видны основные признаки: организация некоторого процесса (мероприятия) и цель, которую преследует этот процесс. Введем основные понятия и принципы исследования операций. Операцией называется всякая система действий, объединённых единым замыслом и направленная к достижению некоторой определенной цели (все вышеприведенные задачи являются «операциями»). Операция – это всегда управляемый процесс (управляемое мероприятие). От лица, принимающего решение, зависит, каким способом выбрать некоторые параметры, характеризующие её организацию. Оптимальными называются решения, по тем или другим признакам предпочтительные перед другими. Цель исследования операций (и, в частности, линейного программирования) - это предварительное количественное обоснование оптимальных решений [Вентцель, c.15, 1980]. Элементами решения могут быть представлены не только конкретными числа (например, оптимальное количество продаваемого товара), но и векторами, функциями, физическими признаками. Например, перед руководством завода поставлена задача увеличения прибыли предприятия от реализации производимой продукции. В этом случае элементами решения будут объемы выпускаемого товара при заданных ограничениях на производства и цене реализации продукции. Если решается задача о перевозке определенного количества груза из множества пунктов отправки во множество пунктов назначения, то совокупность чисел 2 показывающее, какое количество груза будет отправлено из пункта отправления в пункт назначения, будет образовывать решение задачи. Для того чтобы вычленить из всех совокупностей решений самое эффективное необходимо иметь некоторый количественный критерий, так называемый показатель эффективности. Этот показатель должен отражать, нести в себе цель выполняемой операции. Часто в литературе, посвященной исследованию операций, линейному программированию в частности, такой критерий называется целевая функция. В наших занятиях мы будем называть такой количественный критерий также. Выпишем для приведенных выше задач целевую функцию. 1. План снабжения предприятий. Задача операции – обеспечить снабжение сырьем при минимальных расходах на перевозки. Показатель эффективности – суммарные расходы на перевозки сырья за единицу времени, например, месяц ( → ). 2. Постройка участка магистрали. Требуется так спланировать строительство, чтобы закончить его как можно скорее. Естественным показателем эффективности было бы время завершения стройки, если бы оно не было связано со случайными факторами (отказы техники, задержки в выполнении отдельных работ). Поэтому в качестве показателя эффективности можно выбрать среднее ожидаемое время ̅ окончания стройки ( ̅ → ). 3. Выборочный контроль продукции. Естественный показатель эффективности – это средние ожидаемые расходы на контроль за единицу времени, при условии, что система контроля обеспечивает заданный уровень качества, например, средний процент брака не выше заданного ( → ). После представленных разъяснений введем несколько определений. Определение 1. Линейное программирование (ЛП) – это область математического программирования, являющегося разделом математики и изучающего методы решения экстремальных (наибольших и наименьших) значений линейной функции конечного числа переменных, на неизвестные переменные которых наложены линейные ограничения [Красс, Чупрынов, c.255, 2007]. В этом определении линейная функция не что иное, как наш количественный критерий, который мы уже условились называть целевой функцией. В свою очередь, линейные ограничения – это та система объективных условий и требований со стороны экономических реалий (экономических задач), которая выступает сдерживающим фактором в нашей хозяйственной деятельности, например, ограничивает нас в производстве. С точки зрения математики, эти ограничения представляются в виде количественных соотношений между переменными и записываются уравнениями или неравенствами. Определение 2. Совокупность соотношений, состоящая из линейной целевой функции и линейных ограничений на ее переменные, называется математической моделью задачи линейного программирования. Запишем математическую модель линейного программирования в общем виде. Целевая функция: ( ) → ( ) (1.1) Система ограничений при данной целевой функции: { где – неизвестные; (1.2) , , – заданные постоянные величины. 3 Представленная математическая модель может быть записана в свернутом виде: Целевая функция: ( ) ∑ → ( ) Система ограничений при данной целевой функции: ∑ Отметим важный момент в математической записи задачи линейного программирования, если все ограничения имеющейся системы (1.2) являются уравнениями, а переменные положительны, то модель такого вида есть каноническая. Если система ограничений имеет в своей структуре неравенства (пусть даже одно), то модель неканоническая. Для того чтобы составить математическую модель необходимо выполнить следующее: 1. Ввести переменные (обозначить их); 2. Определить цель задачи и в соответствии с поставленной целью составить целевую функцию; 3. Зная о параметрах задачи и количественном выражении этих параметров, составить систему ограничений. На текущий момент мы обозначили два способа записи задачи линейного программирования (развернутый и краткий). Я предлагаю читателю подумать над тем, какой способ записи задачи линейного программирования существует дополнительно. В качестве подсказки, могу сказать, что основным элементом такой записи является объект линейной алгебры. Сейчас попробуем перейти от словестной постановки задачи к ее записи в виде задачи линейного программирования. Задача 1. Задача о планировании производства. Предприятие производит изделия трех видов: . По каждому виду изделия предприятию определен план, по которому оно должно выпустить не менее единиц изделия , не менее единиц изделия и не менее единиц изделия . План может быть перевыполнен, но в определенных пределах; условия спроса ограничивают количества произведенных единиц каждого типа: не более соответственно единиц. На изготовление изделий идет какое-то сырье; всего имеется четыре вида сырья: , причем запасы этого сырья ограничены значениями единиц каждого вида сырья. Укажем, какое количество сырья каждого вида расходуется на изготовление каждого вида изделия. Через обозначим количество единиц сырья вида , необходимое на изготовление одной единицы изделия . Первый индекс у числа – вид изделия, второй – вид сырья. Для того чтобы упростить представление о распределении ресурсов для производства изделий сведем эти значения в таблицу 1.1. Таблица 1.1. Распределение необходимого количества сырья для производства изделия. Сырье Изделия 4 При реализации одно изделие приносит предприятию прибыль , – прибыль , – прибыль . Необходимо так спланировать производство (сколько каких изделий производить), чтобы план был выполнен или перевыполнен (но при отсутствии «затоваривания»), а суммарная прибыль обращалась в максимум. Решение. Элементами решения будут – количеств единиц изделий , которые предприятие произведет. Обязательность выполнения плана производства запишется в виде трех ограничений-неравенств: (1.3) Отсутствие излишней продукции (затоваривания) дает дополнительные ограничениянеравенства: (1.4) Кроме того, нам должно хватить сырья. Соответственно четырем видам сырья будем иметь четыре ограничения-неравенства: { (1.5) 5 Не стоит путаться в индексах при постоянной и общей постановке задачи ЛП – наличие индексов именно в таком порядке обусловлено тем, как они расположены в таблице. Таблица может быть с легкостью переписаны, а индексы в ограничениях этой задачи будут советовать тем индексам, которые записаны в (1.2). ) будет равна Прибыль, приносимая планом ( ( ) ∑ → (1.6) Как видно, это типичная задача линейного программирования, в которой необходимо найти такие неотрицательные значения переменных , чтобы они удовлетворяли неравенствам-ограничениям (1.3) – (1.5) и вместе с тем обращали в максимум линейную целевую функцию (1.6). Предлагаю читателю самостоятельно выполнить построение задачи линейного программирования в математической форме. Задача 2. Предприятие может работать по пяти технологическим процессам, причем количество единиц выпускаемой продукции по разным технологическим процессам за 1 ед. времени соответственно равно 300, 260, 320, 400 и 450 шт. В процессе производства учитываются следующие факторы: сырье, электроэнергия, зарплата и накладные расходы. Затраты соответствующих факторов при работе по разным технологическим процессам в течении 1 ед. времени указаны в нижеследующей таблице. Таблица 1.2. Расходы ресурсов по технологическим процессам. Производственные Затраты при различных технологиях Лимит факторы Сырье 15 18 12 14 20 5000 Электроэнергия 0,2 0,3 0,25 0,15 0,25 400 Оплата труда 60 50 80 60 70 16000 Накладные расходы 15 18 20 10 19 10000 Найти программу максимального выпуска продукции. На этом первая лекция окончена. На следующей лекции мы изучим методы решения таких и подобных задач, узнаем, почему геометрически можно решить задачу с ограниченным числом неизвестных и выясним, что MS Excel имеет в своем арсенале не только формулы. Успехов, встретимся на следующих лекциях и страницах форума! 6