Курсовая работа по "Математическое моделирование"

Содержание.

Введение……………………………………………………………….

Задание…………………………………………………………………

Метод решения………………………………………………………...

Выполнение……………………………………………………………

Вывод…………………………………………………………………..

Использованная литература………………………………………….

Введение

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

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

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

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

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

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

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

Задание.

Вариант ЛП ШВ 01.

Завод шампанских вин «Новый свет» производят виноградное сусло из трех сортов винограда – мускатное, столовое и изабелла.

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

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

Инструкция по составлению смесей:

Шампанское	Спецификация	Цена за 1л. Шампанского, руб.
"Мускатное"	не меньше, чем 60% мускатного	68
	не больше, чем 20%изабелла
Старый свет	не больше, чем 60% изабелла	57
	не меньше, чем 15% мускатного
"Крымское"	не больше, чем 50% изабелла	45

Запасы трех сортов сусла и их стоимость показаны ниже.

Сорт сусла	Наличие, л/день		Стоимость 1л
Мускатное	2000	70
Столовое	2500	50
Изабелла	1200	40

Сколько ежедневно следует производить «Крымского» шампанского (л)?

Метод решения.

Составление первого опорного плава. Определить вектор =(x1,x2,...,xn), который удовлет воряет ограничениям вида

a_ij·x_j ≤ b_i i =

x_j ≥ 0, j =

и обеспечивает максимальное значение целевой функции

F()= c_j·x_j → max

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

где xn+1 — базисные переменные, i =

x_j — свободные переменные, j =.

Решим эту систему относительно базисных переменных:

а функцию цели перепишем в виде уравнения

Полагая, что основные переменные х₁=х₂=x₃=...х_n=0 получим первый опорный план =(0,0,...0,b₁,b₂,...,b_n), который заносим в симплексную таблицу. Последняя строка таблицы называется индексной и заполняется коэффициентами функции цели, взятыми с противоположным знаком.

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

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

Определение ведущих столбца и строки.

Из отрицательных коэффициентов индексной строки выбираем наибольший по абсолютной величине, что и определяет ведущий столбец, который показывает, какая переменная на следующей итерации перейдет из свободных в базисные. Затем элементы столбца свободных членов симплексной таблицы делим на элементы того же знака (⁺/₊; ^—/_) ведущего столбца. Результаты заносим в отдельный столбец δi, которые будут всегда положительные. Строка симплексной таблицы, соответствующая минимальному значению δi является ведущей. Она определяет переменную x_i которая выйдет из базиса и станет свободной. Элемент симплексной таблицы, находящийся на пересечении ведущих столбца и строки, называют разрешающим и выделяют кружком.

Построение нового опорного плана.

Переход к новому плану осуществляется пересчетом симплексной таблицы методом Жордана — Гаусса. Сначала заменим переменные в базисе, т.е. вместо x_i в базис войдет переменная х_j соответствующая ведущему столбцу. Разделим все элементы ведущей строки предыдущей симплексной таблицы на разрешающий элемент и результаты деления занесем в строку следующей симплексной таблицы, соответствующую введенной в базис переменной xj.

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

При решении задачи линейного программирования на минимум целевой функции признаком оптимальности плана являются отрицательные значения всех коэффициентов индексной строки симплексной таблицы. Если в ведущем столбце все коэффициенты a_ij≤0, то функция цели F() не ограничена на множестве допустимых планов, т.е. F() → ¥ и задача не имеет решения. Если в столбце δi симплексной таблицы содержатся два или несколько одинаковых наименьших значения, то новый опорный план будет вырожденным (одна или несколько базисных переменных станут равными нулю). Для выбора ведущей строки в этом случае используют метод Креко, который заключается в следующем. Элементы строк, имеющие одинаковые наименьшие значения δi делятся на предполагаемые разрешающие элементы, а результаты заносятся в дополнительные строки. За ведущую строку выбирается та, в которой раньше встретится наименьшее частное при чтении таблицы слева направо по столбцам.

Например, таблица, содержащая три равных значения

δi = 2, имеет вид:

План	Базисные переменные	Значения базисных переменных	x₁	x₂	x₃	x₄	x₅	х₆	х₇	δi
II	х₄	4	2	3	6	1	0	0	1	4/2=2
	х₅	8	4	8	1	0	1	0	4	8/4=2
	х₆	10	5	12	—1	1	0	1	5	10/5=2

Допустим, разрешающим столбцом является x₁, который вводится в новый план, тогда разрешающим элементом может быть: 2,4 или 5.

По указанному правилу, получится таблица:

Значения базисных переменных	x₁	x₂	x₃	x₄	x₅	х₆	х₇
2	1	1,5	3	0,5	0	0	1
2	1	2	0,25	0	0,25	0	1
2	1	2,4	-0,2	0,2	0	0,2	1

Сравниваем последовательно слева направо полученные частные по столбцам. В первом и втором столбцах все частные одинаковы, а в третьем столбце наименьшее частное 1,5 в первой строке. Следовательно, эта строка и будет разрешающей с разрешающим элементом 2. Если в оптимальный план вошла дополнительная переменная x_n₊₁, то при реализации такого плана имеются недоиспользованные ресурсы i-го вида в количестве, полученном в столбце свободных членов таблицы. Если в индексной строке симплексной таблицы оптимального плана находится нуль, принадлежащий свободной переменной, не вошедшей в базис, а в столбце, содержащем этот нуль, имеется хотя бы один положительный элемент, то задача имеет множество оптимальных планов. Свободную переменную, соответствующую указанному столбцу, можно внести в базис, выполнив соответствующие этапы алгоритма. В результате будет получен второй оптимальный план с другим набором базисных переменных.