|
|
Графический метод решения задачи линейного программированияЗадание 2. Решить графически задачу линейного программирования.
(неравенства в системе ограничений могут содержать знаки Так как задача задана в стандартной форме (все ограничения– неравенства), то решение задачи происходит по следующим этапам: 1. Строят три прямые, уравнения которых получаются в результате замены в ограничениях задачи знаков неравенств на знаки равенств, т. е.
2. Находят полуплоскости, определяемые каждым из ограничений задачи. Для этого в первое, например, неравенство подставляют координаты любой точки, не лежащей на этой прямой. Если координаты этой точки удовлетворяют первому неравенству, то заштриховывают ту полуплоскость, где находится точка, а если нет, то противоположную относительно прямой полуплоскость. 3. Пересечение всех полуплоскостей дает область возможных решений (ОВР). 4. Из этой области выделяем область допустимых решений (ОДР), т.е. пересечение области допустимых решений и первой четверти, где 5. Строим вектор-градиент целевой функции
6. Строим линию уровня градиенту (k -константа). 7. Передвигая линию уровня в направлении вектора точку «входа» в ОДР – это точка минимума, и точку «выхода» из ОДР – это точка максимума. 8. Определяем координаты точки минимума или максимума (в зависимости от условия задачи) аналитически и вычисляем значение целевой функции Пример. Решить задачу линейного программирования графическим методом
Решение. Построим область допустимых решений. Каждое неравенство в системе ограничений заменяем на равенство. В прямоугольной декартовой системе координат
Для того чтобы построить прямую, достаточно знать координаты двух точек этой прямой. Прямые зададим таблично.
Построив прямые, определяем полуплоскости, определяемые данными неравенствами.
Поскольку третья прямая не проходит через начало координат, то подставим координаты точки О(0;0) в третье неравенство, получим Четвертое неравенство определяет полуплоскость, лежащую ниже прямой (4). Находим общую часть полуплоскостей решений, учитывая при этом условия неотрицательности. Заштрихованный многоугольник является областью допустимых решений (ОДР) (рисунок 1). Строим вектор градиент Строим линию уровня По условию задачи нужно найти максимум и минимум функции Z. Передвигая линию уровня параллельно самой себе в направлении возрастания вектора градиента, находим точку «входа» в ОДР– это точка
Следовательно, этой точке. Аналогично, находим точку «выхода» из ОДР – это точка
Следовательно, Ответ:   Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...  Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...  Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...  Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
или 
).
и 
. Таким образом, находим ОДР. Если ОДР пуста, то задача линейного программирования решений не имеет.
, равный
.
, перпендикулярно вектору
, находим
в этой точке.
строим четыре прямые
прямая параллельна оси 
, 
(верно), следовательно, первое неравенство определяет полуплоскость, лежащую ниже прямой (1).
Так как вторая прямая не проходит через начало координат, то подставив координаты точки О(0;0) во второе неравенство, получим 
, 
(верно), следовательно, второе неравенство определяет полуплоскость, лежащую выше прямой (2).
Рисунок 1
, 
(не верно), следовательно, третье неравенство определяет полуплоскость, лежащую выше прямой (3).
.
перпендикулярно вектору 
.
(см. рисунок 1). Найденная точка является точкой минимума. Найдем координаты точки 
аналитически. Эта точка является пересечением прямых (3) и 
. Решим систему:
. Вычислим значение целевой функции в
.
(см. рисунок 1). Найденная точка является точкой максимума. Найдем координаты точки 
. Вычислим значение целевой функции в этой точке. 
.
, 
.