15. Аналитические методы. Методы линейного программирования.

15.1. Аналитические методы

На протяжении всей своей эволюции человек, совершая те или иные деяния, стремился вести себя таким образом, чтобы результат, достигаемый как следствие некоторого поступка, оказался в определенном смысле наилучшим. Двигаясь из одного пункта в другой, он стремился найти кратчайший среди возможных путь. Строя жилище, он искал такую его геометрию, которая при наименьшем расходе топлива, обеспечивала приемлемо комфортные условия существования. Занимаясь строительством кораблей, он пытался придать им такую форму, при которой вода оказывала бы наименьшее сопротивление. Можно легко продолжить перечень подобных примеров.

Наилучшие в определенном смысле решения задач принято называть оптимальными . Без использования принципов оптимизации в настоящее время не решается ни одна более или менее сложная проблема. При постановке и решении задач оптимизации возникают два вопроса: что и как оптимизировать?

Ответ на первый вопрос получается как результат глубокого изучения проблемы, которую предстоит решить. Выявляется тот параметр, который определяет степень совершенства решения возникшей проблемы. Этот параметр обычно называют целевой функцией иликритерием качества . Далее устанавливается совокупность величин, которые определяют целевую функцию. Наконец, формулируются все ограничения, которые должны учитываться при решении задачи. После этого строится математическая модель, заключающаяся в установлении аналитической зависимости целевой функции от всех аргументов и аналитической формулировки сопутствующих задаче ограничений. Далее приступают к поиску ответа на второй вопрос.

Итак, пусть в результате формализации прикладной задачи установлено, что целевая функция , где множество Х – обобщение ограничений, его называют множеством допустимых решений. Существо проблемы оптимизации заключается в поиске на множестве Х – множестве допустимых решений такого решения
, при котором целевая функцияf достигает наименьшего или наибольшего значения.

Составной частью методов оптимизации является линейное программирование.

15.2. Основные понятия линейного программирования

Первое упоминание (1938 г.) о математических методах в эффективном управлении производством принадлежит советскому математику Л. В. Канторовичу. Год спустя,в 1939 г., Л. В. Канторович опубликовал работу «Математические методы организации и планирования производства» и практически применил полученные результаты. Термин «линейное программирование» ввели американские математики Дж. Данциг и Т. Купманс в конце 40-х годов. Дж. Данциг разработал математический аппарат симплексного метода решения задач линейного программирования (1951 г.). Симплексный метод находит применение для решения широкого круга задач линейного программирования и до настоящего времени является одним из основных методов.

Линейное программирование - это раздел математики, ориентированный на нахождение экстремума (максимума или минимума) в задачах, которые описываются линейными уравнениями. Причем линейными уравнениями описывается как сама целевая функция, так и входные параметры (переменные) условия ограничений на входные параметры. Необходимым условием задач линейного программирования является обязательное наличие ограничений на ресурсы (сырье, материалы, финансы, спрос произведенной продукции и т.д.). Другим важным условием решения задачи является выбор критерия останова алгоритма, т. е. целевая функция должна быть оптимальна в некотором смысле. Оптимальность целевой функции должна быть выражена количественно. Если целевая функция представлена одним или двумя уравнениями, то на практике такие задачи решаются достаточно легко. Критерий останова алгоритма (или критерий оптимальности) должен удовлетворять следующим требованиям:

быть единственным для данной задачи;

измеряться в единицах количества;

линейно зависеть от входных параметров.

Исходя из вышесказанного, можно сформулировать задачу линейного программирования в общем виде:

найти экстремум целевой функции

при ограничениях в виде равенств:

(2.2)

при ограничениях в виде неравенств:

(2.3)

и условиях неотрицательности входных параметров:

В краткой форме задача линейного программирования может быть записана так:

(2.5)

при условии

где
- входные переменные;

Числа положительные, отрицательные и равные нулю.

В матричной форме эта задача может быть записана так:

Задачи линейного программирования можно решить аналитически и графически.

15.3. Каноническая задача линейного программирования

, i=1,…,m,

, j=1,…,n.

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

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

Необходимо максимизировать (минимизировать) линейную функцию от n переменных.

при ограничениях

, i =1,…, k ,

, i =1+ k ,…, m ,

, …,

Здесь k ≤ m , r ≤ n . Стандартная задача получается как частный случай общей приk = m , r = n ; каноническая – приk =0, r = n .

Пример.

Кондитерская фабрика производит несколько сортов конфет. Назовем их условно "A", "B" и "C". Известно, что реализация десяти килограмм конфет "А" дает прибыль 90 рублей, "В" - 100 рублей и "С" - 160 рублей. Конфеты можно производить в любых количествах (сбыт обеспечен), но запасы сырья ограничены. Необходимо определить, каких конфет и сколько десятков килограмм необходимо произвести, чтобы общая прибыль от реализации была максимальной. Нормы расхода сырья на производство 10 кг конфет каждого вида приведены в таблице 1.

Таблица 1. Нормы расходов сырья

на производство

Экономико-математическая формулировка задачи имеет вид

Найти такие значения переменных Х=(х1, х2, х3) , чтобы

целевая функция

при условиях-ограничениях:

Линейное программирование представляет собой методы решения определенного класса задач по нахождению крайних значений (шах или min). Они основаны на решении системы линейных уравнений, когда зависимость строго функциональна. В модели линейного программирования выделяются три составные части: целевая (максимизируемая или минимизируемая) функция, система ограничений и условие неотрицательности переменных. Математический аппарат линейного программирования используется при решении задач экономических, технических, военных и др.

В экономических задачах оптимального планирования решение целевой функции сводится к нахождению максимума, например, прибыли, объема производства, производительности труда или минимума текущих затрат, капиталовложений, времени выполнения работ и т.п.

