Разработка модели и решение задачи линейного программирования. 3
Содержание
Введение
При выполнении любых действий и при принятии решений в различных областях деятельности основополагающим желанием является получение наилучшего результата. Смысл действий и принятие решений определяются заинтересованностью в этих действиях и решениях в соответствии с имеющимися возможностями. Заинтересованность может выражаться в получении максимальной прибыли, минимальной себестоимости при заданной производительности, максимальной производительности при заданных затратах.
Современная экономическая наука существенно опирается на математическое моделирование экономических процессов и пронизана различным математическим аппаратом, а применяющийся в ней математический язык позволяет более определенно и однозначно формулировать экономические факты и законы. Формализация основных особенностей функционирования экономических объектов позволяет оценить возможные последствия воздействия на них и использовать такие оценки в управлении.
Для решения задачи оптимального управления необходимо иметь в той или иной форме математическое описание оптимизируемого объекта и метод определения оптимальных управлений (решений). Для решения задачи оптимального управления объектами используется метод математического моделирования.
Исследование экономических явлений математическими методами, в частности в финансово-экономической сфере и бизнесе, помогает лицу, принимающему решение, произвести критический анализ ситуации и в результате более обоснованно и последовательно проводить определенную политику или стратегию поведения при решении сложных, комплексных проблем.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-этап – нахождение
- с помощью дополнительных неотрицательных переменных переходим к равенствам (каноническая форма задачи);
- все переменные разбиваются на две группы: основные и неосновные, при этом определитель матрицы, составленный из коэффициентов при основных переменных должен быть отличным от 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
a1,1x1+a1,2x2+...a1,nxn+xn+1=b
a2,1x1+a2,2x2+...a2,nxn+xn+2=b
..............................
am,1x1+am,2x2+...am,nxn+xn+m=b
В случае, если в исходной задаче необходимо найти минимум − знаки коэффициентов целевой функции 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.
Если в столбце свободных
членов имеются отрицательные
элементы, то выбираем среди них
максимальный по модулю − он
задает ведущую строку k. В этой
строке так же находим максимал
Если среди свободных членов есть отрицательные элементы , а в соответствующей строке нет, то условия задачи несовместны и решений у нее нет.
Если после перерасчета в столбце свободных членов остались отрицательные элементы, то переходим к первому шагу, если таких нет, то ко второму.
4. Шаг 2. Проверка на неразрешимость
На предыдущем этапе найдено допустимое решение. Проверим его на оптимальность. Если среди элементов симплексной таблицы, находившихся в строке F (не беря в расчет элемент b0 - текущее значение целевой функции) нет отрицательных, то найдено оптимальное решение.
Если в строке F есть отрицательные элементы, то решение требует улучшения. Выбираем среди отрицательных элементов строки F максимальный по модулю (исключая значение функции b0)
l − столбец, в котором находится этот элемент, будет ведущим. Для того, что бы найти ведущую строку, находим отношение соответствующего свободного члена и элемента из ведущего столбца, при условии, что они неотрицательны.
k − строка, для которой это отношение минимально − ведущая. Элемент ak,l − ведущий (разрешающий). Переменная, соответствующая ведущей строке (xk) исключается из базиса, переменная соответствующая ведущему столбцу (xl) включается в базис. Пересчитываем симплекс − таблицу по формулам . Если в новой таблице после перерасчета в строке F остались отрицательные элементы, то переходим к шагу 2.
Если невозможно найти ведущую строку, так как нет положительных элементов в ведущем столбце, то функция в области допустимых решений задачи не ограничена − алгоритм завершает работу.
Если в строке F и в столбце свободных членов все элементы положи-тельные, то найдено оптимальное решение.3
Правила преобразования симплекс-таблицы:
При составлении новой симплекс-таблицы в ней происходят следующие изменения (1):
• вместо базисной переменной xk записываем xl;
- вместо небазисной пе-ременной xl записываем xk;
• ведущий элемент заменяется на обратную величину ak,l'= 1/ak,l ;
• все элементы ведущего столбца (кроме ak,l) умножаются на −1/ak,l ;
- все элементы ведущей строки (кроме ak,l) умножаются на 1/ak,l ;
- оставшиеся элементы симплекс-таблицы преобразуются по формуле
Процесс применения симплексного метода предполагает реализацию трех его основных элементов:
1) способ определения какого-либо первоначального допустимого
базисного решения задачи;
2) правило перехода к лучшему (точнее, не худшему) решению;
3) критерий проверки оптимальности найденного решения.
Геометрический (графический) метод
Графический метод решения задачи линейного программирования основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трёхмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трёх изобразить графически вообще невозможно.(Рис.1.)
Рис. 1.1. Система ограничений на плоскости
Рассмотрим задачу линейного программирования в стандартной форме с двумя переменными (n = 2). К такой форме может быть сведена и каноническая задача (с ограничениями в виде уравнений), когда число переменных n больше числа уравнений m на 2, т. е. n – m = 2.
Пусть геометрическим изображением системы ограничений является многоугольник ABCDE (рис.1.1). Необходимо среди точек этого многоугольника найти такую точку, в которой линейная функция F=c1x1+c2x2 принимает максимальное (или минимальное) значение.
Рассмотрим так называемую линию уровня линейной функции F, т. е. линию вдоль которой эта функция принимает одно и тоже значение a, т.е. F = a, или
линии уровня широко используются, например, на картах прогноза погоды, где извилистые линии – так называемые изотермы есть ничто иное, как линии уровня температуры Т = с. Ещё более простым примером линий уровня являются параллели на географической карте. Это линии уровня широты.
Предположим надо найти самую северную точку какой-либо области, например страны или материка. Это будет точка, имеющая наибольшую широту, т. е. точка через которую проходит параллель (линия уровня) с самой большой широтой (уровнем).
Именно так и надо поступать при геометрическом решении задач линейного программирования . на многоугольнике решений следует найти точку, через которую проходит линия уровня функции F с наибольшим (если линейная функция максимизируется) или наименьшим (если она минимизируется) уровнем.
Уравнение линии функции (1) есть уравнение прямой линии. При различных уровнях а.
Линии уровня параллельны, так как их угловые коэффициенты определяются только соотношением между коэффициентами c1 и c2 и следовательно, равны. Таким образом, линии уровня функции F – это своеобразные “параллели”, расположенные обычно под углом к осям координат.
Важное свойство линии уровня линейной функции состоит в том, что при параллельном смещении линии в одну сторону уровень только возрастает, а при смещении линии в другую сторону – только убывает.
Пусть имеются три линии уровня :
F=c1x1 + c2x2 = а1 (I)
F=c1x1 + c2x2 = а2 (II)
F=c1x1 + c2x2 = а3 (III)
Причём линия II заключена между линиями I и III. Тогда а1 < а2 < а3 и а1 > а2 > а3.
В самом деле, на штриховой линии (перпендикулярной к линиям уровня на рис. 1.2) уровень является линейной функцией, а значит, при смещении в одном направлении возрастает, а в другом – убывает.
Для определения направления возрастания рекомендуется изобразить две линии уровня и определить, на какой них уровень больше. Например, одну из линий взять проходящей через начало координат (если линия функция имеет вид F=c1x1 + c2x2, т. е. без свободного члена, то это соответствует нулевому уровню). Другую линию можно провести произвольно, так, например, чтобы она проходила через множество решений системы ограничений. Далее найдём точку, в которой функция принимает максимальное значение, подобно тому как на карте находится самая северная или самая южная точка (на рис. 1.1 – это точка С или А).
2. Разработка модели и решение
задачи линейного
2.1. Вербальная постановка конкретной решаемой задачи «производить или покупать»
Фабрика ООО «Мельник» специализируется на выпуске двух сортов теста: бисквитное и песочное. Для изготовления теста используются такие ингредиенты как яйца и сахар, так же затрачивается и ресурсы труда. Для изготовления бисквитного теста требуется 5 штук яиц и 0,3 килограмма сахара, для изготовления затрачивается 15 минут. А для изготовления песочного теста потребуется 2 яйца, 0,25 килограмма сахара и 30 минут затраченного времени. Стоимость 1 кг бисквитного теста 30 руб., а песочного 20 руб. Общий запас яиц равен 1000 шт., 75 кг сахара и 125 часов трудовых ресурсов.
2.2.
Разработка экономико-
1. Переменные задачи.
В задаче требуется установить, сколько продукции каждого вида надо производить, поэтому искомыми величинами, а значит, и переменными задачи являются суточные объемы производства каждого вида продукции:
х1 – суточный объем производства бисквитного теста, (кг);
х2 – суточный объем производства песочного теста, (кг).
2. Целевая функция.
В условии задачи сформулирована цель – добиться максимального дохода от реализации продукции, т.е. критерием эффективности служит параметр суточного дохода, который должен стремиться к максимуму. Чтобы рассчитать величину суточного дохода от продажи продукции обоих видов, необходимо знать объемы производства, т.е. x1 и х2 кг продукции в сутки, а также цены на продукцию бисквитного и песочного теста – согласно условию 30 и 20 руб. за 1 кг продукции соответственно. Таким образом, доход от продажи суточного объема производства продукции бисквитного теста равен 30х1 руб. в сутки, а от продажи песочного теста – 20х2 тыс. руб. в сутки. Поэтому запишем целевую функцию в виде суммы дохода от продажи продукции бисквитного и песочного теста.
3. Ограничения.
Возможные объемы производства продукции х1 и х2 ограничиваются следующими условиями:
– количество яиц, сахара и трудовых ресурсов, израсходованных в течение суток на производство теста обоих видов, не может превышать запаса этих ингредиентов на складе;
– объем производства продукции не может быть выражен отрицательными значениями.
Запишем эти ограничения в математической форме.
Ограничение по расходу яиц имеет вид:
Левая часть ограничения – это расчет расхода яиц на производство теста обоих видов. Расход яиц на производство 1 кг бисквитного теста – 5 шт.; на производство 1 кг песочного теста – 2 шт. Тогда на производство х1 кг бисквитного теста и х2 кг песочного теста потребуется (5х1 + 2x2) шт. яиц. Правая часть ограничения – это величина запаса яиц на складе – 1000 шт.
Аналогична запись ограничения по расходу сахара:
Так же ограничение по трудовым ресурсам имеет вид:
Неотрицательность объемов производства задается как
Таким образом, математическая модель задачи имеет вид:
Экономико-математическая модель задачи состоит в том, чтобы найти такой план производства продукции , удовлетворяющий системе ограничений, при котором целевая функция принимает максимальное значение.
2.3. Решение поставленной задачи
Приведем задачу к каноническому виду. Для этого в ограничения задачи введем дополнительные переменные х3, х4, х5 и перепишем условие задачи в виде уравнений:
В качестве базисных переменных возьмем х3, х4, х5, тогда небазисные – х1, х2. Полагаем х1 = х2 = 0, тогда х3 =1000, х4=75, х5 =125.
I этап.
х3, х4, х5 – основные переменные;
х1, х2 - неосновные
или
Допустимое решение. Все переменные неотрицательные.
II этап
1.
а)
б) решение допустимо:
в) - решение неоптимальное, т.к. х1 и х2 положительные, значит можно увеличить
г) т.к. при х1 коэффициент больше, переводим ее в основные переменные, х3 переводим в неосновные
х1 max возможное =
таким образом, х1 = 200, х3= 0
Разрешающим будет 1-е уравнение, х3 = 0, х1 переводим в основные переменные
д) Новый состав переменных:
х1, х4, х5 – основные переменные;
х3, х2 – неосновные
2.
а)
б)
в)
Решение не оптимально. Его можно увеличить путем перевода х2 в основные переменные.
г) х2 переводим в основные переменные, х4 выводим в неосновные.
д) базисные переменные: х1 , х2 , х5
неосновные переменные: х3 , х4
3.
а)
б)
в) =
= =6922 - 2,32х3
Так как все оценки свободных переменных положительные, найденное решение является оптимальным:
Максимальная прибыль составит 6922 рубля, при этом необходимо произвести 153,8 кг бисквитного теста и 115,4 кг песочного теста. В оптимальном плане ресурсы яиц и сахара равны нулю (х3=х4=0), так как они используются полностью. А резерв трудовых ресурсов х5 = 28,8, что свидетельствует о излишках.
