КУРСОВАЯРАБОТА
по курсу:Экономико-математические методы и модели
на тему: «Применениелинейного программирования для решения экономических задач (оптимизацияприбыли)»
Тюмень, 2007
СОДЕРЖАНИЕ
Введение 3
1.Теоретико-методическое описание метода линейного программирования 5
2.Области применения и ограничения использования линейного программирования длярешения экономических задач 16
3.Оптимизация прибыли с применением метода ЛП 23
3.1 Постановка задачи иформирование оптимизационной модели 23
3.2 Расчет и анализ результатовоптимизации прибыли 24
Заключение 27
Списоклитературы 29
Введение
Развитие современного общества характеризуетсяповышением технического уровня, усложнением организационной структурыпроизводства, углублением общественного разделения труда, предъявлением высокихтребований к методам планирования и хозяйственного руководства. В этих условияхтолько научный подход к руководству экономической жизнью общества позволитобеспечить высокие темпы развития народного хозяйства.
Одним из необходимых условий дальнейшего развитияэкономической науки является применение точных методов количественного анализа,широкое использование математики. В настоящее время новейшие достиженияматематики и современной вычислительной техники находят все более широкоеприменение в экономических исследованиях и планировании. Этому способствуетразвитие таких разделов математики, как математическое программирование, теорияигр, теория массового обслуживания, а также бурное развитие быстродействующейэлектронно-вычислительной техники. Уже накоплен достаточный опыт постановки ирешения экономических задач с помощью математических методов. Особенно успешноразвиваются методы оптимального планирования, которые и составляют сущностьматематического программирования.
Одной из основных становится задача создания единойсистемы оптимального планирования и управления народным хозяйством на базе широкогоприменения математических методов и электронно-вычислительной техники вэкономике.
Основной целью написания курсовой работы являетсявсесторонний анализ применения линейного программирования для решенияэкономических задач. Задачами курсовой работы являются:
1. Теоретико-методическое описание метода линейногопрограммирования;
2. Выявление области применения и ограниченияиспользования линейного программирования для решения экономических задач;
3. Оптимизация прибыли с применением методалинейного программирования;
4. Постановка задачи и формирование оптимизационноймодели;
5. Расчет и анализ результатов оптимизации прибыли.
1. Теоретико-методическоеописание метода линейного программирования
В настоящее времялинейное программирование является одним из наиболее употребительных аппаратовматематической теории оптимального принятия решений. Для решения задачлинейного программирования разработано сложное программное обеспечение, дающеевозможность эффективно и надежно решать практические задачи больших объемов.Владение аппаратом линейного программирования необходимо каждому специалисту вобласти прикладной математики.
Линейное программирование– это наука о методах исследования и отыскания наибольших и наименьших значенийлинейной функции, на неизвестные которой наложены линейные ограничения. Такимобразом, задачи линейного программирования относятся к задачам на условныйэкстремум функции. По типу решаемых задач методы разделяются на универсальные испециальные. С помощью универсальных методов могут решаться любые задачи линейногопрограммирования (ЗЛП). Специальные методы учитывают особенности модели задачи,ее целевой функции и системы ограничений.
Особенностью задачлинейного программирования является то, что экстремума целевая функциядостигает на границе области допустимых решений. Классические же методыдифференциального исчисления связаны с нахождением экстремумов функции вовнутренней точке области допустимых значений. Отсюда — необходимость разработкиновых методов. [3, c.7]
Линейное программированиепредставляет собой наиболее часто используемый метод оптимизации. К числу задачлинейного программирования можно отнести задачи:
1. рационального использования сырья иматериалов;
2. задачи оптимального раскроя;
3. оптимизации производственнойпрограммы предприятий;
4. оптимального размещения иконцентрации производства;
5. составления оптимального планаперевозок, работы транспорта (транспортные задачи);
6. управления производственнымизапасами;
7. и многие другие, принадлежащие сфереоптимального планирования.
Линейное программированиеявляется одной из основных частей того раздела современной математики, которыйполучил название математического программирования. В общей постановке, задачиэтого раздела выглядят следующим образом.
Требуется найти такиенеотрицательные />, которыеобеспечивают максимум или минимум целевой функции (формула 1.1), которыеудовлетворяют системе ограничений (формула 1.2) и не противоречат условиямнеотрицательности: />.
/> (1.1)
/>
/> (1.2)
… … … … … … … … … …
/>
В зависимости от видафункции /> различают разделыматематического программирования: квадратичное программирование, выпуклое программирование,целочисленное программирование и т.д. Линейное программирование характеризуетсятем, что функция /> являетсялинейной функцией переменных />. [1 c.11-12]
Формы задач линейногопрограммирования:
1. стандартная;
1.1 первая стандартнаяформа (формула 1.3);
1.2 вторая стандартнаяформа (формула 1.4);
2. каноническая (формула1.5).
/>
/>
/> (1.3)
… … … … … … … … … …
/>
/>.
/>
/>
/> (1.4)
… … … … … … … … … …
/>
/>.
/>
/>
/> (1.5)
… … … … … … … … …
/>
/>.
Задачу на минимум (формула1.6) можно решать как задачу на максимум. Достаточно знаки целевой функции поменятьна противоположные (формула 1.7). В результате необходимо знак целевой функциипоменять на противоположный.
/> (1.6)
/> (1.7)
Аналогично можно сменитьзнак неравенства меньше или равно (формула 1.8) на больше или равно (формула1.9).
/> (1.8)
/> (1.9)
Целевая функция задачилинейного программирования достигает своего экстремума (минимума или максимума)в вершине допустимой области. Если целевая функция достигает экстремальногозначения более чем на одной вершине, то она достигает того же значения в любойточке, являющейся выпуклой комбинацией этих вершин (альтернативный оптимум).
Эта теорема имеетважнейшие значение, так как она указывает путь решения задачи линейногопрограммирования. Совсем не надо перебирать все точки допустимой области.Достаточно перебрать вершины допустимой области, а ведь их конечное число.Кроме того, не нужно перебирать все вершины, можно этот перебор существенносократить.
Любой набор чисел />, удовлетворяющийограничениям задачи, называют планом, а множество всех планов допустимой областью.Тот план, который доставляет экстремум (минимум или максимум) целевой функции,называют оптимальным планом или просто решением задачи линейногопрограммирования. [3 c.7-8]
Задачи линейногопрограммирования решаются несколькими методами:
1. графический метод;
2. симплексный метод;
3. двойственность в ЛП;
4.двойственныйсимплексный метод.
Задачи линейногопрограммирования с двумя переменными всегда можно решить графически. Однако ужев трехмерном пространстве такое решение усложняется, а в пространствах,размерность которых больше трех, графическое решение невозможно.
Графический методдовольно прост и нагляден. Он основан на геометрическом представлениидопустимых решений задачи. Каждое из неравенств задачи ЛП определяет накоординатной плоскости /> некоторую полуплоскость, асистема неравенств в целом – пересечение соответствующих плоскостей. Множествоточек пересечения данных полуплоскостей называется областью допустимых решений(ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующимсвойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВпринадлежит ей. ОДР графически может быть представлен выпуклым многоугольником,неограниченным выпуклой многоугольной областью, отрезком, лучом и т.д. В случаенесовместности системы ограничений задачи ОДР является пустым множеством.
При поиске оптимальногорешения задач линейного программирования возможны следующие ситуации: существуетединственное решение задачи, существует бесконечное множество решений (альтернативныйоптимум); ЦФ не ограничена; область допустимых решений– единственная точка;задача не имеет решений. [3 c.55-57]
Любая задача линейногопрограммирования, независимо от вида записи, может быть приведена к стандартнойи канонической форме и решена симплексным методом, который в определенномсмысле является универсальным методом ЛП. Алгоритм симплекс-метода носититерационный характер.
Симплекс-метод позволяетпереходить от одного допустимого базисного решения к другому, причем так, чтозначения целевой функции непрерывно возрастают. Алгоритмы симплекс-методапозволяют также установить, является ли задача ЛП разрешимой.
Переход от одного базисак другому позволяет находить решения почти всех задач ЛП. Определив все крайниеточки, можно вычислить значения целевой функции и найти оптимальное решение.Однако для больших значений m и n это практически невозможно. [1 c.15]
Алгоритм решения задачиЛП табличным симплексом-методом состоит из следующих этапов:
1. рассчитывают изаполняют начальную симплекс-таблицу с допустимым единичным базисом, включаяиндексную строку.
2. находят разрешающийстолбец;
3. находят разрешающуюстроку;
4. рассчитывают методомЖордано-Гаусса все параметры матрицы;
5. анализируют полученныеданные в индексной строке.
Таблицысимплекс-метода необходимо строить до тех пор, пока не будет полученоптимальный план. План будет считаться оптимальным, если в последней индекснойстроке симплекс-таблицы будут только нули и положительные числа. [1 c.20-22]
Припостроении симплексного метода предполагалось, что все опорные планыневырожденные, что обеспечивало получение оптимального плана за конечноеколичество шагов. В случае вырожденного плана вычисления производят аналогично,но в этом случае возможен возврат к старому базису, что приводи к такназываемому зацикливанию./>
Метод искусственногобазиса применяется приналичии в ограничении знаков “равно”, “больше либо равно”, “меньше либо равно” и являетсямодификацией табличного метода. Решение системы производится путём вводаискусственных переменных со знаком, зависящим от типа оптимума, т.е. дляисключения из базиса этих переменных последние вводятся в целевую функцию сбольшими отрицательными коэффициентами m, а в задачи минимизации — с положительными m. Таким образом, из исходной получается новая m — задача.
Если в оптимальномрешении m — задачи нет искусственных переменных,это решение есть оптимальное решение исходной задачи. Если же в оптимальномрешении m — задачи хоть одна из искусственныхпеременных будет отлична от нуля, то система ограничений исходной задачинесовместна и исходная задача неразрешима.
В основумодифицированного симплекс – метода положены такие особенности линейнойалгебры, которые позволяют в ходе решения задачи работать с частью матрицыограничений. Иногда метод называют методом обратной матрицы.
В процессе работыалгоритма происходит спонтанное обращение матрицы ограничений по частям, соответствующим текущимбазисным векторам. Указанная способность делает весьма привлекательной машиннуюреализацию вычислений вследствие экономии памяти под промежуточные переменные изначительного сокращения времени счёта. Хорош для ситуаций, когда числопеременных n значительно превышает число ограничений m.
В целом, метод отражаеттрадиционные черты общего подхода к решению задач линейного программирования,включающего в себя канонизацию условий задачи, расчёт симплекс-разностей,проверку условий оптимальности, принятие решений о коррекции базиса иисключение Жордана-Гаусса.
Особенности заключаются вналичии двух таблиц — основной и вспомогательной, порядке их заполнения инекоторой специфичности расчётных формул.
Каждой задаче линейногопрограммирования можно определенным образом сопоставить некоторую другую задачу,называемую двойственной или сопряженной по отношению к исходной или прямойзадаче. Сопоставляя формы записи прямой и двойственнойзадач, можно установить между ними следующие взаимосвязи:
1.если прямая задача является задачей максимизации, то двойственная будет задачейминимизации, и наоборот;
2.коэффициенты целевой функции прямой задачи становятся свободными членамиограничений двойственной задачи;
3.свободные члены ограничений прямой задачи становятся коэффициентами целевойфункции двойственной задачи;
4.матрица ограничений двойственной задачи получается путем транспортированияматрицы ограничений прямой задачи;
5.знаки неравенств в ограничениях изменяются на противоположные;
6.число ограничений прямой задачи равно числу переменных двойственной задачи, инаоборот.
Видыматематических моделей двойственных задач могут быть представлены в таблице(табл. 1.1).
Таблица1.1
Видыматематических моделей двойственных задачИсходная задача Двойственная задача Несимметричные задачи
/>
/>
/>
/> Симметричные задачи
/>
/>
/>
/>
Такимобразом, прежде чем записать двойственную задачу для данной исходной, системуограничений исходной задачи необходимо привести к соответствующему виду. [3,с.114-115]
Еслииз пары двойственных задач одна обладает оптимальным планом, то и другая имеетрешение, причем для экстремальных значений линейных функций выполняетсяопределенное соотношение (формула 1.10). Если линейная функция одной из задачне ограничена, то другая не имеет решения.
/> (1.10)
Если прямая (а значит, идвойственная) задача разрешима, то в каждой паре двойственных условий одноявляется свободным, а другое закрепленным. Любое из условий называетсясвободным, если оно выполняется как строгое неравенство хотябы для одногооптимального вектора. Условие называется закрепленным, если оно выполняется какравенство для всех оптимальных векторов.
Двойственнуюзадачу выгоднее решать, чем прямую, если в прямой задаче при малом количествепеременных имеется большое количество ограничений. [2, c 70-71]
Симплексный методпозволяет наряду с получением решения прямой задачи получать и решениедвойственной задачи. Этот результат и лежит в основе двойственного симплексногометода решения задачи. Суть метода состоит в таком последовательном перебореугловых точек допустимого множества Q0двойственной задачи, при которомзначение целевой функции возрастает, т. е. в применении симплексного метода крешению двойственной задачи. Будем предполагать, что задача невырождена, т. е.каждой угловой точке множества Q0соответствует квадратная невырожденная система уравненийразмерности m, матрицу которую и называют двойственным базисом прямойзадачи. Вместе с тем двойственный симплекс–метод можно применять при решениизадачи линейного программирования, свободные члены системы уравнений котороймогут быть любыми числами (при решении задачи симплексным методом эти числапредполагались неотрицательными).
Отыскание решения задачидвойственным симплекс-методом включает в себя следующие этапы:
1. Находят псевдопланзадачи.
2. Проверяют этотпсевдоплан на оптимальность. Если псевдоплан оптимален, то найдено решениезадачи. В противном случае либо устанавливают неразрешимость задачи, либо переходятк новому псевдоплану.
3. Выбирают разрешающуюстроку с помощью определения наибольшего по абсолютной величине отрицательногочисла столбца вектора Р0и разрешающий столбец с помощьюнахождения наименьшего по абсолютной величине отношения элементов (m+1)–истроки к соответствующим отрицательным элементам разрешающей строки.
4. Находят новыйпсевдоплан и повторяют все действия начиная со второго этапа.
Двойственный симплексныйметод называют также методом последовательного уточнения оценок, посколькуугловые точки задачи, возникающие при итерациях, можно рассматривать какприближенные значения точной оценки у*, т. е. как приближенные оценки влиянияусловий задачи на величину минимума целевой функции. [2, c.87-92]
Значительнаячасть экономических задач, относящихся к задачам линейного программирования,требует целочисленного решения. К ним относятся задачи, у которых переменныевеличины означают количество единиц неделимой продукции, например распределениепроизводственных заданий между предприятиями, раскрой материалов, загрузкаоборудования, распределение судов по линиям, самолетов по рейсам, а такжезадачи по производству неделимой продукции. Если единица составляет малую частьвсего объема производства, то оптимальное решение находят обычным симплекснымметодом, округляя его до целых единиц, исходя из смысла задачи. В противномслучае округление может привести к решению, далекому от оптимальногоцелочисленного решения.
Задачацелочисленного программирования формулируется так же, как и задача линейногопрограммирования, но включается дополнительное требование, состоящее в том, чтозначения переменных, составляющих оптимальное решение, должны быть целыминеотрицательными числами.
Методрешения таких задач, предложенный Гомори, основан на симплексном методе исостоит в следующем. Симплексным методом находится оптимальный план задачи безучета условия целочисленности. Если оптимальный план целочисленный, товычисления заканчивают; если же оптимальный план содержит хотя бы одну дробнуюкомпоненту Xi, то накладывают дополнительноеограничение, учитывающее целочисленность компонент плана, и вычислениясимплексным методом продолжают до тех пор, пока либо будет найден целочисленныйоптимальный план, либо доказано, что задача не имеет целочисленных оптимальныхпланов. [3 c.122-123]
Особенноширокое распространение линейное программирование получило в экономике, так какисследование зависимостей между величинами, встречающимися во многихэкономических задачах, приводит к линейной функции с линейными ограничениями,наложенными на неизвестные.
2. Области применения иограничения использования линейного программирования для решения экономическихзадач
Особенноширокое применение методы и модели линейного программирования получили прирешении задач экономии ресурсов (выбор ресурсосберегающих технологий,составление смесей, раскрой материалов, производственно-транспортных и другихзадач). [2, c.92]
Рассмотрим постановкузадачи о наилучшем использовании ресурсов. Пусть некоторая производственнаяединица (цех, завод, объединение и т. д.), исходя из конъюнктуры рынка,технических или технологических возможностей и имеющихся ресурсов, можетвыпускать n различных видов продукции (товаров),известных под номерами, обозначаемыми индексом j />. Товары будем обозначать />.Предприятие при производстве этих видов продукции должно ограничиватьсяимеющимися видами ресурсов, технологий, других производственных факторов(сырья, полуфабрикатов, рабочей силы, оборудования, электроэнергии и т. д.).Все эти виды ограничивающих факторов называют ингредиентами />. Пусть их число равно m; припишем им индекс i />. Они ограничены, и их количества равны соответственно/> условных единиц. Такимобразом, /> - вектор ресурсов.Известна экономическая выгода (мера полезности) производства продукции каждоговида, исчисляемая, скажем, по отпускной цене товара, его прибыльности,издержкам производства, степени удовлетворения потребностей и т. д. Примем вкачестве такой меры, например, цену реализации />/>, т. е. />— вектор цен.Известны также технологические коэффициенты />,которые указывают, сколько единиц i–го ресурса требуется для производства единицы продукции j-го вида. Матрицу коэффициентов /> называют технологической иобозначают буквой А. Имеем />.Обозначим через />планпроизводства, показывающий, какие виды товаров /> нужнопроизводить и в каких количествах, чтобы обеспечить предприятию максимум объемареализации при имеющихся ресурсах. Так как />-цена реализации единицы j-йпродукции, цена реализованных /> единицбудет равна />, а общий объем реализациипримет вид (формула 2.1). Это — целевая функция, которую нужно максимизировать.
/> (2.1)
Так как /> — расход i-го ресурса на производство /> единиц j-й продукции, то, просуммироваврасход i-горесурса на выпуск всех n видов продукции, получим общийрасход этого ресурса, который не должен превосходить />/> единиц (формула 2.2).
/>/> (2.2)
Чтобы искомый план />был реализован, наряду с ограничениямина ресурсы нужно наложить условие неотрицательности на объёмы /> выпуска продукции /> />.
В модель задачи о наилучшемиспользовании ресурсов входят: целевая функция (формула 2.3), системаограничений (формула 2.4) и условия неотрицательности (формула 2.5)
/> (2.3)
/> /> (2.4)
/> /> (2.5)
Так как переменные /> входят в функцию /> и систему ограниченийтолько в первой степени, а показатели /> являютсяпостоянными в планируемый период, то это – задача линейного программирования.
В различных отраслях народногохозяйства возникает проблема составления таких рабочих смесей на основе исходныхматериалов, которые обеспечивали бы получение конечного продукта, обладающегоопределенными свойствами. К этой группе задач относятся задачи о выборе диеты,составлении кормового рациона в животноводстве, шихт в металлургии, горючих исмазочных смесей в нефтеперерабатывающей промышленности, смесей для получения бетонав строительстве и т. д… Высокий уровень затрат на исходные сырьевые материалыи необходимость повышения эффективности производства выдвигает на первый планследующую задачу: получить продукцию с заданными свойствами при наименьших затратахна исходные сырьевые материалы.
Сущность задачи обоптимальном раскрое состоит в разработке таких технологически допустимых плановраскроя, при которых получается необходимый комплект заготовок, а отходы (подлине, площади, объему, массе или стоимости) сводятся к минимуму. Более сложныепостановки ведут к задачам целочисленного программирования.
Общаяпостановка транспортной задачи состоит в определении оптимального планаперевозок некоторого однородного груза из m пунктов отправления /> в n пунктов назначения />. При этом в качествекритерия оптимальности обычно берется либо минимальная стоимость перевозоквсего груза, либоминимальное время его доставки. Рассмотрим транспортную задачу, в качествекритерия оптимальности которой взята минимальная стоимость перевозок всегогруза. Обозначим через /> тарифы перевозкиединицы груза из i-го пункта отправления в j-й пункт назначения, через /> – запасы груза в i-мпункте отправления, через /> –потребности в грузе в j–м пункте назначения, а через /> – количество единиц груза,перевозимого из i-го пункта отправления в j-й пункт назначения. Тогдаматематическая постановка задачи состоит в определении минимального значенияфункции (формула 2.7) при определенных ограничениях (формула 2.8) и условиях неотрицательности(формула 2.9).
/> (2.7)
/> (2.8)
/>
/> (2.9)
Обычно исходные данныетранспортной задачи записывают в виде таблицы, которую называют матрицейпланирования. (табл. 2.1).
Таблица 2.1
Матрица планирования ТЗПоставщики Потребители Запасы B1 B2 … Bn A1 C11 C12 … C1n a1 A2 C21 C22 … C2n a2 … … … … … … Am Cm1 Cm2 … Cmn am b1 b2 … bn
Таким образом,обеспечивается доставка необходимого количества груза в каждый из пунктовназначения, вывоз имеющегося груза из всех пунктов отправления, а такжеисключаются обратные перевозки. Всякое неотрицательное решение систем линейныхуравнений называется планом транспортной задачи. План, при котором целевая функцияпринимает свое минимальное значение, называется оптимальным планом транспортнойзадачи. Если в опорном плане число отличных от нуля компонент равно в точности n+m–1, топлан является невырожденным, а если меньше – то вырожденным. [3 c.132-134]
Если общая потребность вгрузе в пунктах назначения равна запасу груза в пунктах отправления, то модельтакой транспортной задачи называется закрытой. Если же указанное условие невыполняется, то модель транспортной задачи называетсяоткрытой.
В случаепревышения запаса над потребностью, вводится фиктивный (n+1)–й пункт назначенияс потребностью (формула 2.10) и соответствующие тарифы считаются равными нулю.Аналогично, в случае, если потребности превышают количество запасов, также вводитсяфиктивный (m+1)–й пункт отправления с запасом груза и тарифы полагаются равныминулю (формула 2.11). Этим задача сводится к обычной транспортной задаче, изоптимального плана которой получается оптимальный план исходной задачи.
/> (2.10)
/> (2.11)
Как и для всякой задачилинейного программирования, оптимальный план транспортной задачи является иопорным планом. Опорный планявляется допустимым решением ТЗ и используется в качественачального базисного решения при нахождении оптимального решения методомпотенциалов. Существует четыре метода нахождения опорных планов:
1. метод северо-западногоугла;
2. метод минимального элемента;
3. метод двойногопредпочтения;
4. метод штрафов (Фогеля).
«Качество»опорных планов, полученных этими методами, различается: в общем случае методФогеля дает наилучшее решение (зачастую оптимальное), а метод северо-западногоугла– наихудшее.
Всесуществующие методы нахождения опорных планов отличаются только способом выбораклетки для заполнения. Само заполнение происходит одинаково независимо отиспользуемого метода. Следует помнить, что перед нахождением опорного планатранспортная задача должна быть сбалансирована.
В методе северо-западногоугла из всех не вычеркнутых клеток выбирается самая левая и верхняя(северо-западная) клетка. Другими словами, на каждом шаге выбирается первая изоставшихся не вычеркнутых строк и первый из оставшихся не вычеркнутых столбцов.
Для тогочтобы заполнить клетку (i,j), необходимо сравнить текущий запас товара в рассматриваемой i-й строке с текущейпотребностью в рассматриваемом j-м столбце. Нахождение опорного плана продолжается до техпор, пока не будут вычеркнуты все строки и столбцы. [3 c.137]
В методеминимального элемента первой клеткой выбирают клетку с наименьшей суммойдоставки и заполняют ее максимально возможным грузом.
Если таблицастоимостей велика, то перебор всех элементов затруднителен. В этом случаеиспользуют метод двойного предпочтения, суть которого заключается в следующем:в каждой строке и каждом столбце отмечают «V» наименьшую стоимость, а затемклетки с двойным символом «VV» заполняют с учетом наименьшей стоимости. Затемраспределяют перевозки по клеткам, отмеченным знаком «V». В оставшейся частитаблицы перевозки распределяют по наименьшей стоимости.
На каждомшаге метода Фогелядля каждой i-йстроки вычисляются штрафы, как разность между двумя наименьшими тарифамистроки. Таким же образом вычисляются штрафы для каждого j-го столбца. После чего выбираетсямаксимальный штраф из всех штрафов строк и столбцов. В строке или столбце,соответствующем выбранному штрафу, для заполнения выбирается не вычеркнутаяклетка с минимальным тарифом. Если существует несколько одинаковых по величинемаксимальных штрафов в матрице, то в соответствующих строках или столбцахвыбирается одна не вычеркнутая клетка с минимальным тарифом.
Если клеток сминимальным тарифом также несколько, то из них выбирается клетка (i,j) с максимальнымсуммарным штрафом, т.е. суммой штрафов по i-й строке и j-му столбцу.
Если план транспортнойзадачи является оптимальным, то ему соответствует система из m+n чисел Ui и Vj, удовлетворяющих условиям: Ui+Vj=Cij для занятыхклеток и Ui+Vj≤Сij всвободных клетках. Числа Ui и Vj называются потенциалами соответственнопоставщиков и потребителей. При решении одному неизвестному потенциалупридается произвольное значение. [3 c.141]
3. Оптимизация прибыли сприменением метода линейного программирования
3.1 Постановка задачи и формирование оптимизационной модели
Предприятие реализуеттовары трех групп. Известны нормативы затрат ресурсов Aij в расчете на единицу товара иограничения по располагаемым ресурсам, которые приведены в (табл. 3.1)
Таблица 3.1
Нормативы затрат ресурсови ограниченийРесурсы Нормативы затрат ресурсов по продаже товаров Aj Bj Cj Рабочее время, чел.ч. А11=0,1 А12=0,2 А13=0,4 Площадь торговых помещений, м2 А21=0,05 А22=0,02 А23=0,02 Издержки обращения на ед. товара, руб. А31=3 А32=1 А33=2 Доход на единицу товара, руб. С1=3 С2=5 С3=4 План продажи, ед. X1 X2 X3
Ограничение объемовресурсов составляют: ресурс первого вида ≤ 1300, ресурс второго вида ≤140, ресурс третьего вида ≤8200.
Необходимо составитьоптимальный план товарооборота по критерию максимума дохода.
Это классическая задачалинейного программирования о наилучшем использовании ресурсов. В данной задачетакже будет присутствовать целочисленное программирование, т.к. продукциянеделимая.
Составим оптимизационнуюмодель. Запишем целевую функцию(формула 3.1), ограничения на количестворесурсов (формула 3.2) и условия неотрицательности (формула 3.3)
/> (3.1)
/> (3.2)
/>
/>
/> (3.3)3.2 Расчет и анализ результатов оптимизации прибыли
Первоначальный опорныйплан симплекс методом находится только тогда, когда в системе ограничения левыеи правые части уравнения равны. Поэтому необходимо перейти от неравенств кравенствам, прибавляя к левым частям неотрицательные дополнительные переменные(дополнительным переменным в линейной функции соответствуют коэффициенты равныенулю). Следовательно, целевая функция (формула 3.4), система ограничений(формула 3.5) и условия неотрицательности (формула 3.6)примут другой вид.
/> (3.4)
/> (3.5)
/>
/>
/> (3.6)
Решаем задачу симплекснымметодом. Расчеты производим в симплекс таблице. (см. табл. 3.2)
Таблица 3.2
Первая симплекснаятаблицаБазис Cj баз. B X1 X2 X3 X4 X5 X6 3 5 4 X4 1300 0.1 0.2 0.4 1 X5 140 0.05 0.02 0.02 1 X6 8200 3 1 2 1 П(x) -3 -5 -4
Этот план не являетсяоптимальным, так как в строке «прибыль» есть три отрицательные оценки. Выбираянаименьшую оценку, находим направляющий столбец. Направляющую строку находим,поочередно деля, значение «В» i-йстроки на элемент i-й строкинаправляющего столбца. Направляющей строкой будет та, в которой значениечастного будет наименьшим. Направляющий столбец — пятый, направляющая строка первая.Разрешающий элемент находим на пересечении направляющей строки и столбца, онравен 0.2. Строим вторую симплексную таблицу. (табл. 3.3)
Таблица 3.2
Вторая симплекснаятаблицаБазис Cj баз. B X1 X2 X3 X4 X5 X6 3 5 4 X2 5 6500 0.5 1 2 5 X5 10 0.04 -0.02 -0.1 1 X6 1700 2.5 -5 1 П(x) 32500 -0.5 6 25
Этот план тоже неоптимальный, так как в строке «прибыль» еще есть отрицательные элементы. Снова находимнаправляющий столбец и строку. Направляющий столбец — четвертый, направляющаястрока — вторая. Разрешающий элемент равен 0.04. Строим третью симплекснуютаблицу. (табл. 3.4)
Таблица 3.3
Третья симплекснаятаблицаБазис Cj баз. B X1 X2 X3 X4 X5 X6 3 5 4 X2 5 6375 1 2.25 6.25 -12.5 X1 3 250 1 -0.5 -2.5 25 X6 1075 1.25 1.25 -62.5 1 П(x) 32625 5.75 23.75 12.5
В результате проведениядвух итераций получаем оптимальный план />,которому соответствует максимальное значение линейной функции F(x)max=32625.
В итоговой строке«прибыль» на пересечении со столбцами X4 X5 X6 можно найти двойственные оценкиресурсов, которые покажут, какую прибыль приносит одна единица каждогоимеющегося в наличии ресурса.
Прибыль от одногочеловеко-часа рабочего времени составит 23 рубля 75 копеек. Прибыль от одногоквадратного метра торговых помещений равна 12 рублям 50 копейкам, а третийресурс (издержки обращения на единицу товара) использован не полностью иприбыль от него равна 0 рублям.
Ответ: Предприятиюнеобходимо реализовывать 250 единиц товара первой группы и 6375 единиц товаравторой группы, тогда остатки третьего ресурса (издержки обращения на единицутовара) составят 1075 рублей. При этом максимальный доход будет равен 32625рублей.
Заключение
Содержаниематематического программирования составляют теория и методы решения задач онахождении экстремумов функций на множествах, определяемых линейными инелинейными ограничениями (равенствами и неравенствами). Математическоепрограммирование является одним из разделов науки об исследовании операций.
Задачи математическогопрограммирования находят применение в различных областях человеческойдеятельности, где необходим выбор одного из возможных образов действий(программ действий), например, при решении проблем управления и планированияпроизводственных процессов, в проектировании и перспективном планировании, ввоенном деле и т.д.
Значительное число задач,возникающих в обществе, связано с управляемыми явлениями, т.е. с явлениями,регулируемыми на основе сознательно принимаемых решений. При том ограниченномобъеме информации, который был доступен на ранних этапах развития общества,принималось оптимальное в некотором смысле решение на основании интуиции иопыта, а затем, с возрастанием объема информации об изучаемом явлении, — с помощьюряда прямых расчетов. Так происходило, например, создание календарных плановработы промышленных предприятий.
Совершенно иная картинавозникает на современном промышленном предприятии с многосерийным имногономенклатурным производством, когда объем входной информации столь велик,что его обработка с целью принятия определенного решения невозможна безприменения компьютеров. Еще большие трудности возникают в связи с задачей опринятии наилучшего решения. Проблема принятия решений в исследовании операцийнеразрывно связана с процессом моделирования.
Первый этап процессамоделирования состоит в построении качественной модели. Второй этап — построение математической модели paccматриваемой проблемы. Этот этап включаеттакже построение целевой функции, т. е. такой числовой характеристики, большему(или меньшему) значению которой соответствует лучшая ситуация с точки зренияпринимающего решения. Итак, в результате этих двух этапов формируетсясоответствующая математическая задача.
Третий этап — исследование влияния переменных на значение целевой функции. Этот этаппредусматривает владение математическим аппаратом для решения математическихзадач, возникающих на втором этапе процесса принятия решения.
Четвертый этап — сопоставление результатов вычислений, полученных на третьем этапе, смоделируемым объектом, т. е. экспертная проверка результатов (критерийпрактики). Таким образом, на этом этапе устанавливается степень адекватностимодели и моделируемого объекта в пределах точности исходной информации.
Широкий класс задачуправления составляют такие экстремальные задачи, в математических моделях которыхусловия на переменные задаются равенствами и неравенствами. Теория и методырешения этих задач как раз и составляют содержание математическогопрограммирования.
Список литературы
1. Берюхова Т.Н.Банк производственных задачв расчетах на ЭВМ: учебное пособие. – Тюмень.: ТюмИИ, 1992. – 124с.
2. Карманов В.Г. Математическоепрограммирование: учебное пособие для студентов вузов. – М.: Физматлит, 2001. –264с.
3. Кузнецов А.В. Математическоепрограммирование: учебное пособие для вузов. – М.: Высшая школа, 1976. – 352с.
4. Мочалов И.А. Нечеткое линейноепрограммирование. // Промышленные АСУ и контроллеры. – 2006. — № 10. – с.26-29.
5. Пашутин С.Оптимизация издержек итехнология формирования оптимального ассортимента. // Управление персоналом. –2005. — №5. – с.20-24.