Методы решения задач математического моделирования

• Введение
• 1. теоретическая часть
• 1.1 Определение основных понятий математического моделирования и характеристика этапов создания математической модели
• 1.2 Характеристика типовых задач математического моделирования и подходов к их решению
• 1.3 Определение и характеристика линейного программирования
• 1.4 Характеристика симплекс-метода как основного аппарата решения задач линейного программирования
• 1.5 Основные этапы, особенности и методы решения транспортной задачи
• 2. Практическая часть
• 2.1 Составление математической модели задачи планирования производства
• 2.2 Решение задачи планирования производства геометрическим способом
• 2.3 Решение задачи планирования производства симплекс-методом
• 2.4 Решение задачи планирования производства с помощью табличного процессора MS Excel
• 2.5 Составление математической модели транспортной задачи
• 2.6 Нахождение опорного плана транспортной задачи методом северо-западного угла
• 2.7 Нахождение опорного плана транспортной задачи методом наименьшего элемента
• 2.8 Решение транспортной задачи методом потенциалов
• 2.9 Решение транспортной задачи при помощи табличного процессора Excel
• Заключение
• Литература
• Приложение 1
• Приложение 2

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

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

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

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

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

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

Из поставленной цели вытекают следующие задачи:

1. Изучение теоретической части материала.

2. Создание математических моделей задач планирования производства и транспортных задач

3. Решение задачи планирования производства аналитическим и программным методами.

4. Решение транспортной задачи различными методами и программным способом.

1. теоретическая часть

1.1 Определение основных понятий математического моделирования и характеристика этапов создания математической модели

Под моделированием понимают процесс построения, изучения и применения моделей.

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

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

В математических методах широко применяются как аналитические, так и статистические модели.

Аналитические модели более грубы, учитывать меньшее число факторов, всегда требует каких-то допущений и упрощений.

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

Операции — всякое мероприятие, система действий, объединенных единым замыслом и направлением к достижению какой-либо цели. Операция является управляемым мероприятием, то есть от нас зависти, каким способом выбрать некоторые параметры, характеризующие ее организацию.

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

Решение - это всякий определенный набор зависящих от нас параметров.

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

Допустимыми решения - это решения, удовлетворяющие системе ограничений и требованию неотрицательности.

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

Оптимальный план — допустимый план, который удовлетворяет условиям максимизации или минимизации (в зависимости от условия задачи).

Целевая функция — функция переменных, от которых зависит достижение оптимального состояния системы.

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

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

· Первый этап — формулировка законов, связывающих основные объекты модели. Этот этап требует широкого знания фактов, относящихся к изучаемым явлениям, и глубокого проникновения в их взаимосвязи.

· Второй этап — исследование математических задач, к которым приводят построенные математические модели.

· Третий этап — выяснение того, удовлетворяет ли принятая гипотетическая модель критерию практики.

· Четвертый этап — последующий анализ модели в связи с накоплением данных об изучаемых явлениях и модернизации модели

Основные этапы математического моделирования

1) Построение модели. На этом этапе задается некоторый «нематематический» объект — явление природы, конструкция, экономический план, производственный процесс и т. д. При этом, как правило, четкое описание ситуации затруднено. Сначала выявляются основные особенности явления и связи между ними на качественном уровне. Затем найденные качественные зависимости формулируются на языке математики, то есть строится математическая модель. Это самая трудная стадия моделирования.

2) Решение математической задачи, к которой приводит модель. На этом этапе большое внимание уделяется разработке алгоритмов и численных методов решения задачи на ЭВМ, при помощи которых результат может быть найден с необходимой точностью и за допустимое время.

3) Интерпретация полученных следствий из математической модели. Следствия, выведенные из модели на языке математики, интерпретируются на языке, принятом в данной области.

4) Проверка адекватности модели. На этом этапе выясняется, согласуются ли результаты эксперимента с теоретическими следствиями из модели в пределах определенной точности.

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

Классификация моделей

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

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

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

1.2 Характеристика типовых задач математического моделирования и подходов к их решению

Задачи моделирования делятся на две категории: прямые и обратные.

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

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

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

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

Их можно разделить на:

