![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Симплекс-метод решения задачи линейного программирования с множеством переменных
Если задача линейного программирования содержит более двух переменных, то ее решение требует применения некоторого алгебраического метода. Принцип, лежащий в основе решения задачи с множеством переменных, достаточно прост. Предполагается, что оптимальному решению соответствует одна из крайних точек допустимого множества. Следовательно, необходимо провести оценку значений целевой функции во всех крайних точках допустимого множества и выбрать ту из них, в которой достигается оптимальное значение целевой функции. Нами используются методы матричной алгебры и такой алгоритм перехода от одной крайней точки допустимого множества к другой, при котором переход осуществляется только в случае, когда значение целевой функции улучшается. Если окажется, что некоторое базисное решение улучшить уже нельзя, то оно является оптимальным планом задачи. Этот алгоритм получил название симплекс-метода. В обычном симплекс-методе принимается предпосылка о максимизации целевой функции задачи линейного программирования в условиях системы ограничений со знаком " Симплекс-метод можно применять также и в решении задач минимизации, и в решении задач, система ограничений которых содержит ограничения со знаком " Базовую модель, с которой мы будем работать в дальнейшем, формально? можно представить следующим образом: Максимизировать Z = с1х1 + с2x2 +... + сnхn. Здесь сi - константы. Данная функция максимизируется в условиях системы m линейных ограничений: a11х1 + а12x2 + а13x3 + … + a1nxn a21х1 + а22x2 + а23x3 + … + a2nxn a31х1 + а32x2 + а33x3 + … + a3nxn .... am1х1 + аm2x2 + аm3x3 + … + amnxn
Данная система содержит n переменных и m ограничений. Первая цифра двойных индексов коэффициентов в левой части системы ограничений соответствует номеру ограничения, вторая — номеру переменной. Например, a32 принадлежит ограничению 3 и является коэффициентом при переменной х2. Проиллюстрируем применение симплекс-метода на примере простой задачи с двумя переменными, решение которой было получено нами ранее с помощью графического метода. Этот прием позволит нам сравнить решение, полученное графическим и алгебраическим методами. Пример: Некоторая фирма производит два вида продуктов Х и Y в условиях ограничений на три вида сырья: RM1, RM2 и RM3. Целью фирмы является выбор такого ассортиментного набора, при котором достигается максимум прибыли в неделю. Задача линейного программирования имеет вид: 1. Выпускается х единиц продукта Х в неделю и у единиц продукта Y в неделю. 2. Максимизируется еженедельная прибыль Р (ф. ст.), где Р = 2 х + у. 3. Максимизация осуществляется в условиях ограничений: RM1: 3 х RM2: 2 у RM3: х + у х, у 4. Найти оптимальный ассортиментный набор и максимальную прибыль за неделю. Определить свободный запас каждого ресурса. Решение Графический метод. В каждое ограничение модели вводятся остаточные переменные si Максимизировать: Р = 2 х + у (ф. ст. в неделю) при ограничениях: RM1: 3 х + s1 = 27 кг в неделю; RM2: 2 у + s2 = 30 кг в неделю; RM3: х + у + s3 = 20 кг в неделю; х, у, s Изобразим систему ограничений графически (см. рис. 3.1.) Рис. 3.1. Задача линейного программирования для объемов выпуска продуктов X и Y в неделю Точка с координатами х = 5, у = 5 принадлежит допустимому множеству. Еженедельная прибыль в этой точке составит: Р=2*5+5=15 ф.ст.в неделю. В качестве типичной линии уровня прибыли выберем прямую: 15 = 2 х + у (ф. ст. в неделю). Точка с координатами х = 0, у = 15 также принадлежит этой прямой. Линия уровня изображена на приведенном выше графике пунктиром. Если осуществлять перемещение линии уровня параллельно ее начальному положению (отмеченному пунктиром), то легко можно убедиться, что оптимум находится в крайней точке А. Эта точка лежит на пересечении линий ограничений RM1 и RM3. Решение системы этих уравнений дает следующие результаты: 3 х = 27, следовательно, х = 9. Подставив это значение во второе уравнение системы, получим: х + у = 20, следовательно, у = 11. Оптимальным ассортиментным набором является производство 9 единиц продукта Х и 11 единиц продукта Y в неделю. Таким образом, максимальная прибыль, получаемая за неделю, составит: Р max = 2 * 9 + 11 = 29 ф. ст. в неделю. Сырье типа 1 и 3 используется полностью, однако существует свободный запас сырья типа 2, т.е. 2 х 11 +s2 =30, следовательно, s= 8 кг в неделю.
|