В тоже время надо отметить, что не каждая задача оптимального планирования может быть сформулирована и разрешена в рамках линейного программирования. Для этого необходимо соблюсти четыре основных условия.

• 1. В задаче должен быть четко сформулирован и количественно определен критерий оптимальности, что не так легко сделать на практике. О работе предприятия чаще всего судят по ряду показателей: объему производства, ассортименту и качеству выпускаемой продукции, рентабельности производства и др. Выбор одного критерия может оказаться далеко не лучшим с точки зрения другого и наоборот.
• 2. Важной составной частью задачи линейного программирования являются ограничения, связанные с наличными ресурсами, потребностями или другими факторами. В реальной экономике не всегда можно учесть взаимодействие слишком большого количества факторов, поэтому составляется упрощенная модель, которая бы более близко отражала действительный характер.
• 3. Линейное программирование предполагает выбор вариантов и оно применимо только тогда, когда конкретные условия экономической задачи обусловливают эту свободу выбора.
• 4. Модель должна содержать только линейные уравнения или неравенства, т.е. все переменные задачи должны быть в первой степени. Реальные экономические зависимости не всегда носят линейный характер.

Учитывая соответствующие условия и приближая экономическую ситуацию для решения задач линейного программирования, необходимо также учитывать, что наложение на переменные величины слишком жестких ограничений может привести к противоречивости всей системы исходных условий задачи.

По характеру решаемых задач методы линейного программирования можно разбить на две группы.

• 1. Универсальные методы. С их помощью могут решаться любые задачи линейного программирования. Самым распространенным из них является симплексный метод , предложенный Дж. Данцигом, метод раз- решаюших множителей , разработанный академиком Л. В. Канторовичем в 1939 г., примерно за 10 лет до его появления за рубежом.
• 2. Специальные методы. Эти методы проще универсальных, но применимы не для всех задач. К ним относятся распределительный метод для решения транспортной задачи, метод разрешающих слагаемых А. Л. Лурье, метод дифференциальных рент А. Л. Брудно, венгерский метод.

К особой группе методов линейного программирования относятся приближенные методы , отличающие от остальных тем, что не гарантируют строго оптимального решения задачи, но они просты и хорошо приспособлены к ручным вычислениям. К ним относятся индексный метод , метод аппроксимации Фогеля и др.

Симплексный метод. Чтобы лучше понять идею симплексного метода, рассмотрим решение задачи оптимизации использования ресурсов с целью достижения максимальной прибыли.

Пример 2.21

Имеется вспомогательное производство, которое использует остающиеся от основного производства материалы. На данном производстве налажен выпуск дверей различного ассортимента: с использованием стекла (ассортимент ЛВС) и без него (ассортимент ДВ). Сбыт данной продукции обеспечен, т.е. продукция может производиться в любых соотношениях, но есть ограничение по количеству рабочих мест в цехе и ресурсам основных материалов. Задача состоит в том, чтобы запланировать цеху ежемесячный выпуск продукции, обеспечивающий наибольшую возможную сумму прибыли.

В задаче не ставится условия обязательного использования всего объема ресурсов. Необходимо, чтобы расход рабочего времени был не больше заданных пределов.

Рассмотрим программу 1, которая предполагает выпуск только дверей ассортимента ДВ, нс используя при этом стекло для их производства.

Если выпускать только ДВ, используя при этом все имеющиеся ресурсы, то их хватит для выпуска:

• - по рабочему времени: 520/9,2 = 56 (шт.);
• - древесине: 24/0,3 = 80 (шт.).

Следовательно, всех ресурсов достаточно для выпуска только 56 дверей.

Прибыль при данном выпуске составит 168 000 руб. (56 3000).

Программа 2 предполагает выпуск только дверей ассортимента ЛВС. В данном случае ресурсов хватит для выпуска:

• - но рабочему времени: 520/4 = 130 (шт.);
• - древесине: 24/0,6 = 40 (шт.);
• - стеклу: 40/2 = 20 (шт.).

Оптимально возможен выпуск только 20 дверей ЛВС, что ограничивается наличием стекла. При этом уйдет 12 м древесины, из оставшейся части возможен еще выпуск 40 шт. дверей ассортимента ДВ. На производство 20 шт. ДВС и 40 шт. ДВ будет потрачено 448 чел.-ч.

Прибыль составит 160 тыс. руб. (20 -2 + 40-3). Значит первая программа предпочтительней. Существуют и другие варианты.

Ограничения данной задачи таковы:

На графике проведем прямую L u соответствующую первому неравенству: Второму неравенству соответствует прямая Ь 2:

Третьему неравенству на графике соответствует прямая, параллельная оси абсцисс L 3:

Поскольку план выпуска должен строиться исходя из всех пяти ограничений задачи, то областью допустимых решений в данном случае будет закрашенный многоугольник.

Максимальное значение целевой функции, найденное в предыдущих расчетах, будет соответствовать точкам прямой:

