Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Геометрический метод решения задачи линейного программирования
|
|
Постановка задачи линейного программирования
Дана система m линейных уравнений и неравенств с n переменными:
a 
x 
+a 
x 
…+a 
x 
b ,
a 
x 
a 
x 
+…+a 
x b 
……………………………………….
a 
x +a 
x +…+a 
x b 
,
a 
x +a 
x +…+a 
x =b 
, (1)
a 
x +a 
x +…+a 
x =b 
,
………………………………………………….
a 
x +a 
x +…+a 
x =b 
,
и линейная (целевая) функция
F=c x 
+c x +…+c x . (2)
Необходимо найти такое решение системы (1) X=(x , x , …, x 
,.., x ), где
x 
0 (j=1, 2, …, l; l n), (3)
при котором линейная функция (2) принимает оптимальное (т.е. максимальное или минимальное) значение.
Система (1) называется системой ограничений, а функция F – линейной функцией, линейной формой, целевой функцией или функцией цели.
Оптимальным решением (или оптимальным планом) задачи линейного программирования называется решение X=(x , x , …, x ) системы ограничений (1), удовлетворяющее условию (3), при котором линейная функция (2) принимает экстремальное (максимальное или минимальное) значение.
При условии, что m< n, система ограничений (1) имеет множество решений. Решения задачи, удовлетворяющие системе (1) и дополнительным условиям (3), называются допустимыми.
Геометрический метод решения задачи линейного программирования основан на использовании теоремы.
Множество решений совместной системы m линейных неравенств с двумя переменными является выпуклым многоугольником (или выпуклой многоугольной областью). Оптимальное решение задачи линейного программирования располагается в одной из угловых точек многоугольника решений.. Если линейная функция принимает экстремальное значение более чем в одной угловой точке, то она принимает его в любой точке, являющейся выпуклой линейной комбинацией этих точек, т.е располагается на отрезке, соединяющем точки..
Многоугольник допустимых решений задачи может быть построен геометрическим методом (см. пример решения). Оптимальное решение выбирается либо путем перебора угловых точек, либо с использованием понятия линии уровня. Линией уровня линейной функции F называется линия, вдоль которой эта функция принимает одно и то же фиксированное значение F=a..
Пример
Решить задачу линейного программирования геометрическим методом.
|
|