- •Федеральное агенство по образованию
- •Введение
- •Общая задача оптимизации
- •1 Методические указания по решению злп в среде Exсel
- •1.1 Максимизация прибыли предприятия Постановка задачи
- •Решение
- •I этап: Составление математической модели
- •II этап: Решение задачи на эвм в среде ms Excel
- •III этап: Анализ решения задачи
- •1.2 Максимизация годового дохода Постановка задачи
- •Решение
- •I этап: Составление математической модели
- •II этап: Решение задачи на эвм в среде ms Excel
- •1.3 Специальные задачи линейного программирования
- •1.3.1 Задача целочисленного программирования
- •1.3.2 Транспортная задача Общая постановка транспортной задачи
- •Математическая модель транспортной задачи
- •1.3.2.1 Закрытая транспортная задача Минимизация стоимости перевозок кирпича
- •Решение
- •I этап: Составление математической модели
- •II этап: Решение задачи на эвм средствами пакета Excel
- •1.3.2.2 Открытая транспортная задача Постановка задачи
- •1.3.3 Задача о назначениях Постановка задачи
- •Решение
- •I этап: Составление математической модели
- •1.3.4 Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений.
- •Задача оптимального использования ресурсов.
- •Решение.
- •I этап: Составление математической модели прямой злп
- •II этап: Решение задачи на эвм в среде ms Excel
- •Ш этап: Составление математической модели двойственной злп
- •Анализ влияния изменения правых частей ограничений на значения целевой функции (чувствительность решения к изменению запасов сырья).
- •2. Вопросы для самоконтроля:
- •3. Варианты заданий для контрольной работы по дисциплине
- •4. Требования к оформлению контрольной работы
Федеральное агенство по образованию
Государственное образовательное учреждение высшего профессионального образования
Тверской государственный технический университет
Линейное программирование.
Примеры решения задач в Excel.
Тверь
2008
Методическое пособие предназначено для студентов специальности «Экономика и управление на предприятии (машиностроение)», изучающих курсы «Экономико-математические методы в управлении» и «Экономико-математические модели объектов отрасли». Пособие можно также рекомендовать студентам экономических специальностей, изучающих экономико-математические методы и модели.
Обсуждено и рекомендовано на заседании кафедры ИПМ (протокол № от марта 2008 г.)
Составители: Е.Е. Фомина, И.Л. Кислова
|
© Тверской государственный технический университет, 2008 |
СОДЕРЖАНИЕ
Введение
В экономике оптимизационные задачи возникают в связи с многочисленностью возможных вариантов функционирования конкретного экономического объекта, когда возникает ситуация выбора варианта, наилучшего по некоторому правилу, критерию, характеризуемому соответствующей целевой функцией (например, иметь минимум затрат, максимум продукции).
Оптимизационные модели отражают в математической форме смысл экономической задачи. Отличительной особенностью этих моделей является наличие условия нахождения оптимального решения (критерия оптимальности), которое записывается в виде функционала. Эти модели при определенных исходных данных задачи позволяют получить множество решений, удовлетворяющих условиям задачи, и обеспечивают выбор оптимального решения, отвечающего критерию оптимальности.
Общая задача оптимизации
В общем виде математическая постановка задачи математического программирования состоит в определении наибольшего или наименьшего значения целевой функции f (x1, x 2, …. x n) при условиях gi (x1 , x2 ,…, x n ) ≤ bi ; ( i = 1,2, … m), где f и gi - заданные функции, а bi - некоторые действительные числа.
Задачи математического программирования делятся на задачи линейного и нелинейного программирования. Если все функции f и gi - линейные, то соответствующая задачи является задачей линейного программирования (ЗЛП). Если хотя бы одна из указанные функций – нелинейная, то соответствующая задача является задачей нелинейного программирования.
Линейное программирование – область математики, разрабатывающая теорию и численные методы решения задач нахождения экстремума (максимума или минимума) линейной функции многих переменных при наличии линейных ограничений, т.е. линейных равенств или неравенств, связывающих эти переменные. К задачам линейного программирования сводится широкий круг вопросов планирования экономических процессов, где ставится задача поиска наилучшего (оптимального) решения.
Cреди задач нелинейного программирования наиболее глубоко изучены задачи выпуклого программирования. Это задачи, в результате решения которых определяется минимум выпуклой (или максимум вогнутой) функции, заданной на выпуклом замкнутом множестве.
В свою очередь, среди задач выпуклого программирования более подробно исследованы задачи квадратичного программирования. В результате решения таких задач требуется в общем случае найти максимум (или минимум) квадратичной функции при условии, что ее переменные удовлетворяют некоторой системе линейных неравенств или линейных уравнений либо некоторой системе, содержащей как линейные неравенства, так и линейные уравнения.
Отдельными классами задач математического программирования являются задачи целочисленного, параметрического и дробно-линейного программирования.
В общем виде задачи линейного программирования (ЗЛП) ставится следующим образом:
Необходимо найти вектор , максимизирующий линейную форму
(1)
и удовлетворяющий условиям
(2)
, (3)
где ,,- действительные числа.
Линейная функция f(X) называется целевой функцией задачи. Условия (2) называются функциональными, а (3) – прямыми ограничениями задачи.
Вектор X=(x1 , x2, … xn ), компоненты которого удовлетворяют функциональным и прямым ограничениям задачи, будем называть планом, или допустимым решением ЗЛП.
Все допустимые решения образуют область определения задачи линейного программирования, или область допустимых решений.
Допустимое решение, максимизирующее целевую функцию f (X ), называется оптимальным планом задачи.
Будем считать, что ЗЛП записана в канонической форме, если ее целевая функция максимизируется, ограничения имеют вид равенств с неотрицательной правой частью и все переменные неотрицательные.
На практике хорошо зарекомендовали себя следующие модели, относящиеся к оптимизационным: определения оптимальной производственной программы; оптимального смешивания компонентов; оптимального раскроя; оптимального размещения предприятий некоторой отрасли на определенной территории; формирования оптимального портфеля ценных бумаг; транспортной задачи.
Для решения ЗЛП существует универсальный метод – метод последовательного улучшения плана, или симплекс-метод, который состоит из двух вычислительных процедур: симплекс-метода с естественным базисом и симплекс-метода с искусственным базисом (М-метод).
Выбор конкретной вычислительной процедуры осуществляется после приведения исходной задачи к каноническому виду задачи линейного программирования (КЗЛП):
В теории линейного программирования показано, что оптимальное решение ЗЛП связано с угловыми (крайними) точками многогранника решений, которым отвечают опорные планы (неотрицательные базисные решения системы уравнений КЗЛП). Каждый из опорных планов определяется системой m линейно независимых векторов, содержащихся в данной системе из n векторов А1,А2, …..Аn. Верхняя граница количества опорных планов, содержащихся в данной задаче, определяется числом сочетаний Cm.
Решение ЗЛП симплекс-методом «вручную» подробно рассмотрено в [1], [5] и др.
ЗЛП широко применяются в экономике и управлении. На практике хорошо зарекомендовали себя следующие модели, относящиеся к оптимизационным:
определения оптимальной производственной программы;
оптимального смешивания компонентов;
оптимального раскроя;
оптимального размещения предприятий некоторой отрасли на определенной территории;
формирования оптимального портфеля ценных бумаг;
транспортной задачи и др.
Менеджер, как лицо ответственное за принятие решений, должен уметь использовать известные модели и понимать как полученный результат использовать для принятия разумного решения.
Огромный вклад в развитие и применение ЗЛП внес наш соотечественник Леонид Витальевич Канторович. За что в 1975 г. Был удостоен Нобелевской премии по экономике.