Многоугольник ограничивает область допустимых решений задачи. Из массы решений нужно выбрать такое, где значение прибыли максимально. В нашем случае эго будет точка пересечения прямых L { и 1 2 . Далее решается система линейных уравнений:

Решая систему, получаем: отсюда прибыль равна:

Если прямая, отвечающая целевой функции (в графическом методе) проходит через вершину многоугольника, то задача имеет единственный оптимальный вариант. Если совпадает со стороной многоугольника, то задача имеет множество решений.

Оптимальное решение должно проходить либо через вершину, либо через сторону многоугольника. Поэтому одна из вершин отвечает оптимальному решению, но неизвестно вначале какая.

Графический метод прост и нагляден, но применение его ограничено.

При трех переменных пришлось бы строить многогранник в многомерной системе координат. При четырех и более переменных графическое изображение невозможно. Но можно представить многомерное пространство абстрактно. Если условие задачи непротиворечиво, то область допустимых значений (ОДЗ) образует выпуклый многоугольник в и-мерном пространстве.

При этом оптимальное решение, если оно существует, обязательно достигается в некоторой вершине многогранника (возможно и более чем в одной).

Таким образом, чтобы найти решение задачи линейного программирования достаточно перебрать варианты, соответствующие вершинам многогранника. Они называются опорными планами. Однако в сложных задачах их может оказаться чрезмерно много и определение опорных планов потребует огромного объема вычислений.

Симплексный метод позволяет осуществить упорядоченный перебор вершин многогранника.

Последовательность расчетов по симплексному методу рассмотрим на примере.

Пример 2.23

Предприятие располагает тремя группами оборудования (I, II, III), па котором изготавливается четыре вида продукции (А, Б, В, Г). Все изделия имеют неограниченный сбыт и, следовательно, предприятие может планировать ассортиментную программу в пределах данной номенклатуры.

Имеются следующие ограничения:

• - наличие основного оборудования;
• - нормы времени на обработку каждого вида изделий на оборудовании каждой группы;
• - величина прибыли, полученная предприятием за единицу конкретного вида изделий.

Требуется получить максимальную прибыль.

Искомый выпуск: х { - изд. А; х 2 - изд. Б; х 3 - изд. В; х 4 - изд. Г.

Максимальная прибыль:

Ограничения:

Для решения задачи симплексным методом все неравенства превращаем в равенства. Для этого вводим в задачу три дополнительные неотрицательные переменные величины: х 5 , х 6 , х 7 и прибавляем их к левой части неравенства:

По своему экономическому смыслу дополнительные переменные есть ни что иное, как неиспользованное время работы конкретного оборудования. Для решения задач симплекс методом составляются специальные симплекс таблицы.

В самой верхней строке записаны коэффициенты целевой функции. Дополнительным переменным соответствуют нулевые коэффициенты. Неиспользованное оборудование не приносит прибыль. Те же нулевые показатели - в столбце С против каждой дополнительной переменной.

В заполнении строки Zj - Cj имеются свои особенности. Рассматривается Zj для каждого столбца. Она получается как сумма произведений величин столбца С на соответствующие коэффициенты столбца j. Поскольку в первоначальном варианте в столбце С находятся 0, то величина Zj для всех столбцов равна 0, а величина Zj - Cj = -Cj. Поэтому в начальном варианте здесь поставлены коэффициенты целевой функции с обратным знаком. Все основные переменные приравнены к 0 и не входят в базис нашей задачи. Дополнительные переменные равны предельным значениям в соответствии с исходными уравнениями. Это означает, что ничего не производится, ресурсы не используются и значение целевой функции равно 0 (прибыль отсутствует).

Решение задачи заключается в последовательном введении в план основных переменных, пока не будет получено оптимальное решение. При этом на каждом этапе расчета можно ввести лишь одну переменную. При этом другая переменная выводится из базы, так как при трех ограничениях в базисе не может быть больше трех переменных.

Поскольку задача решается на max прибыли, начинать надо с наиболее прибыльного изделия. В нашем случае это изд. Г. В базис вводится х 4 . Определим, каким может быть предусмотрен выпуск изд. Г. Это зависит от объема ресурсов и нормативов затрат. На оборудовании группы I можно обработать 3000 изд. (24 000/8), группа II в изготовлении Г не участвует, а группа III может быть использована на обработку 30 000 изд. Принимаем наименьшее из значений (3000 изд.), в таблице в колонку «базис» х 4 ставится на место х 5 (оборудование группы I равняется нулю, так как использовано полностью). Число 8 на пересечении х А и х 5 называется направляющим элементом или генеральным , ключевым , разрешающим.

Строка х 4 в новой таблице получается путем деления строки выводящей переменной х 5 предыдущей таблицы на направляющий элемент. В столбце С проставляется 0,8 - величина прибыли с единицы изд. Г. После этого пересчитывается столбец «план». На оборудовании группы II изд. Г не обрабатывается и в новом варианте фонд его времени остается без изменений (12 000 мин).

Фонд времени оборудования группы III уменьшится на 3000 мин (1 мин х х 3000 шт.), следовательно остаются неиспользованными 27 000 мин. Следующее число столбца «план» - 2400 руб. (0,8 3000) - прибыль при данном варианте. После столбца «план» пересчитываются все остальные столбцы симплексной таблицы, кроме строки вводимой переменной. При этом, следует иметь в виду, что в столбцах всех переменных, входящих в базис, на пересечении одноименных строк и столбцов всегда находится единица, а остальные элементы столбца равны нулю.

Поэтому сразу можно заполнить столбцы х 4 , х 6 и х 7 . Пересчет целесообразно производить по «правилу треугольника». Для того, чтобы рассчитать в новом варианте какой-либо коэффициент, нужно в симплексной таблице найти три числа: число, стоящее на месте этого коэффициента в предыдущем варианте;

• - число, стоящее в той же строке предыдущего варианта, но в столбце вводимой переменной;
• - число, находящееся в новом варианте в одном столбце с искомым коэффициентом, но в строке вновь введенной переменной (элементы этой строки ранее уже были рассчитаны).

Указанные три числа в таблице образуют прямоугольный треугольник. Для определения искомого коэффициента из числа, находящегося в вершине прямого угла необходимо вычесть произведение двух других углов.

Например, для столбца.гр

Производим вычисление:

для коэффициента по строке

для коэффициента строки х 7:

Показатель для строки Zj - Cj можно рассчитать двумя способами:

а) по формуле

б) по правилу «треугольника»:

