Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Симплекс-метод решения задачи линейного программирования с множеством переменных




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

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

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

Базовую модель, с которой мы будем работать в дальнейшем, формально? можно представить следующим образом:

Максимизировать Z = с1х1 + с2x2 + ... + сnхn.

Здесь сi - константы. Данная функция максимизируется в условиях системы m линейных ограничений:

a11х1 + а12x2 + а13x3 + … + a1nxn b1

a21х1 + а22x2 + а23x3 + … + a2nxn b2

a31х1 + а32x2 + а33x3 + … + a3nxn b3

. . . .

am1х1 + аm2x2 + аm3x3 + … + amnxn bm , xi 0

 

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



Пример: Некоторая фирма производит два вида продуктов Х и Y в условиях ограничений на три вида сырья: RM1, RM2 и RM3. Целью фирмы является выбор такого ассортиментного набора, при котором достигается максимум прибыли в неделю. Задача линейного программирования имеет вид:

1. Выпускается х единиц продукта Х в неделю и у единиц продукта Y в неделю.

2. Максимизируется еженедельная прибыль Р (ф. ст.), где Р = 2 х + у.

3. Максимизация осуществляется в условиях ограничений:

RM1: 3 х 27 кг в неделю

RM2: 2 у 30 кг в неделю

RM3: х + у 20 кг в неделю

х, у 0.

4. Найти оптимальный ассортиментный набор и максимальную прибыль за неделю. Определить свободный запас каждого ресурса.

Решение

Графический метод. В каждое ограничение модели вводятся остаточные переменные si Максимизировать: Р = 2 х + у (ф. ст. в неделю) при ограничениях:

RM1: 3 х + s1 = 27 кг в неделю;

RM2: 2 у + s2 = 30 кг в неделю;

RM3: х + у + s3 = 20 кг в неделю;

х, у, s 0.

Изобразим систему ограничений графически (см. рис. 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 кг в неделю.


.

mylektsii.ru - Мои Лекции - 2015-2020 год. (0.009 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал