Методы оптимизации в технико-экономических задачах
Дипломная работа - Менеджмент
Другие дипломы по предмету Менеджмент
такого анализа симплекс-таблицы, если оптимальное решение не найдено и не доказано, что задача не имеет решений, то осуществляется переход к следующей, то есть переход к новому базису.
Исходя из анализа начальной симплекс-таблицы, оптимальное решение не найдено, а целевую функцию можно уменьшить. При переходе к новому базису xl станет свободной неизвестной, а xk - новой базисной неизвестной.
Получаем следующую симплекс-таблицу:
базисные\свободныеxsxlСвободные членыxm?ms=?ms+?mk?ks?ml=?mk?kl?m0=?m0+?mk?k0xr?rs=?rs+?rk?ks?rl=?rk?kl?r0=?r0+?rk?k0xk?ks=-?kl ?ls?kl=1/?lk?k0=-?kl ?l0f(x)?fs=?fs+?fk?ks?fl=?fk?kl?f0=?f0+?fk?k0
После заполнения полученная симплекс-таблица обязательно анализируется. Исходя из результатов анализа, делается вывод или о том, что оптимальное решение найдено, тогда эта таблица является последней, или о том, что задача не имеет решений, или, возможно, что эта таблица промежуточная, то есть задача не доведена до конца. В последнем случае решение нужно продолжить, опираясь на тот же алгоритм.
Как только в строке для целевой функции не будет отрицательных коэффициентов, то делается вывод о нахождении оптимального решения.
Полученные свободные неизвестные принимаются равными нулю, новые базисные неизвестные и целевая функция становятся равными своим свободным членам.
2.2 Задание
Фирме требуется уголь с содержанием примеси фосфора не больше 0,05% и с примесью пепла не более 4,00%. Доступны 3 сорта угля A,B,C по следующим ценам (за тонну):
Сорт угляСодержание примеси фосфора, %Содержание примеси фосфора, %Цена, $A0.0632.535B0.0414.230C0.0153.748
Как из следует смешать, чтобы удовлетворить ограничения на примеси и максимизировать прибыль.
2.3 Построение математической модели задачи
экономический математический модель градиент
Экономико-математическая модель - математическое описание исследуемого экономического процесса или объекта. Эта модель выражает закономерности экономического процесса в абстрактном виде с помощью математических отношений.
Проанализируем условие задачи. Необходимо найти оптимальную смесь угля, при котором прибыль от ее реализации была бы максимальной. Исходя из этого, составим математическую модель задачи.
Обозначим за x1, x2, x3 количество изделий А, В, С соответственно, с учетом того, что требуется уголь с содержанием примеси фосфора не более 0,05% и примеси пепла не более 4,00%. Связь между сортами угля каждого вида и количеством примесей выразится в системе следующим образом:
(1.1)
По смыслу задачи переменные
1?0, x2?0, x3?0 (1.2)
Прибыль от реализации трех сортов угля будет выражена функцией:
=35x1+30x2+48x3 (1.3)
Экономико-математическая модель задачи: найти такое количество каждого сорта угля, x=(x1, x2, x3), удовлетворяющее системе (1.1) и условию (1.2), при котором функция (1.3) принимает максимальное значение:
=35x1+30x2+48x3 > max
f = -35x1-30x2-48x3 > min
2.4 Решение задачи
Решение задачи графоаналитическим методом
Для решения задачи графоаналитическим методом следует учитывать что переменных должно быть не более двух.
F=35x1+30x2 > max= -35x1-30x2 > min
ограничения:
x1?0, x2?0
Построим область допустимых значений.
Любое неравенство двух переменных делит область на два подмножества: в одном они выполняются, в другом - нет. Подмножества представляют собой полуплоскости, разделяемые прямой, которая получается, если в ограничении заменить знак неравенства на знак равенства.
Найдем градиент и антиградиент функции:
Значение функции будет уменьшатся при движении по направлению антиградиента и увеличиваться по направлению градиента.
Далее следует уловить тот момент, в котором эта линия имеет последнюю общую точку с ОДР.
Чтобы найти решение необходимо решить систему:
Оптимальное решение:
т. А(0,28;0,78)
F(0,28;0,78)=35*0,28+30*0,78=33,2
Решение задачи симплекс-методом
Для решения задачи симплекс-методом, необходимо сначала привести ее к канонической форме. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам. Введем две дополнительные переменные, в результате чего ограничения запишутся в виде системы уравнений:
x4?0, x5?0
После приведения задачи к канонической форме необходимо выбрать первоначальный базис. В качестве базисных переменных возьмем x4, x5, а оставшиеся три переменные x1, x2, x3 будут свободными неизвестными. При этом необходимо, чтобы базисные неизвестные обладали следующим свойством: если все остальные неизвестные (x1, x2, x3) принять равными нулю, то переменные, выбранные в качестве базисных, должны быть неотрицательными.
Базисные переменные нужно выразить через свободные неизвестные:
Запишем опорный план:
Целевую функцию нужно выразить через свободные неизвестные:
Так как коэффициенты перед тремя переменными в целевой функции имеют отрицательный знак, выясним до какого предела можно увеличивать свободные переменные.
Отрицательные коэффициенты стоят перед x1, x2 и х3.
Из первого уравнения следует, что х1=0,79.
Из второго уравнения следует, что x2=0,95.
Из второго уравнения следует, что x3=1,08.
Теперь посчитаем, насколько каждая переменная уменьшает целевую функцию, для чего подставим максимально допустимое значение в выражение для целевой функции, а остальны