Аналогично производим расчеты и для других столбцов нового варианта симплексной таблицы.

Теперь необходимо выяснить, является ли второй вариант оптимальным или он может быть улучшен. Для этого просматривается строка Zj - Cj. Если она содержит отрицательные числа, то вариант может быть улучшен.

На 0,3 руб. в расчете на каждую вводимую единицу изделий увеличится прибыль при введении в базис числах! (изд. А) и на 0,1 руб. при введении числах 3 (изд. В). Эти цифры могут показаться противоречащими исходным данным: согласно которым изд. А приносит 0,4 руб. прибыли, В - 0,5 руб. Но дело в том, что на данном этапе задачи введение в план этих изделий вытеснит известное количество ранее введенных изд. Г, чтобы для их производства высвободить оборудование группы I.

На следующем этане целесообразнее ввести х { (изд. А), гак как ему соответствует наибольшее по абсолютной величине отрицательное число. Аналогично предыдущему варианту установим сколько едении изд. А может быть включено в план с учетом того, что он уже содержит выпуск изд. Г. Для этого числа из столбца «план» делим на соответствующие (только положительные) коэффициенты из столбца вводимой переменной х { и из полученных частных выбираем наименьшее:

Отсюда следует, что в новый вариант расчета может быть введено не более 4000 изд. А, гак лимитирующим фактором является оборудование группы II. Следовательно, переменная х { заменит в базисе переменную х в.

На пересечении столбца х х и строки х 6 находим и подчеркиваем направляющий элемент - 3. Далее рассчитываем строку введенной переменной путем деления элементов строки х 6 предыдущего варианта на направляющий элемент. Затем рассчитываем столбец «план»:

Прибыль при новом варианте составит:

По описанному правилу заполняем следующие столбцы. Просматривая строку Zj - Cj видим, что в ней содержатся только нули и положительные элементы, что означает, что вариант 3 является оптимальным решением и не может быть улучшен. В него входят лишь два вида изделий из четырех. Переменная х 3 соответствует в последней строке 0. Это означает, что введение в план на последующем шаге х 3 не увеличит прибыль, но и не уменьшит ее и полученный результат также будет оптимальным. Разделив числа столбца «план» на коэффициенты столбца х 3 и выбрав из полученных минимальное, определяем, что данная переменная должна вводиться в базис на место переменной^. В результате последующих преобразований получаем новый оптимальный план, в котором предусматривается выпуск 2182 изд. А (х {) и 5455 изд. В (.г 3). Найдем еще несколько оптимальных вариантов решения нашей задачи. Вариант /: 50% из первой программы и 50% из второй программы:

Вариант II: 80% из первой программы и 20% из второй программы:

Эти варианты также обеспечивают прибыль в размере 3600 руб.

Наличие нескольких практически равных эффективных планов позволяет определить ряд промежуточных вариантов, что в экономических задачах дает дополнительные возможности для анализа и качественного отбора наиболее приемлемых из них.

При решении задач симплекс методом могут встретиться случаи «вырождения». При т ограничениях невырожденный план всегда содержит т положительных переменных, а остальные п - т переменных задачи в базис не входят и равняются нулю. Однако возможно равенство нулю и одной или нескольких переменных из входящих в базис, т.е. наличие одного или несколько нулей в столбце «план» симплексной таблицы. Такой план и называется вырожденным. При вырожденном плане наличие отрицательных чисел в строке Zj - Cj не означает, что следующий вариант обеспечит увеличение значения целевой функции. Оно может остаться неизмененным, причем на протяжении не только одного, но и нескольких последовательных шагов. Так происходит зацикливание , которое препятствует дальнейшим расчетам и может быть преодолено лишь с помощью специальных приемов.

В настоящее время при решении задач оптимизации широко применяются персональные компьютеры. При этом используется система электронных таблиц «Microsoft Excel ».

Для решения задач оптимизации в MS Excel используют надстройку Поиск решения, которая вызывается из пункта главного меню «Сервис».

Если в версии Excel , установленной на вашем компьютере, отсутствует данный подпункт меню «Сервис», необходимо вызвать пункт меню «Надстройки» и в предложенном списке дополнительных модулей выбрать «Поиск решения».

Рассмотрим на примере использование данной надстройки, решив с ее помощью задачу производственного планирования.

Пример 2.24

Предприятие выпускает продукты А, В, С, D из трех типов ресурсов. Математическая модель имеет следующий вид: шах/(Х) = 7,5я* 1 +3х 2 + 6дг 3 + 12.г 4 (целевая функция - суммарная стоимость выпуска).

Ограничения по запасам ресурсов и неотрицательности переменных таковы:

Составим шаблон в редакторе Excel.

Теперь занесем в данную задачу числовую информацию.

В выделенные пустые ячейки (значения целевой функции и левых частей неравенств) необходимо занести формулы, отображающие связи и отношения между числами на рабочем столе.

Ячейки С 4 - F a называются в Excel изменяемыми (в нашей модели это неизвестные переменные). Поиск решения при их изменении будет находить оптимальное значение целевой функции. Значения, которые первоначально вводят в эти ячейки, обычно нули (незаполненные клетки трактуются по умолчанию как содержащие нулевые значения).

Теперь необходимо ввести формулы. В нашей математической модели целевая функция представляет собой произведение вектора коэффициентов на вектор неизвестных. Действительно, выражение можно рассматривать

как произведение вектора (7, 5, 3, б, 12) на вектор (.г, х 2 , я-*, х А).

В Excel существует функция СУММПРОИЗВ, которая позволяет найти скалярное произведение векторов. Данную функцию необходимо вызвать в ячейку #5, а в качестве перемножаемых векторов задать адреса ячеек, содержащих коэффициенты уравнений (в данном случае, это С5: F5 ), и ячеек, в которые в результате решения будут помещены значения х и х 2 , х 3 , х 4 (ячейки СА : FA).

Каждая левая часть ограничения тоже представляет собой произведение двух векторов: соответствующей строки матрицы затрат и вектора неизвестных. Выражение 2х х + х 2 + 0Дг 3 + 4х л (для первого ограничения 2х, + х 2 + 0,5х 3 + 4 х 4 2400) будем рассматривать как произведение вектора коэффициентов (2,1,0,5,4) и вектора переменных (х и х 2 , х 3 , х 4).

В ячейке, отведенной для формулы левой части первого ограничения ((79), вызовем функцию СУММПРОИЗВ. В качестве адресов перемножаемых векторов занесем адрес строки коэффициентов С9: /0 и адрес значений переменных С4: FA.

В четыре оставшиеся ячейки графы «Левая часть» вводим аналогичные формулы, используя соответствующую строку матрицы затрат. Фрагмент экрана с введенными формулами выглядит следующим образом.

К моменту вызова сервиса «Поиск решения» на рабочий стол с задачей должны быть занесены формулы для левых частей ограничений и формула для значения целевой функции.

В меню «Сервис» выбираем «Поиск решения». В появившемся окне задаем следующую информацию:

• а) в качестве целевой ячейки устанавливаем адрес ячейки для значения целевой функции #5;
• б) «флажок» устанавливаем на вариант «максимальному значению», так как в данном случае целевая функция дохода подлежит максимизации;
• в) в качестве изменяемых ячеек заносится адрес строки значений переменных С4: F4;
• г) справа от окна, предназначенного для занесения ограничений, нажимаем кнопку «Добавить», появится форма для занесения ограничения;

д) в левой части формы «Ссылка на ячейку» заносится адрес формулы для левой части первого ограничения G 9, выбирается требуемый знак неравенства (в нашем случае,

е) аналогично заносятся все ограничения задачи, после чего нажимается кнопка «ОК».

