Метод линейного программирования относится к группе. Понятие линейного программирования

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

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

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

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

Линейное программирование применяется при решении следующих экономических задач:

1. Задача управления и планирования производства.

2. Задач определения оптимального размещения оборудования на морских судах, в цехах.

3. Задача определения оптимального плана перевозок груза (транспортная задача).

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

5. Задач о смесях, диете (планирование состава продукции) и т.д.

3. МОДЕЛЬ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ, ЕЁ ПРЕДСТАВЛЕНИЕ В ЭЛЕКТРОННЫХ ТАБЛИЦАХ MS EXCEL.

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

Основные этапы создания модели линейного программирования в Excel:

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

2. Создание и отладка табличной модели линейного программирования. На основе символической модели ЛП создается ее представление в Excel.

3. Попытка оптимизации модели с помощью надстройки ПОИСК РЕШЕНИЯ.

4. ИСПОЛЬЗОВАНИЕ НАДСТРОЙКИ ПОИСК РЕШЕНИЯ .

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

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

Общий алгоритм работы с надстройкой Поиск решения.

1. В меню Сервис выбрать команду Поиск решения .
2. В поле Установит целевую ячейку введите адрес ячейки, в которй находится формула, для оптимизации модели.
3. Для того, чтобы максимизировать значение целевой ячейки путем изменения значений влияющих ячеек, установите переключатель в положение Максимальному значению . Для того, чтобы минимизировать значение целевой ячейки путем изменения значений влияющих ячеек, установите переключатель в положение Минимальному значению . Для того, чтобы целевая ячейка приобретала значение конкретного числа, установите переключатель в положение Значение и введите соответствующее число.
4. В поле Изменяя ячейки введите адреса ячеек, которые изменяют свои значения, разделяя их запятыми. Изменяемые ячейки должны быть прямо или непрямо связанные с целевой ячейкой. Допускается установка до 200 изменяемых ячеек.
5. В поле Ограничения введите все ограничения, которые налагаются на поиск решения.
6. Нажмите кнопку Выполнить .
7. Для сохранения найденного решения установите переключатель в диалоговом окне Результаты поиска решения в положение Сохранить найденное решение . Для возобновления входных данных установите переключатель в положение Восстановить исходные значения.
8. Для того, чтобы прервать поиск решения, нажмите клавишу Еsс . MS Excel пересчитает лист с учетом найденных значений ячеек, которые влияют на результат.

Алгоритм роботи з надбудовою Поиск решения.

5. РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПРИ ПОМОЩИ ПРОГРАММЫ MS EXCEL.

Пример. Кондитерский цех для изготовления трех видов карамели А, В, С использует три основных вида сырья: сахар, патоку и фруктовое пюре. Нормы затрат сахара на изготовление 1кг карамели каждого вида соответственно уровни: 0,8кг; 0,5кг; 0,6кг; патоки – 04кг; 0,4кг; 0,3кг; фруктового пюре – 0кг; 0,1кг; 0,1кг. Конфеты можно производить в любых количествах (реализация обеспечена), но запас сырья ограниченный: запасы сахара – 80кг, патоки – 60кг, фруктового пюре – 12кг. Прибыль от реализации 1кг карамели вида А составляет 10грн., вида В – 11грн., вида С – 12грн.

Таблица 1

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

Линейное программирование представляет собой методы решения определенного класса задач по нахождению крайних значений (шах или 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 - искомое количество дверей ДВС.

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

Основное содержание симплексного метода заключается в следующем:

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

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

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

1. Привести задачу к каноническому виду
2. Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости системы ограничений)
3. Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода
4. Если выполняется признак единственности оптимального решения, то решение задачи заканчивается
5. Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения

Пример решения задачи симплексным методом

Пример 26.1

Решить симплексным методом задачу:

Решение:

Приводим задачу к каноническому виду.

Для этого в левую часть первого ограничения-неравенства вводим дополнительную переменную x 6 с коэффициентом +1. В целевую функцию переменная x 6 входит с коэффицентом ноль (т.е. не входит).

Получаем:

Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю х1 = х2 = х3 = 0.

Получаем опорное решение Х1 = (0,0,0,24,30,6) с единичным базисом Б1 = (А4, А5, А6).

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

Δ k = C б X k — c k

• C б = (с 1 , с 2 , ... , с m) — вектор коэффициентов целевой функции при базисных переменных
• X k = (x 1k , x 2k , ... , x mk) — вектор разложения соответствующего вектора А к по базису опорного решения
• С к — коэффициент целевой функции при переменной х к.

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

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

В последней строке таблицы с оценками Δ k в столбце "А 0 " записываются значения целевой функции на опорном решении Z(X 1).

Начальное опорное решение не является оптимальным, так как в задаче на максимум оценки Δ 1 = -2, Δ 3 = -9 для векторов А 1 и А 3 отрицательные.

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

Определим, введение какого из двух векторов приведет к большему приращению целевой функции.

Приращение целевой функции находится по формуле: .

Вычисляем значения параметра θ 01 для первого и третьего столбцов по формуле:

Получаем θ 01 = 6 при l = 1, θ 03 = 3 при l = 1 (таблица 26.1).

Находим приращение целевой функции при введении в базис первого вектора ΔZ 1 = — 6*(- 2) = 12, и третьего вектора ΔZ 3 = — 3*(- 9) = 27.

Следовательно, для более быстрого приближения к оптимальному решению необходимо ввести в базис опорного решения вектор А3 вместо первого вектора базиса А6, так как минимум параметра θ 03 достигается в первой строке (l = 1).

Производим преобразование Жордана с элементом Х13 = 2, получаем второе опорное решение Х2 = (0,0,3,21,42,0) с базисом Б2 = (А3, А4, А5). (таблица 26.2)

Это решение не является оптимальным, так как вектор А2 имеет отрицательную оценку Δ2 = — 6. Для улучшение решения необходимо ввести вектор А2 в базис опорного решения.

Определяем номер вектора, выводимого из базиса. Для этого вычисляем параметр θ 02 для второго столбца, он равен 7 при l = 2. Следовательно, из базиса выводим второй вектор базиса А4. Производим преобразование Жордана с элементом х 22 = 3, получаем третье опорное решение Х3 = (0,7,10,0,63,0) Б2 = (А3, А2, А5) (таблица 26.3).

Это решение является единственным оптимальным, так как для всех векторов, не входящих в базис оценки положительные

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Ответ: max Z(X) = 201 при Х = (0,7,10,0,63).

Метод линейного программирования в экономическом анализе

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Назначение сервиса . Онлайн-калькулятор предназначен для решения задач линейного программирования симплексным методом путем перехода к КЗЛП и СЗЛП . При этом задача на минимум целевой функции сводятся к задаче на поиск максимума через преобразование целевой функции F*(X) = -F(X) . Также имеется возможность составить двойственную задачу .

Решение происходит в три этапа:

1. Переход к КЗЛП. Любая ЗЛП вида ax ≤ b , ax ≥ b , ax = b (F(X) → extr) сводится к виду ax = b , F(X) → max ;
2. Переход к СЗЛП. КЗЛП вида ax = b сводится к виду ax ≤ b , F(X) → max ;
3. Решение симплексным методом;

Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word .

Количество переменных 2 3 4 5 6 7 8 9 10
Количество строк (количество ограничений) 1 2 3 4 5 6 7 8 9 10

Переход от задачи минимизации целевой функции к задаче максимизации

Задача минимизации целевой функции F(X) легко может быть сведена к задаче максимизации функции F*(X) при тех же ограничениях путем введения функции: F*(X) = -F(X) . Обе задачи имеют одно и то же решение X*, и при этом min(F(X)) = -max(F*(X)) .
Проиллюстрируем этот факт графически:

F(x) → min

F(x) → max

Для оптимизации функции цели используем следующие понятия и методы.
Опорный план – план с определёнными через свободные базисными переменными.
Базисный план – опорный план с нулевыми базисными переменными.
Оптимальный план – базисный план, удовлетворяющий оптимальной функции цели (ФЦ).

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

Переменные x 1 , …, x m , входящие с единичными коэффициентами только в одно уравнение системы, с нулевыми - в остальные, называются базисными или зависимыми . В канонической системе каждому уравнению соответствует ровно одна базисная переменная. Переход осуществляется с помощью метода Гаусса-Жордана . Основная идея этого метода состоит в сведении системы m уравнений с n неизвестными к каноническому виду при помощи элементарных операций над строками.
Остальные n-m переменных (x m +1 ,…, x n) называются небазисными или независимыми переменными .

Базисное решение называется допустимым базисным решением , если значения входящих в него базисных переменных x j ≥0, что эквивалентно условию неотрицательности b j ≥0.
Допустимое базисное решение является угловой точкой допустимого множества S задачи линейного программирования и называется иногда опорным планом .
Если среди неотрицательных чисел b j есть равные нулю, то допустимое базисное решение называется вырожденным (вырожденной угловой точкой) и соответствующая задача линейного программирования называется вырожденной .

