Реферат: Графический метод и симплекс-метод решения задач линейного программирования
p1 : 1x1 +2x2 =6
Построим эту прямую на плоскости с координатными осями x1 и x2 . Для проведения прямой достаточно знать две ее точки. Проще всего найти точки пересечения прямой с осями координат. Полагая x1 = 0 , из уравнения прямой получим x2 = 3 , а при x2 = 0 найдем x1 = 6 . Таким образом прямая p1 пройдет через точки (0,3) и (6,0) . Чтобы определить, по какую сторону от прямой расположена искомая полуплоскость, достаточно подставить в неравенство (1.2) координаты любой точки плоскости. Если прямая не проходит через начало координат, то удобнее всего взять точку (0, 0) . Очевидно, что в этой точке неравенство (1.2) строго выполняется (1* 0 + 2* 0 < 6) , значит полуплоскость, определяемая этим неравенством, лежит ниже прямой p1 , включая в себя начало координат. Искомую полуплоскость отметим штриховкой (рис.1.1 ).
Аналогично построим полуплоскость, задаваемую неравенством (1.3). Для этого нанесем на координатную плоскость граничную прямую
p2 : 2x1 +x2 =8 ,
найдя ее точки пересечения с осями координат: (0,8) и (4,0) .
Подставляя координаты точки (0,0) в неравенство (2.3), видим, что начало координат лежит в искомой полуплоскости (2* 0 + 1* 0 < 8) , значит все точки, удовлетворяющие неравенству (2.3), расположены левее прямой p2 . Отметим эту область штриховкой (рис.1.1 ).
Точки, задаваемые ограничением (4 ), находятся ниже прямой
p3 : -x1 +x2 =1,
проходящей через точки (0, 1) и (-1, 0) .
Наконец, условия неотрицательности: x1 ³ 0, x2 ³0 задают все точки первой четверти, что также отметим штриховкой.
Выделяя теперь точки плоскости, удовлетворяющие всем ограничениям задачи (1.1)-(1.5), то есть расположенные одновременно во всех заштрихованных полуплоскостях, получаем множество планов X . Оно представляет собой многоугольник (в данной задаче - пятиугольник). Его стороны лежат на прямых, уравнения которых получаются из исходной системы неравенств (1.2)-(1.5) заменой знаков неравенств на строгие равенства.
Рис. 1.1
Для графического представления целевой функции введем понятие линии уровня (изолинии функции).
Определение. Линией уровня (изолинией) функции f(x) называется множество точек x = (x1, x2 ) , в которых она принимает одно и то же постоянное значение f(x) = h , где h - некоторое число. Для линейной функции двух переменных f(x) = c1 x1 + c2 x2 линия уровня, соответствующая числу h , будет представлять прямую с уравнением
c1 x1 + c2 x2 = h (1.6)
При изменении числа h будем получать семейство линий уровня (параллельных прямых) с одним и тем же направляющим вектором c = =(c1 , c2) , перпендикулярным всем прямым. Известно, что вектор c = (c1 , c2 ) для линейной функции f(x) = c1 x1 +c2 x2 указывает направление ее возрастания. Геометрически это означает, что при параллельном перемещении прямой (1.6) в направлении целевого вектора c значение целевой функции возрастает.
Построим линии уровня целевой функции f(x) = 3x1 + 2 x2 в нашей задаче. Их уравнения будут иметь вид 3x1 + 2 x2 = h. Они задают семейство параллельных прямых, зависящих от параметра h . Все прямые перпендикулярны целевому вектору c = (3, 2) , составленному из коэффициентов целевой функции, поэтому для построения семейства линий уровня целевой функции достаточно построить ее целевой вектор, и провести несколько прямых, перпендикулярных этому вектору. Линии уровня будем проводить на множестве планов X , помня при этом, что при параллельном перемещении прямых в направлении целевого вектора c = (3, 2) значение функции f(x)= 3x1 + 2x2 будет возрастать. Поскольку в задаче оптимальный план должен доставлять целевой функции максимально возможное значение, то для решения задачи графически надо среди всех точек x = (x1, x2 ) множества планов X найти такую точку x* = (x1 *, x2 *) , через которую пройдет последняя линия уровня в направлении целевого вектора c = (3,2) . Из рисунка 1.2 видно, что искомой точкой будет точка, лежащая в вершине множества X , образованной пересечением прямых p1 и p2 . Решая систему уравнений, описывающих эти прямые найдем оптимальный план x1 * = 3 1 /3 , x2 * = 1 1 /3 . При этом максимальное значение целевой функции будет равно f(x*) = 12 2 /3 . Таким образом, ежесуточно фабрика должна производить 3 1 /3 тонн краски INT и 1 1 /3 тонн краски EXT , получая при этом доход 12 2 /3 тыс. долларов.
x1 + 2 x2 = 6,
2 x1 + x2 = 8,
Пример 1.2. Лечебное предприятие закупает два вида мультивитаминных комплексов «Здоровье» и «Долголетие» с содержанием витаминов трех видов. Количество единиц этих витаминов в одном грамме мультикомплексов, необходимая их норма при профилактическом приеме и стоимость одного грамма комплексов «Здоровье» и «Долголетие» отражены в таблице
| Витамины | Кол-во единиц витаминов в 1 гр. комплекса | Норма единиц витаминов | |
| Здоровье | Долголетие | ||
| V 1 | 3 | 1 | 9 |
| V 2 | 1 | 2 | 8 |
| V 3 | 1 | 6 | 12 |
| Стоимость 1 грамма комплекса | 5 руб. | 4 руб. | |
Сколько граммов мультивитаминных комплексов каждого вида требуется на один профилактический прием, чтобы были получены все витамины не меньше требуемой нормы, и при этом их суммарная стоимость была минимальной.
Составим математическую модель задачи. Для этого введем переменные: x1 – количество комплекса «Здоровье» (гр.) , x2 – количество комплекса «Долголетие» (гр.) , необходимое для профилактического приема. Целевая функция выражает суммарную стоимость витаминных комплексов, которая должна быть минимально возможной
f( x)= 5 x1 + 4 x2 ® min (1.7)
Ограничения, описывающие выполнение норм по витаминам, имеют вид:
По витамину V1 : 3x1 + x2 ³9 , (1.8)
По витамину V2 : x1 + 2x2 ³ 8, (1.9)
По витамину V3 : x1 + 6x2 ³12 . (1.10)
При этом переменные должны быть неотрицательны: xj ³0, j = 1, 2.