принятие решений в условиях определенности — исходные данные — детерминированные; принятие решений в условиях неопределенности — исходные данные — случайные величины.

Таблица 1.2.1

Классификация задач оптимизации

А по критерию эффективности:

· одноцелевое принятие решений (один критерий эффективности);

· многоцелевое принятие решений (несколько критериев эффективности).

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

В общем виде обратная детерминированная задача будет выглядеть следующим образом.

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

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

Реальные задачи содержит помимо выше перечисленных факторов, еще одну группу — неизвестные факторы. Тогда обратную задачу можно сформулировать следующим образом.

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

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

1.3 Определение и характеристика линейного программирования

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

Линейное программирование — наиболее разработанный и широко применяемый раздел математического программирования. Это объясняется следующим:

· математические модели очень большого числа экономических задач линейны относительно искомых переменных;

· эти типы задач в настоящее время наиболее изучены;

· для них разработаны специальные конечные методы, с помощью которых эти задачи решаются, и соответствующие стандартные программы для их решения на ЭВМ;

· многие задачи линейного программирования, будучи решенными, нашли уже сейчас широкое практическое применение в народном хозяйстве;

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

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

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

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

В общей постановке задача линейного программирования выглядит следующим образом:

Имеются какие-то переменные х = (х₁, х₂, … х_n) и функция этих переменных f (x) = f (х₁, х₂, … х_n), которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции f (x) при условии, что переменные x принадлежат некоторой области G:

В зависимости от вида функции f (x) и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т. д. Линейное программирование характеризуется тем, что а) функция f (x) является линейной функцией переменных х₁, х₂, … х_nб) область G определяется системой линейных равенств или неравенств.

Математическая модель любой задачи линейного программирования включает в себя:

· максимум или минимум целевой функции (критерий оптимальности);

· систему ограничений в форме линейных уравнений и неравенств;

· требование неотрицательности переменных.

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

1.4 Характеристика симплекс-метода как основного аппарата решения задач линейного программирования

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

Допустим, предприятие предполагает выпускать два вида продукции и, для производства которых используется сырьё трех видов.

Производство обеспечено сырьем каждого вида в количествах:, , кг. На изготовление единицы изделия требуется затратить сырья каждого вида, , кг., соответственно, а для единицы изделия —, , кг. Прибыль от реализации единицы изделия составляет ден.ед., для единицы изделия — ден.ед. (табл.1.4.1).

Таблица 1.4.1

Составляем математическую модель:

математический моделирование производство транспортный

(1.4.1)

Введем базисные переменные и преобразуем исходную задачу к виду:

(1.4.2)

Решим систему уравнений относительно базисных переменных x3, x4, x5.

Таблица 1.4.2

Итерация № 0

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

— вектор, составленный из координат соответствующих базисных переменных.

Текущий план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

Будем считать что Z2 наименьший элемент, а строку с наименьшим отношением свободного члена к соответствующему элементу выбранного столбца — строку Х4.

