Суббота, 10.12.2016, 04:06
Главная Регистрация RSS
Вы вошли как Гость | Группа "Гости"Приветствую Вас, Гость
Поделиться
Статистика
Яндекс.Метрика
Flag Counter
Онлайн всего: 7
Гостей: 7
Пользователей: 0
» »
15:14
Решить графически задачу

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

Задача. Решить графически задачу линейного программирования, определив экстремальное значение целевой функции:

при ограничениях

Решение.

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

Построим уравнение 3x1+x2 = 9 по двум точкам.
Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 9. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 3. Соединяем точку (0;9) с (3;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 3 • 0 + 1 • 0 - 9 ≤ 0, т.е. 3x1+x2 - 9≥ 0 в полуплоскости выше прямой.
Построим уравнение x1+2x2 = 8 по двум точкам.
Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 4. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 8. Соединяем точку (0;4) с (8;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 • 0 + 2 • 0 - 8 ≤ 0, т.е. x1+2x2 - 8≥ 0 в полуплоскости выше прямой.
Построим уравнение x1+x2 = 8 по двум точкам.
Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 8. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 8. Соединяем точку (0;8) с (8;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 • 0 + 1 • 0 - 8 ≤ 0, т.е. x1+x2 - 8≤ 0 в полуплоскости ниже прямой.

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

Проверить правильность построения графиков функций можно с помощью калькулятора

 

Рассмотрим целевую функцию задачи F = 4x1+6x2 → min.
Построим прямую, отвечающую значению функции F = 0: F = 4x1+6x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление минимизации F(X). Начало вектора – точка (0; 0), конец – точка (4; 6). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Прямая F(x) = 4x1+6x2  пересекает область в точке B. Так как точка B получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:
3x1+x2=9
x1+2x2=8

Решив систему уравнений, получим: x1 = 2, x2 = 3
Откуда найдем минимальное значение целевой функции:
F(X) = 4*2 + 6*3 = 26

Категория: Линейное программирование | Просмотров: 2142 | Добавил: Admin | Теги: симплекс метод, транспортная задача, графический метод, система неравенств | Рейтинг: 0.0/0



Всего комментариев: 0
avatar
  .