![]() |
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Графический метод решения задачи линейного программирования
Сразу отметим, что существенным недостатком графического метода является возможность его применения только в задачах с двумя переменными. Экономико-математическая модель ЗЛП включает неравенства и их системы. Геометрическую интерпретацию решений неравенств, их систем и в целом ЗЛП дают следующие теоремы. Теорема 1 [1]. Множество решений линейного неравенства Теорема 2. Множество решений совместной системы линейных неравенств
является выпуклым многоугольником(или выпуклой многоугольной областью). Замечание. Для решения систем вида (1) необходимо решить каждое неравенство в отдельности, а затем найти пересечение полученных полуплоскостей. Теорема 3. Множество всех допустимых решений совместной системы m линейных уравнений с n переменными ( Теорема 4. Если ЗЛП имеет оптимальное решение, то целевая функция достигает его в одной из угловых точек (вершин) многоугольника (многогранника) решений. Если целевая функция достигает оптимума более, чем в одной угловой точке, то она его достигает также в любой точке, являющейся их линейной комбинацией (стороны многоугольника или многогранника). Графический метод решения ЗЛП включает три этапа: 1. Определение области допустимых решений (ОДР) задачи. 2. Определение оптимальных точек (точки максимума и/или точки минимума). 3. Вычисление оптимальных значений целевой функции в оптимальных точках. Пример. Для изготовления двух видов продукции
Требуется найти такой план производства продукции, при котором прибыль от ее реализации будет максимальной. Решение: Оптимизационная ЭММ задачи:
Графическое решение: 1. Определение области допустимых решений (ОДР) задачи Этот этап реализуется в соответствии с теоремами 1, 2 и замечанием к ней. При этом искомая ОДР будет находиться только в первой четверти декартовой системы координат, т.к. в модели задачи есть прямые ограничения Решение 1-го неравенства Строим прямую
Для выбора нужной полуплоскости координаты любой точки подставляем в неравенство: если неравенство верно, решением неравенства будет полуплоскость, содержащая эту точку, если неверно – решением будет другая полуплоскость. Для удобства расчетов подставляют координаты начала координат – точки О (0, 0):
Аналогично решаем все остальные неравенства. Решение 2-го неравенства
Решение 3-го неравенства
Решение 4-го неравенства
ОДР задачи – это находящееся в первой четверти пересечение всех полученных полуплоскостей, т.е. выпуклый шестиугольник ОАВСDE (рис. 1).
Рисунок 1. Графическое решение задачи 2. Определение оптимальных точек (точки максимума и точки минимума) задачи В соответствии с теоремой 4 оптимальные точки ЗЛП могут находиться в вершинах ОДР. Для поиска оптимальных вершин используют вектор-градиент и линию уровня целевой функции. Вектор-градиент – это вектор В нашей задаче вектор-градиент Далее строят линию уровня целевой функции. Линия уровня – это прямая, заданная уравнением В нашей задаче проведем через начало координат перпендикулярно вектору 3. Вычисление оптимального значения целевой функции Для вычисления оптимального значения целевой функции координаты оптимальной точки необходимо подставить в целевую функцию:
Экономическая интерпретация полученных результатов Предприятию выгодно производить 6 единиц продукции вида Подставив найденные значения переменных в левые части ограничений, узнаем, как использованы ресурсы при производстве продукции: Таким образом, первые два ресурса израсходованы при производстве полностью (их называют дефицитными), третий ресурс остался после производства в количестве 1 усл. ед., четвертого ресурса осталось 3 усл. ед. Ресурсы, оставшиеся после производства, называются недефицитными. Графический метод позволяет провести анализ чувствительности оптимального решения ЗЛП к изменению условий задачи. Так, изменение запасов ресурсов (правых частей ограничений) приводит к параллельному смещению соответствующих прямых, ограничивающих ОДР; изменение стоимости (или прибыли) единицы продукции означает изменение координат вектор-градиента. В результате получается новый оптимальный план и оптимальное значение целевой функции. Особые случаи графического метода: 1. Неединственность оптимального решения имеет место в случае, когда линия уровня параллельна одной из сторон многоугольника решений. Тогда оптимальными точками будут все точки этой стороны (их бесконечно много). Оптимальное значение целевой функции единственное, одинаковое для всех оптимальных точек. 2. Неограниченность целевой функции задачи: если ОДР задачи – выпуклая многоугольная область, то при смещении линии уровня в направлении вектор-градиента выхода из области достичь невозможно. В этом случае говорят, что точка максимума бесконечно удалена и Существуют и другие особые случаи графического метода, которые необходимо рассмотреть самостоятельно с использованием рекомендованной в конце учебного пособия литературы.
Популярное:
|
Последнее изменение этой страницы: 2017-03-11; Просмотров: 1204; Нарушение авторского права страницы