Xreferat.com » Рефераты по информатике и программированию » Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

"Гомельский государственный университет имени Франциска Скорины"

математический факультет

кафедра ВМиП


Курсовая работа


"Оптимальное распределение неоднородных ресурсов"


Гомель 2006

Содержание


Введение

Постановка задач

Выявление основных особенностей, взаимосвязей и количественных закономерностей

Решение задачи традиционными методами

Решение задачи с использованием системы Mathcad

Заключение

Литература


Введение


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

Как известно в настоящее время широко используются следующие системы символьной математики: Maple, Matlab, Mathematica, Reduce, Derive, Theorist, Macsyma. Почему же наш выбор пал на Mathcad? На это есть несколько причин:

1) Reduce, Derive, Theorist, Macsyma были созданы для совершенно других задач. Их основное назначение это доказательство теорем алгебры (Reduce, Macsyma). Derive, Theorist морально устарели еще 5 лет назад. Matlab ориентирован на работу с матрицами. Остаются только Maple, Mathematica и Mathcad.

2) Из этих программ только Mathematica и Mathcad обладают современными средствами визуализации представления данных. И запись в системе Mathcad наиболее приближена к записи математических задач без применения компьютера.

3) Mathcad изначально создавался для численного решения математических задач. С развитем Mathcad впитал в себя только лучшее от Maple (ядро для символьных вычислений) и Matlab (библиотеку высокоскоростных алгоритмов NAG).

4) Mathcad более доступен для массового пользователя.

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


Постановка задач


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

Постановка задачи А. Для изготовления Оптимальное распределение неоднородных ресурсов видов изделий Оптимальное распределение неоднородных ресурсов необходимы ресурсы Оптимальное распределение неоднородных ресурсов видов: трудовые, материальные, финансовые и др. Известно необходимое количество отдельного Оптимальное распределение неоднородных ресурсов-го ресурса для изготовления каждого Оптимальное распределение неоднородных ресурсов-го изделия. Назовем эту величину нормой расхода Оптимальное распределение неоднородных ресурсов. Пусть определено количество каждого вида ресурса, которым предприятие располагает в данный момент, – Оптимальное распределение неоднородных ресурсов. Известна прибыль Оптимальное распределение неоднородных ресурсов, получаемая предприятием от изготовления каждого Оптимальное распределение неоднородных ресурсов-го изделия. Требуется определить, какие изделия, и в каком количестве должно изготавливать предприятие, чтобы обеспечить получение максимальной прибыли. Необходимая исходная информация представлена в табл.


Данные для задачи A

Используемые ресурсы Оптимальное распределение неоднородных ресурсов

Изготавливаемые изделия

Наличие ресурсов Оптимальное распределение неоднородных ресурсов


Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов


Трудовые 3 5 2 7 15
Материальные 4 3 3 5 9
Финансовые 5 6 4 8 30

Прибыль Оптимальное распределение неоднородных ресурсов

40 50 30 20

Постановка задачи В. Пусть в распоряжении завода железобетонных изделий (ЖБИ) имеется Оптимальное распределение неоднородных ресурсов видов сырья (песок, щебень, цемент) в объемах Оптимальное распределение неоднородных ресурсов, Требуется произвести продукцию Оптимальное распределение неоднородных ресурсов видов. Дана технологическая норма Оптимальное распределение неоднородных ресурсов. потребления отдельного Оптимальное распределение неоднородных ресурсов-го вида сырья для изготовления единицы продукции каждого Оптимальное распределение неоднородных ресурсов-го вида. Известна прибыль Оптимальное распределение неоднородных ресурсов, получаемая от выпуска единицы продукции Оптимальное распределение неоднородных ресурсов-го вида. Требуется определить, какую продукцию и в каком количестве должен производить завод ЖБИ, чтобы получить максимальную прибыль. Исходные данные представлены в табл.


Данные для задачи B

Используемые ресурсы Оптимальное распределение неоднородных ресурсов

Изготавливаемые изделия

Наличие ресурсов Оптимальное распределение неоднородных ресурсов


Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов


Песок 3 5 2 7 15
Щебень 4 3 3 5 9
Цемент 5 6 4 8 30

Прибыль Оптимальное распределение неоднородных ресурсов

40 50 30 20

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


Выявление основных особенностей, взаимосвязей и количественных закономерностей


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


Оптимальное распределение неоднородных ресурсов 7


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

В этом случае система равенств примет такой вид:


Оптимальное распределение неоднородных ресурсов 7


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

Построение математической модели. Критерий оптимизации (суммарную величину прибыли) можно тогда представить так:


Оптимальное распределение неоднородных ресурсов 7


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


Оптимальное распределение неоднородных ресурсов 7

Совокупность системы ограничений Error: Reference source not found, целевой функции Error: Reference source not found и граничных условий Error: Reference source not found образует математическую модель для нашей задачи.


Решение задачи традиционными методами


