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

Содержание

 

 

 

 

Введение

 

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

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

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

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

Целью данной курсовой работы является разработка модели и решение задачи линейного программирования (на примере задачи «производить или покупать».

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

• теоретические аспекты линейного программирования;
• вербальная постановка конкретной решаемой задачи;
• разработка экономико-математической модели решаемой задачи;
• решение поставленной задачи;
• решение поставленной задачи с помощью средств EXСEL;
• интерпретация результатов расчетов и выработка управленческого решения

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

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

 

1. Теоретические аспекты линейного  программирования

 

1.1. Задачи линейного программирования  на основании общей математической  формулировки

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

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

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

Формулировка задачи линейного программирования

Естественной формой задачи линейного программирования является задача об определении максимума линейной целевой функции, обычно называемой линейной формой. Имеются какие-то переменные х = (х1 , х2 , … хn ) и функция этих переменных:

 

 

которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции f(x) при условии,

при (i = 1, 2, 3, . . . , m).

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

Такую задачу называют «основной» или «стандартной» в линейном программировании.

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

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

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

1) целевая функция исходной задачи  формулируется на максимум, а  целевая функция двойственной  задачи - на минимум, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид £, в задаче на минимум - вид ³;

2) матрица А, составленная из  коэффициентов при неизвестных  в системе ограничений исходной  задачи и аналогичная матрица  Ат в двойственной задаче получаются друг из друга транспонированием;

3) число переменных в двойственной  задаче равно числу функциональных  ограничений исходной задачи, а  число ограничений в системе  двойственной задачи - числу переменных в исходной задаче;

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

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

Решая ЗЛП симплексным методом, одновременно решается двойственная ЗЛП. Переменные двойственной задачи называют объективно обусловленными оценками.

 

1.2. Методы решения задачи линейного  программирования

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

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

Алгоритм решения задачи симплекс-методом включает в себя однократно выполняемый 0-этап и повторяемый конечное число шагов 1-этап.

0-этап – нахождение первоначально  допустимого базисного решения:

1. с помощью дополнительных неотрицательных переменных переходим к равенствам (каноническая форма задачи);
2. все переменные разбиваются на две группы: основные и неосновные, при этом определитель матрицы, составленный из коэффициентов при основных переменных должен быть отличным от 0. (табл .1.1)

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

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

Пример исходной симплекс-таблицы для задачи ЛП:

Таблица 1

Симплекс-таблица

	x1	x2	...	xn-1	xn	b
F	-a0,1	-a0,2	...	-a0,n-1	-a0,n	-b0
xn+1	a1,1	a1,2	...	a1,n-1	a1,n	b1
xn+2	a2,1	a2,2	...	a2,n-1	a2,n	b2
...	...	...	...	...	...	...
xn+m	am,1	am,2	...	am,n-1	am,n	bm

 

Нам известно, что x1, x2, xn − исходные переменные, xn+1, xn+2, xn+m − дополнительные переменные. Все дополнительные переменные мы приняли как базисные, а исходные переменные как небазисные (дополнительные записаны в первый столбец симплекс-таблицы, а исходные в первую строку).

Алгоритм применения симплекс-метода

1. Подготовительный этап

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

F=a0,1x1+a0,2x2+...a0,nxn +b0 → max

a1,1x1+a1,2x2+...a1,nxn+xn+1=b1

a2,1x1+a2,2x2+...a2,nxn+xn+2=b2

.......................................

am,1x1+am,2x2+...am,nxn+xn+m=bm

В случае, если в исходной задаче необходимо найти минимум − знаки коэффициентов целевой функции F меняются на противоположные a0,n= −a0,n. Знаки коэффициентов ограничивающих условий со знаком "≥" так же меняются на противоположные. В случае, если условие содержит знак "≤" − коэффициенты запишутся без изменений. 

2. 0 этап

Составляем симплексную таблицу, соответствующую исходной задаче:

Таблица 2

Симплекс-таблица

	x1	x2	...	xn-1	xn	b
F	-a0,1	-a0,2	...	-a0,n-1	-a0,n	-b0
xn+1	a1,1	a1,2	...	a1,n-1	a1,n	b1
xn+2	a2,1	a2,2	…	a2,n-1	a2,n	b2
…	…	…	…	…	…	…
xn+m	am,1	am,2	…	am,n-1	am,n	bm

 

3. Шаг 1. Проверка на оптимальность

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