Окно «Поиск решения» с занесенной информацией выглядит следующим образом.

Далее необходимо нажать кнопку «Параметры», установить «флажки» «Линейная модель» и «Неотрицательные значения», поскольку в данном случае задача относится к линейному программированию, а ограничение требует неотрицательности значений.

Затем следует нажать «ОК», «Выполнить», после чего появляется окно результата решения.

Если в результате всех действий получено окно с сообщением «Решение найдено», то вам предоставляется возможность получения трех типов отчета, которые полезны при анализе модели на чувствительность. В данном примере достаточно сохранить найденное решение, нажав «ОК». В результате получено решение задачи.

Если же в результате решения задачи выдано окно с сообщением о невозможности нахождения решения, это означает, что при оформлении задачи была допущена ошибка (не заполнены формулы для ограничений, неправильно установлен «флажок», максимизации (минимизации) и т.д.).

В окне «Поиск решения» имеется кнопка «Параметры».

Установим флажок «Показывать результаты итераций», нажмем «ОК».

Затем нажмем кнопку «Выполнить».

Ms Excel выдаст следующее окно.

На рабочем листе будут показаны результаты первой итерации.

После этого нажимаем кнопку «Продолжить», на рабочем листе отображаются результаты второй итерации.

Снова нажимаем кнопку «Продолжить», на рабочем листе отображаются результаты третьей итерации.

При следующем нажатии кнопки «Продолжить», программа выдает окно «Результаты поиска решения», где необходимо сохранить найденное решение и выбрать тип отчета.

В данном разделе рассмотрен общий формат решения задач оптимизации в Excel. В зависимости от экономических моделей, выполняют его соответствующие модификации.

Отчеты выглядят следующим образом.

1. Отчет по результатам.

2. Отчет по устойчивости.

3. Отчет по пределам.

Теперь рассмотрим пример, в котором математическая модель имеет тот же вид, но ограничения имеют разные знаки.

Пример 2.25

Л. Допустим, математическая модель такова: Она имеет следующие ограничения:

Отчет по устойчивости.

Б. Теперь предположим, что математическая модель имеет другие ограничения:

В данном случае имеем следующие результаты по отчетам.

Отчет по устойчивости.