Ведущий столбец Х2, так как (- наименьшее отрицательное число.

За ведущую выберем строку 2, так как отношение свободного члена к соответствующему элементу выбранного столбца для 2 строки является наименьшим.

Разрешающий элемент .

Разделим элементы строки 2 на разрешающий элемент ().

От элементов строки 1 отнимаем соответствующие элементы строки 2, умноженные на .

От элементов строки 3 отнимаем соответствующие элементы строки 2, умноженные на .

От элементов строки Z отнимаем соответствующие элементы строки 3, умноженные на .

Заменяем базисную переменную Х5 на Х1.

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

Порядок работы с симплекс таблицей

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

Алгоритм перехода к следующей таблице такой:

· просматривается последняя строка (индексная) таблицы и среди коэффициентов этой строки (исключая столбец свободных членов Y0) выбирается наименьшее отрицательное число при отыскании max, либо наибольшее положительное при задачи на min. Если такового нет, то исходное базисное решение является оптимальным и данная таблица является последней;

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

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

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

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

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

· в новой таблице все элементы ключевого столбца = 0, кроме разрезающего, он всегда равен 1.

· столбец, у которого в ключевой строке имеется 0, в новой таблице будет таким же.

· строка, у которой в ключевом столбце имеется 0, в новой таблице будет такой же.

· в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы

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

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

1.5 Основные этапы, особенности и методы решения транспортной задачи

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

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

Таблица 1.5.1

Составим математическую модель данной задачи:

Целевая функция:

(1.5.1)

Ограничения:

(1.5.2)

— количество груза, отправляемого с базы в пункт

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

Методы решения транспортных задач

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

Условия задачи удобно располагать в таблице, вписывая в ячейки количество перевозимого груза из Аi в Bj груза X_ij? 0, а в маленькие клетки — соответствующие тарифы C_ij.(рис. 1.5.1)

Рисунок 1.5.1

Затем решение задачи разбивается на два этапа:

· Определение опорного плана (Это решение можно найти, используя метод «северо-западного угла» или метод «минимального элемента» .)

· Нахождение оптимального решения путем последовательных операций. Метод северо-западного угла

Сущность метода заключается в том, что на каждом шаге заполняется левая верхняя (северо-западная) клетка оставшейся части таблицы, причем максимально возможным числом: либо полностью выносится груз из Аi, либо полностью удовлетворяется потребность Вj. Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы аi и не удовлетворятся все потребности bj. В заключении проверяют, удовлетворяют ли найденные компоненты плана Х_ij горизонтальным и вертикальным уравнениям.

Метод наименьшего элемента

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

Метод потенциалов

Соотношения определяют систему из m+n-1 линейных уравнений с m+n известными, имеющую бесчисленное множество решений; для её определённости одному неизвестному присваивают произвольное значение (обычно альфа равное 0), тогда все остальные неизвестные определяются однозначно.

Критерий оптимальности Если известны потенциалы решения Х0 транспортной задачи и для всех незаполненных ячеек выполняются условия б_i+в_j? C_ij, то Х0 является оптимальным планом транспортной задачи.

Если план не оптимален, то необходимо перейти к следующему плану (таблице) так, чтобы транспортные расходы не увеличивались.

Цикл перерасчёта таблицы — это последовательность ячеек, удовлетворяющая условиям:

· Одна ячейка пустая, все остальные занятые.

· Любые две соседние ячейки находятся в одной строке или в одном столбце.

· Никакие три соседние ячейки не могут быть в одной строке или в одном столбце.

Пустой ячейке присваивают знак «+», остальным — поочерёдно знаки «-» и «+» .

Для перераспределения плана перевозок с помощью цикла перерасчёта сначала находят незаполненную ячейку (r, s), в которой бr+вs > Crs, и строят соответствующий цикл; затем в минусовых клетках находят число X = min (X_ij). Далее составляют новую таблицу по следующему правилу:

· В плюсовых клетках добавляем Х.

· Из минусовых клеток вычитаем Х.

· Все остальные клетки вне цикла остаются без изменения.

Получим новую таблицу, дающую новое решение Х, такое, что F (X₁)? F (X₀); оно снова проверяется на оптимальность через конечное число шагов, обязательно найдем оптимальный план транспортной задачи, ибо он всегда существует.

2. Практическая часть

2.1 Составление математической модели задачи планирования производства

Задача. Предприятие предполагает выпускать два вида продукции А1 и А2, для производства которых используется сырь? трех видов. Производство обеспечено сырьем каждого вида в количествах: b1, b2, b3 кг. На изготовление единицы изделия А1 требуется затратить сырья каждого вида а11, а21, а31 кг, соответственно, а для единицы изделия А2 — а12, а22, а32 кг. Прибыль от реализации единицы изделия А1 составляет с1 ден.ед., для единицы изделия А2 — с2 ден.ед.

Требуется составить план производства изделий А1 и А2 обеспечивающий максимальную прибыль предприятия от реализации готовой продукции.

Таблица 2.1.1

Исходная таблица

Математическая модель

Пусть x1-количество изделий А₁; Х2-количество изделий А₂;

Ограничения:

Целевая функция: Z= 40×1 + 30×2 > max

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

Найдем область допустимых решений

Посмотрим прямые:

4x1+x2=240

2x1+3×2=180

1x1+5×2=251

Рисунок 2.2.1

Многоугольник OABCDобласть допустимых решений.

Построим прямую уровня

Возьмем из области допустимых решений произвольную точку М (20; 20), подставим в целевую функцию:

Z: 40 *20 + 30 * 20 = 1400

40×1 + 30×2 = 1400 — уравнение прямой уровня.

Результаты расчётов приведены на рис. 2.2.1.

Определим направление перемещения прямой уровня

б (40; 30) — координаты вектора, в направлении которого нужно перемещать прямую уровня до пересечения с последней граничной точкой области допустимых решений.

Эта точка С.

Найдём её координаты:

Найдем максимальную прибыль

40*54+30*24=2880

Ответ: Для достижения максимальной прибыли 2880 ден.ед. следует производить 54 ед. продукции вида А₁ и 24. продукции вида А₂.

2.3 Решение задачи планирования производства симплекс-методом

Введем базисные переменные и преобразуем исходную задачу к виду:

Z= 40×1 + 30×2 + 0x₃ + 0x₄ + 0x₅ > max

Решим систему уравнений относительно базисных переменных: x₃, x₄, x₅.

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,240,180,251)

