Математические методы

ВВЕДЕНИЕ

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

Целочисленное программирование возникло в 50-60-е годы нашего века из нужд практики - главным образом в работах американских математиков Дж.Данцига и Р.Гомори. Первоначально целочисленное программирование развивалось независимо от геометрии чисел на основе теории и методов математической оптимизации, прежде всего линейного программирования. Однако в последние время исследования в этом направлении все чаще проводятся средствами математики целых чисел.

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

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

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

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

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

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

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

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

 

1 ПОСТАНОВКА ЗАДАЧИ

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

Компания по производству игрушек изготавливает две различные игрушки А и В. Каждая игрушка должна производиться тремя машинами: 1,2 и 3. Эти машины могут обрабатывать только одну игрушку в каждый момент времени. Изготовление одной единицы А требует 40 мин. – 1 машины, 20 мин. – 2 машины, 10 мин. – 3 машины. Для изготовления одной единицы В необходимо 20 мин. – 1 машины, 30 мин. – 2 машины, 30 мин. – 3 машины. Каждая машина может работать 40 часов в неделю. Игрушка А приносит 4 рубля прибыли на единицу, а В – 3 рубля. Полагают, что спрос на эти игрушки превышает предложение компании. Сколько каждого вида игрушек должна делать компания каждую неделю, чтобы максимизировать прибыль?

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

Приведём экономическую задачу в математическую форму, для этого введём следующие переменные:

х1 – игрушка А;

х2 – игрушка В;

Переведем часы в минуты : 40 часов в неделю=2400 минут в неделю.

Математический вид:

F(х)=4 х1+ 3х2 →max

при ограничениях

40x1 + 20x2≤2400

20x1 + 30x2≤2400

10x1 + 30x2≤2400

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

В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≤) вводим базисную переменную x5. 

40x1 + 20x2 + 1x3 + 0x4 + 0x5 = 2400

20x1 + 30x2 + 0x3 + 1x4 + 0x5 = 2400

10x1 + 30x2 + 0x3 + 0x4 + 1x5 = 2400

 

2 МЕТОД ОПТИМИЗАЦИИ

Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например:

• количество продукции - расход сырья
• количество продукции - качество продукции

Для постановки задачи оптимизации необходимо:

1. Наличие объекта оптимизации  и цели оптимизации. При этом  формулировка каждой задачи оптимизации должна требовать экстремального значения лишь одной величины, т.е. одновременно системе не должно приписываться два и более критериев оптимизации, т.к. практически всегда экстремум одного критерия не соответствует экстремуму другого.

2. Наличие ресурсов оптимизации, под которыми понимают возможность выбора значений некоторых параметров оптимизируемого объекта.

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

4. Учет ограничений.

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

2.1 Характеристика линейного  программирования

Термин "программирование" в названии дисциплины ничего общего с термином "программирование (т.е. составление программ) для ЭВМ" не имеет, так как дисциплина "линейное программирование" возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и др. задач. Термин "линейное программирование" возник в результате неточного перевода английского "linear programming". Одно из значений слова "programming" - составление планов, планирование. Следовательно, правильным переводом "linear programming" было бы не "линейное программирование", а "линейное планирование", что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми.

Итак, линейное программирование возникло после Второй Мировой Войны и стал быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а так же математической "стройности".

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

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

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

Первые постановки задач линейного программирования были сформулированы известным советским математиком Л.В. Канторовичем, которому за эти работы была присуждена Нобелевская премия по экономике.

Значительное развитие теория и алгоритмический аппарат линейного программирования получили с изобретением и распространением ЭВМ и формулировкой американским математиком Дж. Дансингом симплекс-метода.

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

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

2.2 Характеристика целочисленного  программирования

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

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

• задачи оптимизации раскроя;
• оптимальное проектирование лесных машин и оборудования;
• оптимизации системы сервиса и технического обслуживания машинно-тракторного парка;
• и т.д.

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

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

2.3 Понятие симплекс-метода

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

Пусть стоит задача максимизации (минимизации)

при условиях

где Aj (j=1,...,n) , B - m-мерные векторы. 
Напомним несколько ключевых определений и свойств задачи.

Вектор X=(X1,X2,..,Xn) , удовлетворяющий условиям (1.2) и (1.3), называется планом. Множество планов в геометрической интерпретации представляет собой выпуклый многогранник.