• Воспользуемся для решения этой же задачи одним из методов линейного программирования - графическим. Пример 2.22 Введем обозначения: х{ - искомое количество дверей ДВ, х2 - искомое количество дверей ДВС.

Линейное программирование – направление математики, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием оптимальности.

Несколько слов о самом термине линейное программирование. Он требует правильного понимания. В данном случае программирование - это, конечно, не составление программ для ЭВМ. Программирование здесь должно интерпретироваться как планирование, формирование планов, разработка программы действий.

К математическим задачам линейного программирования относят исследования конкретных производственно-хозяйственных ситуаций, которые в том или ином виде интерпретируются как задачи об оптимальном использовании ограниченных ресурсов.

Круг задач, решаемых при помощи методов линейного программирования достаточно широк. Это, например:

· задача об оптимальном использовании ресурсов при производственном планировании;

· задача о смесях (планирование состава продукции);

· задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке");

· транспортные задачи (анализ размещения предприятия, перемещение грузов).

Линейное программирование – наиболее разработанный и широко применяемый раздел математического программирования (кроме того, сюда относят: целочисленное, динамическое, нелинейное, параметрическое программирование). Это объясняется следующим:

· математические модели большого числа экономических задач линейны относительно искомых переменных;

· данный тип задач в настоящее время наиболее изучен. Для него разработаны специальные методы, с помощью которых эти задачи решаются, и соответствующие программы для ЭВМ;

· многие задачи линейного программирования, будучи решенными, нашли широкое применение;

· некоторые задачи, которые в первоначальной формулировке не являются линейными, после ряда дополнительных ограничений и допущений могут стать линейными или могут быть приведены к такой форме, что их можно решать методами линейного программирования.

Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных.

В общем виде модель записывается следующим образом:

целевая функция:

F = c1x1 + c2x2 + ... + cnxn → max(min);

ограничения:

a11x1 + a12x2 + ... + a1nxn {≤ = ≥} b1,

a21x1 + a22x2 + ... + a2nxn {≤ = ≥} b2,

am1x1 + am2x2 + ... + amnxn {≤ = ≥} bm;

требование неотрицательности:

Задача состоит в нахождении оптимального значения функции при соблюдении ограничений.

Итак , Линейное программирование – это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием.

Необходимым условием постановки задачи линейного программирования являются ограничения на наличие ресурсов, величину спроса, производственную мощность предприятия и другие производственные факторы.

Сущность линейного программирования состоит в нахождении точек наибольшего или наименьшего значения некоторой функции при определенном наборе ограничений, налагаемых на аргументы и образующих систему ограничений, которая имеет, как правило, бесконечное множество решений. Каждая совокупность значений переменных (аргументов функции F), которые удовлетворяют системе ограничений, называется допустимым планом задачи линейного программирования. Функция F, максимум или минимум которой определяется, называется целевой функцией задачи. Допустимый план, на котором достигается максимум или минимум функции F, называется оптимальным планом задачи.

Система ограничений, определяющая множество планов, диктуется условиями производства. Задачей линейного программирования (ЗЛП) является выбор из множества допустимых планов наиболее выгодного (оптимального).

Симплекс-метод является основным в линейном программировании . Решение задачи начинается с рассмотрений одной из вершин многогранника условий. Если исследуемая вершина не соответствует максимуму (минимуму), то переходят к соседней, увеличивая значение функции цели при решении задачи на максимум и уменьшая при решении задачи на минимум. Таким образом, переход от одной вершины к другой улучшает значение функции цели. Так как число вершин многогранника ограничено, то за конечное число шагов гарантируется нахождение оптимального значения или установление того факта, что задача неразрешима.

Этот метод является универсальным, применимым к любой задаче линейного программирования в канонической форме . Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен r , то мы можем выбрать r неизвестных, которые выразим через остальные неизвестные. Для определенности предположим, что выбраны первые, идущие подряд, неизвестные X 1 , X 2 , ..., X r . Тогда наша система уравнений может быть записана как

К такому виду можно привести любую совместную систему , например, методом Гаусса. Правда, не всегда можно выражать через остальные первые r неизвестных (мы это сделали для определенности записи). Однако такие r неизвестных обязательно найдутся. Эти неизвестные (переменные) называются базисными, остальные свободными.

Придавая определенные значения свободным переменным и вычисляя значения базисных (выраженных через свободные), мы будем получать различные решения нашей системы ограничений. Таким образом, можно получить любое ее решение. Нас будут интересовать особые решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения называются базисными , их столько же, сколько различных базисных видов у данной системы ограничений. Базисное решение называется допустимым базисным решением или опорным решением , если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменные X 1 , X 2 , ..., X r , то решение {b 1 , b 2 ,..., b r , 0, ..., 0} будет опорным при условии, что b 1 , b 2 ,..., b r ≥ 0 .

Симплекс-метод основан на теореме, которая называется фундаментальной теоремой симплекс-метода. Среди оптимальных планов задачи линейного программирования в канонической форме обязательно есть опорное решение ее системы ограничений. Если оптимальный план задачи единственен, то он совпадает с некоторым опорным решением. Различных опорных решений системы ограничений конечное число. Поэтому решение задачи в канонической форме можно было бы искать перебором опорных решений и выбором среди них того, для которого значение F самое большое. Но, во-первых, все опорные решения неизвестны и их нужно находить, a, во-вторых, в реальных задачах этих решений очень много и прямой перебор вряд ли возможен. Симплекс-метод представляет собой некоторую процедуру направленного перебора опорных решений. Исходя из некоторого, найденного заранее опорного решения по определенному алгоритму симплекс-метода мы подсчитываем новое опорное решение, на котором значение целевой функции F не меньше, чем на старом. После ряда шагов мы приходим к опорному решению, которое является оптимальным планом.

Итак, симплексный метод вносит определенный порядок как при нахождении первого (исходного) базисного решения, так и при переходе к другим базисным решениям. Его идея состоит в следующем.

Имея систему ограничений , приведенную к общему виду, то есть к системе m линейных уравнений с n переменными (m < n) , находят любое базисное решение этой системы, заботясь только о том, чтобы найти его как можно проще.

Если первое же найденное базисное решение оказалось допустимым , то проверяют его на оптимальность . Если оно не оптимально , то, осуществляется переход к другому, обязательно допустимому базисному решению .

Симплексный метод гарантирует, что при этом новом решении линейная форма, если и не достигнет оптимума, то приблизится к нему. С новым допустимым базисным решением поступают так же, пока не находят решение, которое является оптимальным.

Если первое найденное базисное решение окажется недопустимым , то с помощью симплексного метода осуществляется переход к другим базисным решениям , которые приближают нас к области допустимых решений, пока на каком-то шаге решения либо базисное решение окажется допустимым и к нему применяют алгоритм симплексного метода, либо мы убеждаемся в противоречивости системы ограничений.

Таким образом, применение симплексного метода распадается на два этапа: нахождение допустимого базисного решения системы ограничений или установление факта ее несовместности; нахождение оптимального решения.
При этом каждый этап может включать несколько шагов, соответствующих тому или иному базисному решению. Но так как число базисных решений всегда ограниченно, то ограниченно и число шагов симплексного метода.

Приведенная схема симплексного метода явно выражает его алгоритмический характер (характер четкого предписания о выполнении последовательных операций), что позволяет успешно программировать и реализовать этот метод на ЭВМ. Задачи же с небольшим числом переменных и ограничений могут быть решены симплексным методом вручную.

Не останавливаясь подробнее на сути алгоритма, опишем его вычислительную сторону. Вычисления по симплекс-методу организуются в виде симплекс-таблиц , которые являются сокращенной записью задачи линейного программирования в канонической форме. Перед составлением симплекс-таблицы задача должна быть преобразована , система ограничений приведена к допустимому базисному виду , c помощью которого из целевой функции должны быть исключены базисные переменные. Вопрос об этих предварительных преобразованиях мы рассмотрим ниже. Сейчас же будем считать, что они уже выполнены и задача имеет вид.

Аннотация: Данная лекция раскрывает ряд вопросов, посвященных линейному программированию как одному из разделов математического программирования; в частности, формулирует основные виды задач линейного программирования, раскрывает отличия данных задач от классических задач математического анализа; знакомит с различными формами записи данных задач, осуществляет их постановку и исследование структуры. Наиболее полно раскрыт вопрос о решении задач линейного программирования симплекс-методом.

1. Понятие математического программирования

– это математическая дисциплина, в которой разрабатываются методы отыскания экстремальных значений целевой функции среди множества ее возможных значений, определяемых ограничениями.

Наличие ограничений делает задачи принципиально отличными от классических задач математического анализа по отысканию экстремальных значений функции. Методы математического анализа для поиска экстремума функции в задачах математического программирования оказываются непригодными.

Для решения задач математического программирования разработаны и разрабатываются специальные методы и теории. Так как при решении этих задач приходится выполнять значительный объем вычислений, то при сравнительной оценке методов большое значение придается эффективности и удобству их реализации на ЭВМ.

Можно рассматривать как совокупность самостоятельных разделов, занимающихся изучением и разработкой методов решения определенных классов задач.

В зависимости от свойств целевой функции и функции ограничений все задачи математического программирования делятся на два основных класса:

• задачи линейного программирования,
• задачи нелинейного программирования .

Если целевая функция и функции ограничений – линейные функции, то соответствующая задача поиска экстремума является задачей линейного программирования. Если хотя бы одна из указанных функций нелинейна, то соответствующая задача поиска экстремума является задачей нелинейного программирования .

2. Понятие линейного программирования. Виды задач линейного программирования

Линейное программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования . Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина " математическое программирование ". Термин "программирование" в названии дисциплины ничего общего с термином "программирование (т.е. составление программы) для ЭВМ" не имеет, т.к. дисциплина " линейное программирование " возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач.

Термин " линейное программирование " возник в результате неточного перевода английского " linear programming ". Одно из значений слова "programming" - составление планов, планирование. Следовательно, правильным переводом английского " linear programming " было бы не " линейное программирование ", а "линейное планирование", что более точно отражает содержание дисциплины. Однако, термины линейное программирование , нелинейное программирование, математическое программирование и т.д. в нашей литературе стали общепринятыми и поэтому будут сохранены.

Итак, линейное программирование возникло после второй мировой войны и стало быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а также математической стройности.

Можно сказать, что линейное программирование применимо для решения математических моделей тех процессов и систем, в основу которых может быть положена гипотеза линейного представления реального мира.

Линейное программирование применяется при решении экономических задач, в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; в задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д.

Задача линейного программирования (ЛП), как уже ясно из сказанного выше, состоит в нахождении минимума (или максимума) линейной функции при линейных ограничениях.

Общая форма задачи имеет вид: найти при условиях

Наряду с общей формой широко используются также каноническая и стандартная формы. Как в канонической, так и в стандартной форме

Т.е. все переменные в любом допустимом решении задачи должны принимать неотрицательные значения (такие переменные принято называть неотрицательные в отличие от так называемых свободных переменных, на область значений которых подобное ограничение не накладывается). Отличие же между этими формами состоит в том, что в одном случае I 2 = 0 , а в другом - I 1 = 0 .

Задача ЛП в канонической форме.

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

Линейное программирование - математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах -мерного векторного пространства , задаваемых системами линейных уравнений и неравенств.

Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования . Одновременно оно - основа нескольких методов решения задач целочисленного и нелинейного программирования . Одним из обобщений линейного программирования является дробно-линейное программирование .

Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их.

История

Метод внутренних точек был впервые упомянут И. И. Дикиным в 1967 году .

Задачи

Основной (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы) вида :

при условиях

Задача линейного программирования будет иметь канонический вид , если в основной задаче вместо первой системы неравенств имеет место система уравнений :

Основную задачу можно свести к канонической путём введения дополнительных переменных.

Задачи линейного программирования наиболее общего вида (задачи со смешанными ограничениями: равенствами и неравенствами, наличием переменных, свободных от ограничений) могут быть приведены к эквивалентным (имеющим то же множество решений) заменами переменных и заменой равенств на пару неравенств .

Легко заметить, что задачу нахождения максимума можно заменить задачей нахождения минимума, взяв коэффициенты с обратным знаком.

Примеры задач

Максимальное паросочетание

Рассмотрим задачу о максимальном паросочетании в двудольном графе : есть несколько юношей и девушек, причём для каждых юноши и девушки известно, симпатичны ли они друг другу. Нужно поженить максимальное число пар со взаимной симпатией.

Введём переменные , которые соответствуют паре из -того юноши и -той девушки и удовлетворяют ограничениям:

с целевой функцией . Можно показать, что среди оптимальных решений этой задачи найдётся целочисленное. Переменные, равные 1, будут соответствовать парам, которые следует поженить.

Максимальный поток

Пусть имеется граф (с ориентированными рёбрами), в котором для каждого ребра указана его пропускная способность. И заданы две вершины: сток и исток. Нужно указать для каждого ребра, сколько через него будет протекать жидкости (не больше его пропускной способности) так, чтобы максимизировать суммарный поток из истока в сток (жидкость не может появляться или исчезать во всех вершинах, кроме стока и истока).

Возьмём в качестве переменных - количество жидкости, протекающих через -тое ребро. Тогда

где - пропускная способность -того ребра. Эти неравенства надо дополнить равенством количества втекающей и вытекающей жидкости для каждой вершины, кроме стока и истока. В качестве функции естественно взять разность между количеством вытекающей и втекающей жидкости в истоке.

Обобщение предыдущей задачи - максимальный поток минимальной стоимости. В этой задаче даны стоимости для каждого ребра и нужно среди максимальных потоков выбрать поток с минимальной стоимостью. Эта задача сводится к двум задачам линейного программирования: сначала нужно решить задачу о максимальном потоке, а потом добавить к этой задаче ограничение , где - величина максимального потока, и решить задачу с новой функцией - стоимостью потока.

Эти задачи могут быть решены быстрее, чем общими алгоритмами решения задач линейного программирования, за счёт особой структуры уравнений и неравенств.

Транспортная задача

Имеется некий однородный груз, который нужно перевести с складов на заводов. Для каждого склада известно, сколько в нём находится груза , а для каждого завода известна его потребность в грузе. Стоимость перевозки пропорциональна расстоянию от склада до завода (все расстояния от -го склада до -го завода известны). Требуется составить наиболее дешёвый план перевозки.

Решающими переменными в данном случае являются - количества груза, перевезённого из -го склада на -й завод. Они удовлетворяют ограничениям:

Целевая функция имеет вид: , которую надо минимизировать.

Игра с нулевой суммой

Есть матрица размера . Первый игрок выбирает число от 1 до , второй - от 1 до . Затем они сверяют числа и первый игрок получает очков, а второй очков ( - число, выбранное первым игроком, - вторым). Нужно найти оптимальную стратегию первого игрока.

Пусть в оптимальной стратегии, например, первого игрока число нужно выбирать с вероятностью . Тогда оптимальная стратегия является решением следующей задачи линейного программирования:

в которой нужно максимизировать функцию . Значение в оптимальном решении будет математическим ожиданием выигрыша первого игрока в наихудшем случае.

Алгоритмы решения

Наиболее известным и широко применяемым на практике для решения общей задачи линейного программирования (ЛП) является симплекс-метод . Несмотря на то, что симплекс-метод является достаточно эффективным алгоритмом, показавшим хорошие результаты при решении прикладных задач ЛП, он является алгоритмом с экспоненциальной сложностью . Причина этого состоит в комбинаторном характере симплекс-метода, последовательно перебирающего вершины многогранника допустимых решений при поиске оптимального решения.

Первый полиномиальный алгоритм , метод эллипсоидов , был предложен в 1979 году советским математиком Л. Хачияном , разрешив таким образом проблему, долгое время остававшуюся нерешённой. Метод эллипсоидов имеет совершенно другую, некомбинаторную, природу, нежели симплекс-метод. Однако в вычислительном плане этот метод оказался неперспективным. Тем не менее, сам факт полиномиальной сложности задач привёл к созданию целого класса эффективных алгоритмов ЛП - методов внутренней точки , первым из которых был алгоритм Н. Кармаркара, предложенный в 1984 году . Алгоритмы этого типа используют непрерывную трактовку задачи ЛП, когда вместо перебора вершин многогранника решений задачи ЛП осуществляется поиск вдоль траекторий в пространстве переменных задачи, не проходящих через вершины многогранника. Метод внутренних точек, который, в отличие от симплекс-метода, обходит точки из внутренней части области допустимых значений, использует методы логарифмических барьерных функций нелинейного программирования , разработанные в 1960-х годах Фиако (Fiacco) и МакКормиком (McCormick).

См. также

• Графический метод решения задачи линейного программирования

Примечания

Литература

• Томас Х. Кормен и др. Глава 29. Линейное программирование // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. - 2-е изд. - М .: «Вильямс», 2006. - С. 1296. - ISBN 5-8459-0857-4
• Акулич И.Л. Глава 1. Задачи линейного программирования, Глава 2. Специальные задачи линейного программирования // Математическое программирование в примерах и задачах. - М .: Высшая школа, 1986. - 319 с. - ISBN 5-06-002663-9
• Карманов В. Г. Математическое программирование. - 3-е издание. - М .: Наука, 1986. - 288 с.
• Данциг Джордж Бернард «Воспоминания о начале линейного программирования»

Ссылки

• - Бесплатный оптимизационный пакет, предназначенный для решения задач линейного, целочисленного и целевого программирования.
• Вершик А. М. «O Л. В. Канторовиче и линейном программировании »
• Большакова И. В., Кураленко М. В. «Линейное программирование. Учебно-методическое пособие к контрольной работе ».
• Барсов А. С. «Что такое линейное программирование », Популярные лекции по математике , Гостехиздат, 1959.
• М. Н. Вялый Линейные неравенства и комбинаторика . - МЦНМО , 2003.

Wikimedia Foundation . 2010 .

• Зальтен, Феликс
• Глагов, Мартина

Смотреть что такое "Линейное программирование" в других словарях:

линейное программирование - — линейное программирование Область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между… … Справочник технического переводчика

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

Линейное программирование - область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между переменными. В самом общем виде задачу Л.п. можно записать так. Даны… … Экономико-математический словарь