Пример №1 . Свести задачу линейного программирования к стандартной ЗЛП.
F(X) = x 1 + 2x 2 - 2x 3 → min при ограничениях:
4x 1 + 3x 2 - x 3 ≤10
- 2x 2 + 5x 3 ≥3
x 1 + 2x 3 =9
Для приведения ЗЛП к канонической форме необходимо:
1. Поменять знак у целевой функции. Сведем задачу F(X) → min к задаче F(X) → max. Для этого умножаем F(X) на (-1). В первом неравенстве смысла (≤) вводим базисную переменную x 4 ; во втором неравенстве смысла (≥) вводим базисную переменную x 5 со знаком минус.
4x 1 + 3x 2 -1x 3 + 1x 4 + 0x 5 = 10
0x 1 -2x 2 + 5x 3 + 0x 4 -1x 5 = 3
1x 1 + 0x 2 + 2x 3 + 0x 4 + 0x 5 = 9
F(X) = - x 1 - 2x 2 + 2x 3
Переход к СЗЛП .
Расширенная матрица системы ограничений-равенств данной задачи:

4	3	-1	1	0	10
0	-2	5	0	-1	3
1	0	2	0	0	9

Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x 4 .
2. В качестве базовой переменной выбираем x 2 .
Разрешающий элемент РЭ=-2. Строка, соответствующая переменной x 2 , получена в результате деления всех элементов строки x 2 на разрешающий элемент РЭ=-2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x 2 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:

4-(0 3):-2	3-(-2 3):-2	-1-(5 3):-2	1-(0 3):-2	0-(-1 3):-2	10-(3 3):-2
0: -2	-2: -2	5: -2	0: -2	-1: -2	3: -2
1-(0 0):-2	0-(-2 0):-2	2-(5 0):-2	0-(0 0):-2	0-(-1 0):-2	9-(3 0):-2

Получаем новую матрицу:

4	0	6 1 / 2	1	-1 1 / 2	14 1 / 2
0	1	-2 1 / 2	0	1 / 2	-1 1 / 2
1	0	2	0	0	9

3. В качестве базовой переменной выбираем x 3 .
Разрешающий элемент РЭ=2. Строка, соответствующая переменной x 3 , получена в результате деления всех элементов строки x 3 на разрешающий элемент РЭ=2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x 3 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:

4-(1 6 1 / 2):2	0-(0 6 1 / 2):2	6 1 / 2 -(2 6 1 / 2):2	1-(0 6 1 / 2):2	-1 1 / 2 -(0 6 1 / 2):2	14 1 / 2 -(9 6 1 / 2):2
0-(1 -2 1 / 2):2	1-(0 -2 1 / 2):2	-2 1 / 2 -(2 -2 1 / 2):2	0-(0 -2 1 / 2):2	1 / 2 -(0 -2 1 / 2):2	-1 1 / 2 -(9 -2 1 / 2):2
1: 2	0: 2	2: 2	0: 2	0: 2	9: 2

Получаем новую матрицу:

3 / 4	0	0	1	-1 1 / 2	-14 3 / 4
1 1 / 4	1	0	0	1 / 2	9 3 / 4
1 / 2	0	1	0	0	4 1 / 2

Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (4,2,3).
Соответствующие уравнения имеют вид:
3 / 4 x 1 + x 4 - 1 1 / 2 x 5 = -14 3 / 4
1 1 / 4 x 1 + x 2 + 1 / 2 x 5 = 9 3 / 4
1 / 2 x 1 + x 3 = 4 1 / 2
Выразим базисные переменные через остальные:
x 4 = - 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4
x 2 = - 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4
x 3 = - 1 / 2 x 1 +4 1 / 2
Подставим их в целевую функцию:
F(X) = - x 1 - 2(- 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4) + 2(- 1 / 2 x 1 +4 1 / 2)
или

Система неравенств:
- 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4 ≥ 0
- 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4 ≥ 0
- 1 / 2 x 1 +4 1 / 2 ≥ 0
Приводим систему неравенств к следующему виду:
3 / 4 x 1 - 1 1 / 2 x 5 ≤ -14 3 / 4
1 1 / 4 x 1 + 1 / 2 x 5 ≤ 9 3 / 4
1 / 2 x 1 ≤ 4 1 / 2
F(X) = 1 / 2 x 1 + x 5 -10 1 / 2 → max
Упростим систему.
3 / 4 x 1 - 1 1 / 2 x 2 ≤ -14 3 / 4
1 1 / 4 x 1 + 1 / 2 x 2 ≤ 9 3 / 4
1 / 2 x 1 ≤ 4 1 / 2
F(X) = 1 / 2 x 1 + x 2 -10 1 / 2 → max

Пример №2 . Найдите сначала графическим методом, а затем симплекс-методом решение задачи
F(X) = x 1 + x 2 - x 3 + x 5 +15 → max (min) при ограничениях:
-3x 1 + x 2 + x 3 =3
4x 1 + 2x 2 - x 4 =12
2x 1 - x 2 + x 5 =2
x 1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0, x 5 ≥ 0