Линейное программирование

Линейное программирование

Задачей линейного программирования (ЗЛП) называется  задача отыскания экстремума (максимума или минимума)  линейной функции от нескольких переменных при линейных  ограничениях на эти переменные. )  2 x , xxf ( 1 1   127 x x 1    7 83 x  1   ,0 0 x 1 2 x x 2 2 2 5 x 2  max целевая функция система  ограничений

Транспортная задача 380т 220т 320т 200т 280т

Транспортная задача Стоимости перевозок        С пл. Завод №1 №2 №1 №2 №3 2 4 4 5 6 3

Транспортная задача Завод №1 x y 320т 320­x­y Стройплощадки №1 №2 №3 220т 200т 280т Завод №2 280­y 200­x x+y­100 380т План перевозок С.пл. зав. №1 №2 №1 x №2 y 200­x 280­y №3 320­x­y x+y­100 Завод №1Завод №2№1№2№3

Математическая модель Стоимость перевозок С.пл. зав. №1 №2 №1 №2 №3 2 4 4 5 6 3 С.пл. зав. №1 №2 План перевозок №3 №2 №1 x y 200­x 280­y 320­x­y x+y­100 Стоимость запланированных перевозок f(x,y)= 2x + 4y + 6(320­x­y) + 4(200­x) + 5(280­y) + 3(x+y­100) = = 3820 – 5x – 4y

Математическая модель f(x,y) = 3820 – 5x – 4y   min→ Целевая функция       x 320 200   yx 0  x 0  y 0 280   x y 0 100  y ,0  0 Система ограничений Ограничения  неотрицательности

Планирование производства Запас  ресурса 24 12 8 4 3 1 4 6 2 1 5 x – число выпускаемых  табуреток y – число выпускаемых  стульев Ресурс1 Ресурс2 Ресурс3 Прибыл ь Суммарная прибыль от реализации всей продукции f(x,y) = 4x + 5x  → max Цель задачи – максимизация прибыли

Планирование производства Расход ресурса ≤ Запас ресурса Запас  ресурса 24 12 8 4x + +3x +x 6y ≤ 2y ≤ y ≤ 24 12 8 Ресурс1 Ресурс2 Ресурс3 Прибыл ь 4 3 1 4 6 2 1 5 Расход ресурсаЗапас ресурса

Математическая модель f(x,y) = 4x + 5y  →  max Целевая функция 24 12 6  y x 4  x y 2  y 8 3 x Система ограничений x  y ,0  0 Ограничения  неотрицательности

Составление оптимального рациона Предположим, что в дневной рацион животных должны входить  питательные вещества двух видов в количестве, заданном в  таблице. Имеется возможность составлять рацион из кормов двух  видов, для которых задано содержание питательных веществ в  единице корма и цена одной единицы каждого из видов кормов.  При удовлетворении условий по необходимому содержанию  питательных веществ в данном рационе требуется достичь его  минимальной стоимости. Корм1 Корм2 Пит. в­во1 Пит. в­во2 Цена корма 2 6 5 1 4 2 Пит. вещ­ в в  рац. 12 30

Математическая модель min  2 y ,( yxf  2 x  x 6   x 5 x  12  30 y  ,0 0 ) y 4 y

Составить математическую модель На  фабрике  для  производства  двух  видов  продукции  используются  три  вида  сырья.  Оно  имеется  на  фабрике  в  следующих  количествах: 13  единиц вида А,  9  единиц вида  В  и  8  единиц  вида  С.  На  производство  первого  вида  продукции  надо  израсходовать  (2;  0;  2)  единиц  указанных  видов сырья, а для второго вида продукции эти показатели  равны  (2;  3;  0).  Прибыль,  получаемая  фабрикой  от  реализации  первого  вида  продукции,  равна  3  условным  единицам,  а  от  реализации  единицы  продукции  второго  вида  единицам.  Составить  математическую модель работы фабрики, чтобы обеспечить  наибольшую прибыль. таким  же  равна  4

Математическая модель max y 4  y yxf ,(  2 x  y 3   x 2   x ) 3 x  13 2  9  8 y ,0  0

Составьте математическую модель На  животноводческой  ферме  производится  откорм  скота.  Пусть  известно,  что  каждому  животному  надо  ежедневно  выдать не менее 6 единиц вещества А, 8 единиц вещества В  и  12  единиц  вещества  С  (этими  веществами  могут  быть,  например, белки, жиры и углеводы). Для откорма животных  можно  закупить  два  вида  кормов  (например,  жмых  и  комбикорм).  Единица  веса  первого  корма  содержит  21  единицу  вещества  А,  2  единицы  вещества  В  и  4  единицы  вещества С, а стоимость ее равна 3рублям. Для второго вида  кормов  соответствующие  цифры  равны  3;  2;  2  и  2рублям.  Составьте  математическую  модель  процесса,  при  котором  была бы обеспечена суточная потребность в веществах А, В  С, причем стоимость его была бы наименьшей.

Математическая модель min y 2  ) 3 yxf ,( x   21 3 6 y x   y 2 8 2 x    x y 2 12 4    ,0 y 0 x

Графический метод y 8 6 4 0 f(x,y) = 4x + 5y  →  max x ≥0 y ≥0 4x+6y ≤ 24 4x+6y = 24 3x+2y ≤ 12 3x+2y = 12 x + y ≤ 8 4 6 8 x x= 12 5 y= 12 5 f= 108 5 Вывод: наиболее выгодно выпускать табуретки и стулья в  одинаковом количестве.

ЗЛП неразрешима   Система не имеет  ни одного  решения y 0 x

ЗЛП неразрешима  Целевая функция  не ограничена на  множестве  решений y 0 N x

ЗЛП разрешима  Множество  решений состоит  из одной точки y 0 x

ЗЛП разрешима  Единственное  оптимальное  решение ЗЛП N y 0 x

Решить ЗЛП графически min f      x  x y  2 1 x y  y 2 x  4 y 2 x   y ,0 0 max f    x  2 y x  1 y x  1 x y   ,0 1 y max f    x  x 2 y  y 1 x   x 2 y 1   ,0 y 0 max  y x f   x y 1   ,0 x y 0

Решить ЗЛП графически f(x,y) = 3820 – 5x – 4y   min→       x 320 200   yx 0  x 0  y 0 280   x y 0 100  y ,0  0

Решить ЗЛП графически №1 №2 120 тыс.т 80 тыс.т А Б В 100 тыс.т 60 тыс.т 40 тыс.т Стоимость перевозок №1 №2 24 15 12 18 27 9 А Б В

Математическая модель 5 y  1380  min  x 120 80 ) ,( yxf   y x   x 100    y 60    x y   0 x  0 y

Графическое решение  3x 120 80 ) ,( yxf  x y  x 100  y 60  x y  0  0 x y 15  y 4140  min y 120 80 60 10 0 10 80 100 120 x x=60, y=60, f =3420