Общая задача оптимизации

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего профессионального образования

Тверской государственный технический университет

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

Примеры решения задач в Excel.

Тверь

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

Обсуждено и рекомендовано на заседании кафедры ИПМ (протокол № от марта 2008 г.)

Составители: Е.Е. Фомина, И.Л. Кислова

© Тверской государственный технический университет, 2008

СОДЕРЖАНИЕ

Введение. 4

1 Методические указания по решению ЗЛП в среде Exсel 7

1.1 Максимизация прибыли предприятия. 7

1.2 Максимизация годового дохода. 17

1.3 Специальные задачи линейного программирования. 25

1.3.1 Задача целочисленного программирования. 25

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

1.3.2.1 Закрытая транспортная задача. 27

1.3.2.2 Открытая транспортная задача. 34

1.3.3 Задача о назначениях. 35

1.3.4 Двойственность в задачах линейного программирования...36

2. Вопросы для самоконтроля. 47

3. Варианты заданий. 48

4. Требования к оформлению контрольной работы.. 59

Использованная литература. 60

Введение

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

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

Общая задача оптимизации

В общем виде математическая постановка задачи математического программирования состоит в определении наибольшего или наименьшего значения целевой функции f (x_1, x _{2, ….} x _n) при условиях g_i (x₁ , x_{2 ,…,} x _n ) ≤ b_i ; ( i = 1,2, … m), где f и g_i - заданные функции, а b_i - некоторые действительные числа.

Задачи математического программирования делятся на задачи линейного и нелинейного программирования. Если все функции f и g_i - линейные, то соответствующая задачи является задачей линейного программирования (ЗЛП). Если хотя бы одна из указанные функций – нелинейная, то соответствующая задача является задачей нелинейного программирования.

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

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

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

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

В общем виде задачи линейного программирования (ЗЛП) ставится следующим образом:

Необходимо найти вектор , максимизирующий линейную форму

(1)

и удовлетворяющий условиям

(2)

, (3)

где , , - действительные числа.

Линейная функция f(X) называется целевой функцией задачи. Условия (2) называются функциональными, а (3) – прямыми ограничениями задачи.

Вектор X=(x_{1 ,} x_{2, …} x_n ), компоненты которого удовлетворяют функциональным и прямым ограничениям задачи, будем называть планом, или допустимым решением ЗЛП.

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

Допустимое решение, максимизирующее целевую функцию f (X ), называется оптимальным планом задачи.

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

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

Для решения ЗЛП существует универсальный метод – метод последовательного улучшения плана, или симплекс-метод, который состоит из двух вычислительных процедур: симплекс-метода с естественным базисом и симплекс-метода с искусственным базисом (М-метод).

Выбор конкретной вычислительной процедуры осуществляется после приведения исходной задачи к каноническому виду задачи линейного программирования (КЗЛП):

В теории линейного программирования показано, что оптимальное решение ЗЛП связано с угловыми (крайними) точками многогранника решений, которым отвечают опорные планы (неотрицательные базисные решения системы уравнений КЗЛП). Каждый из опорных планов определяется системой m линейно независимых векторов, содержащихся в данной системе из n векторов А₁,А₂, …..А_n. Верхняя граница количества опорных планов, содержащихся в данной задаче, определяется числом сочетаний C_m.

Решение ЗЛП симплекс-методом «вручную» подробно рассмотрено в [1], [5] и др.

ЗЛП широко применяются в экономике и управлении. На практике хорошо зарекомендовали себя следующие модели, относящиеся к оптимизационным:

· определения оптимальной производственной программы;

· оптимального смешивания компонентов;

· оптимального раскроя;

· оптимального размещения предприятий некоторой отрасли на определенной территории;

· формирования оптимального портфеля ценных бумаг;

· транспортной задачи и др.

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

Огромный вклад в развитие и применение ЗЛП внес наш соотечественник Леонид Витальевич Канторович. За что в 1975 г. Был удостоен Нобелевской премии по экономике.