Таблица 2.3.1

Итерация № 0

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

Сб — вектор, составленный из координат соответствующих базисных переменных.

Текущий план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

Ведущий столбец X1, так как -40 — наименьшее отрицательное число.

За ведущую выберем строку 1, так как отношение свободного члена к соответствующему элементу выбранного столбца для 3 строки является наименьшим.

Таблица 2.3.2

Разрешающий элемент 4

От элементов строки 2 отнимаем соответствующие элементы строки 1, умноженные на 2.

От элементов строки 3 отнимаем соответствующие элементы строки 1, умноженные на 1.

От элементов строки ?? отнимаем соответствующие элементы строки 1, умноженные на -40 (Табл. 2.3.2)

Заменяем базисную переменную X3 на X1

Таблица 2.3.3

Итерация № 1

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

За ведущий выберем столбец 2, так как -20 наименьший элемент в ?? строке.

За ведущую выберем строку 2, так как отношение свободного члена к соответствующему элементу выбранного столбца для 2 строки является наименьшим.

Разрешающий элемент 2,5

Разделим элементы строки 2 на 2,5(Табл. 2.3.3).

Таблица 2.3.4

От элементов строки 1 отнимаем соответствующие элементы строки 2, умноженные на 0,25.

От элементов строки 3 отнимаем соответствующие элементы строки 2, умноженные на 4,75.

От элементов строки ?? отнимаем соответствующие элементы строки 2, умноженные на -20

Таблица 2.3.5

X2 = (54, 24, 77, 0, 0)

??(X2) = 40*54 + 30*24 = 2880 (Табл. 2.3.5).

Ответ: Для достижения максимальной прибыли 2880 ден.ед. следует производить 54 ед. продукции вида А1 и 24 ед. продукции вида А2. (ответ совпадает с ответом полученным графическим способом).

2.4 Решение задачи планирования производства с помощью табличного процессора MS Excel

1) Ввод данных

Вводим данные таблицы 3 в ячейки EXCEL (рис. 2.4.1.).

· В ячейках B3: С5 введены виды продукции.

· В ячейках B6: C6 находится прибыль от реализации единицы изделия A1 и А2.

· В ячейках D3: D5 находятся ограничения по сырью.

2) Записываем формулы для вычисления ограничений

Введем формулы в ячейки B7: B9

· B7: =B10*B3+B11*C3

· B8: =B10*B4+B11*C4

· B9: =B10*B5+B11*C5

3) Записываем формулу для вычисления целевой функции Целевая функция находится в ячейке E2

· В ячейку E2 введем формулу: =B10*B6+B11*C6

Рисунок 2.4.1

4) Заполнение окна процедуры «Поиск решения»

· Целевая функция: E2 ($E$ 2);

· Вид поиска: max;

· Изменяемые ячейки: B10: B11 ($B$ 10:$B$ 11);

· В поле «Ограничения» добавим заданные ограничения:

$B$ 10:$B$ 11 = целое;

$B$ 10:$B$ 11 >= 0;

$B$ 7 <= $D$ 3

$B$ 8 <= $D$ 4

$B$ 9 <= $D$ 5

· В окне «Параметры» установить «Линейная модель». Результаты заполнения окна показаны на (рис. 2.4.2), (рис. 2.4.3).

Рисунок 2.4.2

Рисунок 2.4.3

5) Выполнив процедуру «Поиск решения» получим следующие результаты (рис. 2.4.4):

Рисунок 2.4.4

Ответ: Для достижения максимальной прибыли 2880 ден.ед. следует производить 54 ед. продукции вида А1 и 24 ед. продукции вида А2. (ответ совпадает с ответом полученным графическим способом и соответствует решению задачи симплекс-методом).

2.5 Составление математической модели транспортной задачи

Задача На три базы А1, А2, А3 поступил однородный груз в количествах: а1, a2, а3 соответственно. Груз требуется развести в пять пунктов: b1 в пункт В1, b2 В пункт В3, b3 в пункт В3, b4 в пункт В4, b5 в пункт В5.

Спланировать перевозки так, чтобы их общая стоимость была минимальной.

Математическая модель транспортной задачи:

Пусть Хij — количество груза, отправляемого с базы Аi в пункт Вj.

Целевая функция:

Таблица 2.5.1

Исходная таблица

Ограничения:

2.6 Нахождение опорного плана транспортной задачи методом северо-западного угла

Используя метод северо-западного угла, построим первый опорный план транспортной задачи (Табл. 2.6.1).

Таблица 2.6.1

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

2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n — 1 = 7. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F (x) = 2*100 + 10*50 + 7*40 + 12*130 + 6*30 + 13*150 + 16*80 = 5950

2.7 Нахождение опорного плана транспортной задачи методом наименьшего элемента

Используя метод наименьшего элемента, построим первый опорный план транспортной задачи (Табл. 2.7.1).

Таблица 2.7.1

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

2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n — 1 = 7. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F (x) = 2*100 + 4*50 + 7*20 + 5*150 + 18*70 + 6*160 + 16*30 = 3990

2.8 Решение транспортной задачи методом потенциалов

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

Таблица 2.8.1

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij (Табл. 2.8.1).

Выбираем максимальную оценку свободной клетки (1;5): 4

Для этого в перспективную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-» (Табл. 2.8.2).

Таблица 2.8.2

Цикл приведен в таблице (1,5; 1,2; 2,2; 2,3; 3,3; 3,5;).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т. е.

у = min (1, 2) = 50

Прибавляем 50 к объемам грузов, стоящих в плюсовых клетках и вычитаем 50 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план (Табл. 2.8.3).

Таблица 2.8.3

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

Таблица 2.8.4

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij (Табл. 2.8.4).

Выбираем максимальную оценку свободной клетки (2;1): 3

Для этого в перспективную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-» (Табл. 2.8.5).

Таблица 2.8.5

Цикл приведен в таблице (2,1; 2,3; 3,3; 3,5; 1,5; 1,1;).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (3, 5) = 30. Прибавляем 30 к объемам грузов, стоящих в плюсовых клетках и вычитаем 30 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план (Табл. 2.8.6).

Таблица 2.8.6

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

Таблица 2.8.7

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij (Табл. 2.8.7).

Выбираем максимальную оценку свободной клетки (2;4): 5

Для этого в перспективную клетку (2;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-» (Табл. 2.8.8).

Таблица 2.8.8

Цикл приведен в таблице (2,4; 2,3; 3,3; 3,4;).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (2, 3) = 50. Прибавляем 50 к объемам грузов, стоящих в плюсовых клетках и вычитаем 50 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план (Табл. 2.8.9).

Таблица 2.8.9

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

Таблица 2.8.10

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij(Табл. 2.8.10).

Минимальные затраты составят:

F (x) = 2*70 + 4*80 + 3*30 + 7*90 + 5*50 + 6*160 + 13*100 = 3690

2.9 Решение транспортной задачи при помощи табличного процессора Excel

1) Ввод данных

· Вводим данные таблицы 2.5.1 в ячейки EXCEL (рис 2.9.1).

· В ячейки B2: F4 введены стоимости перевозок.

· В ячейках H7: H9 находится количество имеющегося в наличии товара.

· В ячейках B11: F11 находятся запросы пунктов назначения.

· Ячейки B7: F9 — рабочие (изменяемые) ячейки, в которых будут вычисляться значения переменных задачи X_ij.

