Полная версия

Главная arrow Информатика arrow Интегрированные автоматизированные системы управления химическими производствами и предприятиями

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Графическое решение задачи линейного программирования

Линейное уравнение описывает множество точек, лежащих на одной прямой. Линейное неравенство описывает некоторую область на плоскости. Например, неравенство х < 7 означает, что

x принимает значения, которые либо меньше 7, либо равны 7. Графически эту ситуацию можно проиллюстрировать следующим образом. Проведем прямую х = 7. Обратимся к графику, изображенному на рис. 6.4 слева. Данная прямая разделяет плоскость на три множества точек: точки, для которых х = 7, т. е. точки, лежащие на самой прямой; точки, для которых х < 7, область слева от прямой; и точки, для которых х > 7, т. е. точки, принадлежащие области, лежащей справа от прямой. Последнее множество нас не интересует. Область, не подлежащую рассмотрению, обычно принято заштриховывать.

Предположим, что х1 + х2 < 10. Какую часть плоскости описывает данное неравенство? Схема поиска ответа на этот вопрос аналогична схеме, используемой в предыдущем примере. Во-первых, проведем прямую хг + х2 < 10. Обратимся к графику, изображенному на рис. 6.5 слева. Как и в предыдущем примере, проведенная прямая разделяет плоскость на три множества точек: точки, для которых х1 + х2 - 10, принадлежащие прямой; точки, для которых

xi + х2 < Ю принадлежащие области, лежащей ниже прямой; и точки, для которых х12 > 10 принадлежащие области, лежащей выше указанной прямой (рис. 6.5 справа).

Графическое изображение неравенствах^ 7

Рис. 6.4. Графическое изображение неравенствах^ 7

Графическое изображение неравенства х,+х< 10

Рис. 6.5. Графическое изображение неравенства х,+х2< 10

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

Применим теперь данную процедуру к задаче линейного программирования, сформулированной в примере 6.1.

Пример 6.2

Допустимые области для каждого из ограничений задачи показаны на рис. 6.6.

Ограничение на фонд рабочего времени

Рис. 6.6. Ограничение на фонд рабочего времени: х1 + 2 < 4000 чел.ч в неделю

Ограничение на производственные мощности

Рис. 6.7. Ограничение на производственные мощности:

< 2250 деталей в неделю и х2 < 1750 деталей в неделю

Ограничение на металлические стержни

Рис. 6.8. Ограничение на металлические стержни: 2х, + 5х2 < 10 000 кг в неделю

Ограничение на листовой металл

Рис. 6.9. Ограничение на листовой металл: 5*!+ 2*2 <10 000 кг в неделю

Ограничение на постоянные заказы и неотрицательность

Рис. 6.10. Ограничение на постоянные заказы и неотрицательность: х > 600 деталей в неделю и xv х2 > О

Ограничение на профсоюзное соглашение

Рис. 6.11. Ограничение на профсоюзное соглашение: х,+ х2 > 1500 деталей в неделю

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

Задача линейного программирования для выпуска деталей типа А и В к автомобилям в неделю

Рис. 6.12. Задача линейного программирования для выпуска деталей типа А и В к автомобилям в неделю

Необходимо определить оптимальный ассортиментный набор, максимизирующий общий доход завода за неделю. Целевая функция (критерий оптимизации) задачи имеет вид:

Чтобы построить линию уровня этой функции для типичного значения, выберем принадлежащую допустимому множеству точку с координатами X] = х2 = 1000. Для этого ассортиментного набора общий доход за неделю составляет:

В качестве контрольной линии уровня будем использовать прямую

Эта прямая проходит также через точку с координатами хг = 0, х2 = 1,75, на рис. 6.12 она изображена пунктирной линией. Движение параллельно прямой в направлении увеличения дохода приводит нас в точку Л, что является последним допустимым решением.

Лимитирующими являются ограничения на:

фонд рабочего времени: хг + 2х2 < 4000 ч. в неделю;

листовой металл: 5хх + 2 < 10 000 кг в неделю.

Решив соответствующую систему уравнений, получим:

следовательно, хг = 1500 и после подстановки значения хг в систему значение х2 = 1250.

Оптимальным ассортиментным набором является выпуск 1500 деталей типа А и 1250 деталей типа В в неделю. Таким образом, максимальный доход за неделю составит:

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

Нетрудно установить, что значения остаточных переменных в ограничениях на производственные мощности равны 750 для деталей типа А и 500 для деталей типа В, а именно:

Остаточная переменная ограничения на металлические стержни:

следовательно, s4 = 750 кг в неделю.

Избыточная переменная ограничения на постоянные заказы:

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

следовательно, s7 =1250 деталей в неделю сверх минимального количества деталей, оговоренного в профсоюзном соглашении.

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

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

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

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

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>