Слайд 1Графическое решение задач линейного программирования
Слайд 2 f(X) = 2x1-5x2→max Целевая функция:
Ограничения:
3x1 + 2x2 ≥ 6 (1)
X1
≤ 4 (2)
X2 ≤ 4 (3)
X1 + x2 ≤ 6 (4)
X1 ≥ 0
, x2 ≥ 0 (5-6)
Математическая модель задачи.
Слайд 3Построение области допустимых планов
1) Построение границы 1:
3x1 + 2x2
= 6 – прямая линия
Решение неравенства 1:
Подставляем точку О(0;0)
в неравенство: 3*0 + 2*0 ≥ 6-неверно, следовательно точка О не принадлежит области допустимых планов.
Слайд 52) Построение границы 2: х1 = 4 –прямая линия
Решение неравенства
2: 0 ≤ 4 – верно
3) Построение границы 3: х2
= 4 – прямая линия
Решение неравенства 3: 0 ≤ 4 – верно
4)Построение границы 4: х1 + x2 = 6 – прямая линия
Решение неравенства 4: 0 + 0 ≤ 6 - верно
Слайд 7II. Оптимизация целевой функции:
1) Построение градиента:
g = (2; -5) –
(коэффициенты при Х в целевой функции)
Градиент - вектор, направление которого
показывает максимальную скорость роста этой функции.
Слайд 92) Построение линии уровня целевой функции:
Линия, на которой функция принимает
одно и то же значение. (нулевая функция)
f (X) = 0
=> 2x1-5x2 = 0
Слайд 11Передвигаем линию уровня в сторону градиента (если задача на max),
при этом значение целевой функции возрастает. Если задача на min,
то - в сторону, противоположную градиенту.
Последняя точка контакта линии уровня с планом определяет оптимальный план (Х*), на котором функция имеет max или min значение.
Слайд 13Оптимальный план Х* совпадает с
точкой D.
Чтобы вычислить координаты этого
плана нужно найти точки пересечения тех границ, где он находиться.
Х*
(2) ∩ (5)
Х1 = 4
Х2 = 0
Слайд 14Оптимальный план Х* = (4; 0)
Максимальное значение функции:
max f(X) =
f(X*) = 2*4 – 5*0 = 8
Слайд 15Непустое множество планов основной задачи линейного программирования образует выпуклый многогранник.
Каждая вершина этого многогранника определяет опорный план. В одной из
вершин многогранника решений (т. е. для одного из опорных планов) значение целевой функции является максимальным (при условии, что функция ограничена сверху на множестве планов). Если максимальное значение функция принимает более чем в одной вершине, то это же значение она принимает в любой точке, являющейся выпуклой линейной комбинацией данных вершин.
Слайд 16Стороны этого многоугольника лежат на прямых, уравнения которых получаются из
исходной системы ограничений заменой знаков неравенств на знаки точных равенств.
Таким
образом, исходная задача линейного программирования состоит в нахождении такой точки многоугольника решений, в которой целевая функция F принимает максимальное значение. Эта точка существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху. При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение. Для определения данной вершины построим линию уровня, проходящую через многоугольник решений, и будем передвигать ее в направлении вектора до тех пор, пока она не пройдет через ее последнюю общую точку с многоугольником решений. Координаты указанной точки и определяют оптимальный план данной задачи.
Слайд 17при нахождении ее решения могут встретиться случаи, изображенные на рис.
1 - 4.
Рис. 1 характеризует такой случай, когда целевая функция
принимает максимальное значение в единственной точке А.
Из рис. 2 видно, что максимальное значение целевая функция принимает в любой точке отрезка АВ.
Слайд 18На рис. 3 изображен случай, когда целевая функция не ограничена
сверху на множестве допустимых решений.
На рис. 4 – случай, когда
система ограничений задачи несовместна.
нахождение минимального значения линейной функции при данной системе ограничений отличается от нахождения ее максимального значения при тех же ограничениях лишь тем, что линия уровня передвигается не в направлении вектора, а в противоположном направлении.
Слайд 19Этапы графического решения задачи линейного программирования
1. Строят прямые, уравнения которых
получаются в результате замены в ограничениях знаков неравенств на знаки
точных равенств.
2. Находят полуплоскости, определяемые каждым из ограничений задачи.
3. Находят многоугольник решений.
4. Строят вектор-градиент целевой функции .
5. Строят линию уровня целевой функции , проходящую через многоугольник решений.
6. Передвигают прямую в направлении вектора , в результате чего-либо находят точку (точки), в которой целевая функция принимает максимальное значение, либо устанавливают неограниченность сверху функции на множестве планов.
7. Определяют координаты точки максимума функции и вычисляют значение целевой функции в этой точке.
Слайд 20Пример.
Для производства двух видов изделий А и В предприятие использует
три вида сырья. Нормы расхода сырья каждого вида на изготовление
единицы продукции данного вида приведены в табл. В ней же указаны прибыль от реализации одного изделия каждого вида и общее количество сырья данного вида, которое может быть использовано предприятием.
Слайд 21Учитывая, что изделия А и В могут производиться в любых
соотношениях (сбыт обеспечен), требуется составить такой план их выпуска, при
котором прибыль предприятия от реализации всех изделий является максимальной,
Математическая модель задачи: среди всех неотрицательных решений данной системы линейных неравенств требуется найти такое, при котором функция F принимает максимальное значение.
Слайд 2212х1+4х2=300
3х1+12х2=252
4х1+4х2=120
30х1+40х2=1080
Слайд 23Задача составления рациона.
При откорме каждое животное ежедневно должно получать не
менее 9 ед. питательного вещества S1, не менее 8 ед.
вещества S2 и не менее 12 ед. вещества S3. Для составления рациона используют два вида корма. Содержание количества единиц питательных веществ в 1 кг каждого вида корма и стоимость 1 кг корма приведены в таблице
Необходимо составить дневной рацион нужной питательности, причем затраты на него должны быть минимальными.
Слайд 24Решение
Для составления математической модели обозначим через х1 и х2 соответственно
количество килограммов корма 1 и 2 в дневном рационе. Принимая
во внимание значения, приведенные в таблице и условие, что дневной рацион удовлетворяет требуемой питательности только в случае, если количество единиц питательных веществ не меньше предусмотренного, получаем систему ограничений
3х1 + х2>= 9
х1 + 2х2 >= 8
х1 + 6х2 >= 12
х1>= 0, х2 >= 0.
Цель данной задачи – добиться минимальных затрат на дневной рацион, поэтому общую стоимость рациона можно выразить в виде линейной функции
Z = 4х1 + 6х2 (ед.)
Требуется найти такие х1 и х2, при которых функция Z принимает минимальное.
Слайд 25Построим многоугольник решений. Для этого в системе координат х1Ох2 на
плоскости изобразим граничные прямые
3х1 + х2 = 9 (L1)
х1
+ 2х2 = 8 (L2)
х1 + 6х2 = 12 (L3)
х1 = 0, х2 = 0.
Взяв какую-нибудь точку, например, начало координат, установим, какую полуплоскость определяет соответствующее неравенство.
В результате получим неограниченную многоугольную область с угловыми точками А, В, С, D.
Для построения прямой 4х1 + 6х2 = 0 строим радиус-вектор N = (4;6) и через точку O проводим прямую, перпендикулярную ему. Построенную прямую Z = 0 перемещаем параллельно самой себе в направлении вектора N. Из риc. следует, она впервые коснется многогранника решений и станет опорной по отношению к нему в угловой точке В. Если прямую перемещать дальше в направлении вектора N, то значения линейной функции на многограннике решений возрастут, значит, в точке В линейная функция Z принимает минимальное значение.
Точка В лежит на пересечении прямых L1 и L2. Для определения ее координат решим систему уравнений
3x1 + х2 = 9
х1 + 2х2 = 8
Имеем: х1 = 2; х2 = 3. Подставляя значения х1 и х2 в линейную функцию, получаем Zmin = 4 2 + 6 3 = 26.
Таким образом, для того, чтобы обеспечить минимум затрат (26 ед. в день), необходимо дневной рацион составить из 2 кг корма 1 и 3 кг корма 2.
Слайд 26Решите графически задачи
1
2 3
4 5
6 7 8 9 10
Ответ: F(1;2)=5