· В ячейках G7: G9 нужно записать формулы для вычисления левых частей ограничений

§ в G7 должна быть сумма ячеек B7: F7;

§ в G8 должна быть сумма ячеек B8: F8;

§ в G9 должна быть сумма ячеек B9: F9.

· Формулы для вычисления левых частей ограничений введем в ячейки B10: F10:

§ в B10 должна быть сумма ячеек B7: B9;

§ в C10 должна быть сумма ячеек C7: C9;

§ в D10 должна быть сумма ячеек D7: D9;

§ в E10 должна быть сумма ячеек E7: E9;

§ в F10 должна быть сумма ячеек F7: F9;

· Целевую функцию поместим в ячейку G2:

§ H4: СУММПРОИЗВ (B2:F4; B7: F9).

· Таблица исходных данных имеет вид (рис. 2.9.1):

Рисунок 2.9.1.

2) Заполнение окна процедуры «Поиск решения»

· Целевая функция: G2 ($G$ 2);

· Значение целевой функции: min;

· Изменяемые ячейки: B7: F9($B$ 7: $F$ 9);

· Ограничения задачи:

$B$ 10: $F410 = $B411: $F$ 11

$B$ 7: $F$ 9 = целое

$B$ 7: $F$ 90

$G$ 7: $G$ 9 = $H$ 7: $H$ 9

В окне «Параметры» установить «Линейная модель».

Результаты заполнения окна показаны на рис. 2.9.2.

Рисунок 2.9.2

3) Выполнив процедуру «Поиск решения» получим следующие результаты (рис. 2.9.3):

Рисунок 2.9.3

Таким образом из A1 следует отвезти 70 ед. товара в B1 и 80 ед. товара в B5; из A2 отвезти 30 ед. товара в B1, 90 ед. товара в B2 и 50 ед. товара в В4; из A3 отвезти 160 ед. товара в B3 и 100 ед. товара в B4. При этом суммарная стоимость транспортных расходов составит 3690 рубля.

Заключение

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

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

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

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

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

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

1. Кузнецов А. В., Новикова Г. И., Холод И. И. — «Сборник задач по математическому программированию». Минск, Высшая школа, 1985 г.

2. Кузнецов А. В., Новикова Г. И., Холод И. И. — «Высшая математика. Математическое программирование». Минск, Высшая школа, 2001 г.

3. Красс М. С., Чупрынов Б. П. «Основы математики и ее приложения в экономическом образовании», Издательство «Дело», Москва 2001 г.

4. Лященко И. Н. Линейное и нелинейное программирование. / Лященко И. Н., Карагодова Е. А., Черникова Н. В., Шор Н. З. — К.: «Высшая школа», 1975, 372с.

5. http://www.edu.ru

6. http://www.rfst.fsoft.ru

Приложение 1

Задача. Предприятие предполагает выпускать два вида продукции А₁ и А₂, для производства которых используется сырьё трех видов. Производство обеспечено сырьем каждого вида в количествах: b₁, b₂, b₃ кг. На изготовление единицы изделия А₁ требуется затратить сырья каждого вида а₁₁, а₂₁, а₃₁ кг, соответственно, а для единицы изделия А₂ — а₁₂, а₂₂, а₃₂ кг. Прибыль от реализации единицы изделия А₁ составляет с₁ ден.ед., для единицы изделия А₂ — с₂ ден.ед. Данные для решения задачи представлены в таблице 1

Требуется составить план производства изделий А₁ и А₂ обеспечивающий максимальную прибыль предприятия от реализации готовой продукции.

Необходимо:

· Решить задачу геометрически (графики построить в системе Mathcad);

· Решить задачу симплекс-методом;

· Решить задачу программным способом с помощью табличного процессора MS Excel.

Таблица 1

Приложение 2

Задача. На три базы А₁, А₂, А₃ поступил однородный груз в количествах: а_1, а₂, а₃ соответственно. Груз требуется развезти в пять пунктов: b₁ в пункт В₁, b₂ в пункт В₂, b₃ в пункт В₃, b₄ в пункт В₄, b₅ в пункт В₅. Данные для решения задачи представлены в таблице 2