Математическая модель процесса планирования отгрузки

РефератПомощь в написанииУзнать стоимостьмоей работы

Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно — основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробно-линейное программирование. Задача математического моделирования… Читать ещё >

Математическая модель процесса планирования отгрузки (реферат, курсовая, диплом, контрольная)

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

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

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

Термин «программирование» нужно понимать в смысле «планирования». Он был предложен в середине 1940;х годов Джорджем Данцигом, одним из основателей линейного программирования, еще до того, как компьютеры были использованы для решения линейных задач оптимизации.

Нужно определить максимум линейной целевой функции (линейной формы).

при условиях.

Математическая модель процесса планирования отгрузки.

при .

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

Такую задачу называют «основной» или «стандартной» в линейном программировании.

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

Задача линейного целочисленного программирования формируется следующим образом: найти такое решение (план) X = (x1,x2,…, xn), при котором линейная функция.

(1).

принимает максимальное или минимальное значение при ограничениях.

=bi, i=1, 2…, m. (2).

хj 0, j=1, 2,…, n.(3).

xj — целые числа (4).

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

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

Задачи линейного программирования имеет следующий вид:

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

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

Некоторое предприятие производит n типов продукции, затрачивая при этом m типов ресурсов. Известны следующие параметры: aij — количество i-го ресурса, необходимое для производства единичного количества j-й продукции; aij0 (i=1,…, m; j=1,…, n);

bi-запас i-го ресурса на предприятии, bi>0;

cj-цена единичного количества j-й продукции, cj>0.

Предполагается, что затраты ресурсов растут прямо пропорционально объему производства. Пусть xj — планируемый объем производства j-й продукции. Тогда допустимым является только такой набор производимой продукции x=(x1,x2,…, xn), при котором суммарные затраты каждого вида i-го ресурса не превосходят его запаса:

(1).

Кроме того, имеем следующее ограничение: xj0; j=1,…, n. (2).

Стоимость набора продукции x выражается величиной: (3).

Задача планирования отгрузки в моем случае ставится следующим образом: среди всех векторов x, удовлетворяющим ограничениям (1), (2), найти такой, при котором величина (3) принимает наибольшее значение.

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

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

Таблица 2.1 — Симплекс-таблица.

#№.

Базисные столбцы.

Bs.

Базисное решение Xs.

C1.

C2.

…

Cm.

Cm+1.

…

Ck.

…

Cn.

A1.

A2.

…

Am.

Am+1.

…

Ak.

…

An.

A1.

…

A2.

…

Al.

…

Am.

…

Оценки.

…

Шаг 2. Вычисление характеристических разностей (оценок) по формулам и запись оценок вю строку симплекс-таблицы.

Шаг 3. Вычисление оценки, удовлетворяющей условию:

Если все, то в соответствии с выполнением критерия оптимальности вектор — оптимальное решение, и далее следует перейти к шагу 9, иначе — к шагу 4.

Шаг 4. Вычисление нового базисного решения из условия:

Шаг 5. Вычисление компонент нового базисного решения по формулам:

Шаг 6. Вычисление элементов новой симплекс-таблицы дляй итерации метода по формулам:

Шаг 7. Корректировка симплекс-таблицы с учетом изменений коэффициентов целевой функции, соответствующих новому базисному решению. Формируем таблицу 2.2.

Таблица 2.2. — Симплекс-таблица.

#№.

Базисные столбцы.

Базисное решение Xs.

C1.

C2.

…

Cm.

m+1.

…

Ck.

…

Cn.

A1.

A2.

…

Am.

Am+1.

…

Ak.

…

An.

A1.

…

A2.

…

Al.

…

Am.

…

Оценки.

…

Шаг 8. Переход к шагу 2.

Шаг 9. Остановка, регистрация оптимального решения.

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

Показать весь текст

Заполнить форму текущей работой