Алгоритм решения. Для решения данной задачи разработано много способов. Рассмотрим один из наиболее распространенных – симплекс-метод. Для его использования необходимо определить начальный базис, то есть такое решение, которое удовлетворяет системе равенств Error: Reference source not found. В некоторых задачах базис просматривается непосредственно, но во многих его необходимо найти.

В данной задаче базис определяется легко. Для этого требуется взять Оптимальное распределение неоднородных ресурсов неизвестных по числу уравнений в системе Error: Reference source not found, желательно наиболее редко встречающиеся в ней. В нашей совокупности уравнений (Оптимальное распределение неоднородных ресурсов) это Оптимальное распределение неоднородных ресурсов, Оптимальное распределение неоднородных ресурсов, Оптимальное распределение неоднородных ресурсов, которые и выражаем через оставшиеся неизвестные Оптимальное распределение неоднородных ресурсов, Оптимальное распределение неоднородных ресурсов, Оптимальное распределение неоднородных ресурсов, Оптимальное распределение неоднородных ресурсов.

Систему уравнений необходимо записать в таком виде:


Оптимальное распределение неоднородных ресурсов 7


Переменные, находящиеся в левой части системы уравнений, называются базисными (основными), а находящиеся справа – небазисными (неосновными). Для определения значений базисных переменных Оптимальное распределение неоднородных ресурсов, Оптимальное распределение неоднородных ресурсов, Оптимальное распределение неоднородных ресурсов необходимо приравнять к нулю небазисные Оптимальное распределение неоднородных ресурсов, Оптимальное распределение неоднородных ресурсов, Оптимальное распределение неоднородных ресурсов, Оптимальное распределение неоднородных ресурсов и подставить их в систему уравнений Error: Reference source not found. Полученное таким образом решение называется базисным. В нашей задаче оно будет выглядеть следующим образом:


Оптимальное распределение неоднородных ресурсов

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

1. Заполнение исходной симплекс-таблицы. В соответствии с полученной системой уравнений и критерием оптимизации заполняем исходную симплекс-таблицу.


Симплекс-таблица

Базисные переменные Свободные члены Коэффициенты при базисных и небазисных переменных

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

15 3

Оптимальное распределение неоднородных ресурсов

2 7 1 0 0

Оптимальное распределение неоднородных ресурсов

9 4 3 3 5 0 1 0

Оптимальное распределение неоднородных ресурсов

30 5 6 4 8 0 0 1

Оптимальное распределение неоднородных ресурсов

0 40 50 30 20 0 0 0

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

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

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

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

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

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

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

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


Вторая итерация симплекс-метода

Базисные переменные Сбободные члены Коэффициенты при базисных и небазисных переменных

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

3 3/5 1 2/5 7/5 1/5 0 0

Оптимальное распределение неоднородных ресурсов

0 11/5 0

Оптимальное распределение неоднородных ресурсов

4/5 -3/5 1 0

Оптимальное распределение неоднородных ресурсов

12 7/5 0 8/5 -2/5 -6/5 0 1

Оптимальное распределение неоднородных ресурсов

-150 10 0 10 -50 -10 0 0

Аналогичные преобразования проводим и для других строк. После этого выполняем новую итерацию. Цикл расчета начинается с этапа 2 и проводится до тех пор, пока не будет найдено оптимальное решение. Поскольку в последней строке табл. в целевой функции не все коэффициенты при небазисных переменных положительны, то решение не оптимально; следовательно, выполняется следующий итерационный цикл расчета и строится новая симплекс-таблица. В качестве вводимой в базис небазисной переменной берем Оптимальное распределение неоднородных ресурсов (можно Оптимальное распределение неоднородных ресурсов) как имеющую наибольший положительный коэффициент. Отмечаем звездочкой столбец Оптимальное распределение неоднородных ресурсов. В качестве выводимой из базиса переменной берем Оптимальное распределение неоднородных ресурсов, так как для нее частное от деления свободного члена на соответствующий коэффициент минимально. Разрешающий множитель равен 9/5. Результаты расчета представлены в табл.


Третья итерация симплекс-метода

Базисные переменные Свободные члены Коэффициенты при базисных и небазисных переменных

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

Оптимальное распределение неоднородных ресурсов

3 1/9 1 0 1/9 1/3 -2/9 0

Оптимальное распределение неоднородных ресурсов

0 11/9 0 1 4/9 -3/9 5/9 0

Оптимальное распределение неоднородных ресурсов

12 -5/9 0 0 -10/9 -2/3 -8/9 1

Оптимальное распределение неоднородных ресурсов

-150 -20/9 0 0 -490/9 -20/3 -50/9 0

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


Оптимальное распределение неоднородных ресурсов


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


Решение задачи с использованием системы Mathcad


Введем сначала поясняющий текст в рабочем листе. Для этого разместим курсор (визир – красный крестик) в месте

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

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

Похожие рефераты: