 |
Примеры задач линейного программирования
|
|
|
|
Глава 2 Линейное и целочисленное программирование
Постановка задачи линейного программирования
Пусть дана система т линейныхуравнений и неравенств с п переменными:
(1)
и линейная функция:
(2)
Требуется найти решение системы 
при котором функция z принимает оптимальное значение (максимальное или минимальное).
Такая задача называется задачей линейного программирования (ЗЛП) в общем виде. Система (1) называется системой ограничений; функция (2) называется целевой функцией (функцией цели).
Таким образом, задачи линейного программирования (ЛП) – это задачи, в которых линейны как целевая функция, так и ограничения в виде равенств или неравенств и для которых методы математического анализа оказываются непригодными. Задачи ЛП представляет собой наиболее часто используемый метод оптимизации.
К их числу относятся задачи:
- рациональное использование сырья и материалов; задачи оптимизации раскроя;
- рациональное использование сырья и материалов; задачи оптимизации раскроя;
- оптимизации производственной программы предприятий;
- оптимального размещения и концентрации производства;
- на составление оптимального плана перевозок, работы транспорта;
- управления производственными запасами
и многие другие, принадлежащие сфере оптимального планирования.
Около 75% от общего числа применяемых оптимизационных методов приходится на задачи ЛП. Около четверти машинного времени, затраченного в последние годы на проведение научных исследований, было отведено решению задач ЛП и их многочисленных модификаций.
ЗЛП можно записать в сокращенном виде:
(
)
(
)
Оптимальным решением (планом) ЗЛП называется решение 
системы ограничений (2), при котором целевая функция принимает оптимальное значение.
|
|
|
Если система ограничений (1) состоит из одних неравенств (не нарушая общности, будем говорить, что ограничения имеют вид «
», так как, если знак неравенства «
», то можно умножить его на -1 перейти к неравенству вида «»), то такую задачу называют задачей линейного программирования в стандартном виде (в стандартной форме).
Если все ограничения системы (1) - уравнения (вида «=»), то такую задачу называют задачей линейного программирования в каноническом виде (в канонической форме).
Справедливо утверждение. Любая ЗЛП может быть приведена к каноническому виду.
Приведем ограничения (1) к каноническом виду:
Теорема. Любому решению неравенства 
соответствует определенное решение 
уравнения 
в котором 
и наоборот.
Примеры задач линейного программирования
Задача об использовании ресурсов. Для изготовления двух видов продукции 
и 
используется четыре вида ресурсов 
, Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в таблице 1:
| Вид ресурса | Запас ресурса | Число единиц ресурсов, затрачиваемых на изготовление единицы продукции | |
|
|
| ||
| |||
| |||
| - | ||
| - |
Прибыль, получаемая от единиц продукции и -соответственно 2 и 3 руб. Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной.
Решение. Составим экономико-математическую модель задачи. Пусть 
и 
- число единиц продукции и соответственно, запланированных к производству. Для их изготовления потребуется 
единиц ресурса ; 
единиц ресурса ; 
единиц ресурса и 
единиц ресурса . Так как потребление ресурсов не должно превышать запасов, соответственно 18, 16, 5 и 21 единицы, то связь между потреблением ресурсов и их запасами выразится системой неравенств:
|
|
|
(3)
По смыслу задачи переменные:
(4)
Суммарная прибыль 
составит 
руб. от реализации продукции и 
руб. от реализации продукции , т.е.:
(5)
Таким образом, получили экономико-математическую модель задачи: найти такой план выпуска продукции 
, удовлетворяющий системе (3) и условию (4), при котором функция (5) принимает максимальное значение.
Задача составления рациона (задача о диете, задача о смесях). Имеются два вида корма I и II, содержащие питательные вещества (витамины) 
. Содержание числа единиц питательных веществ в 1 кг каждого вида корма и необходимый минимум питательных веществ приведены в таблице 2:
| Питательное Вещество (витамин) | Необходимый минимум питательных веществ | Число единиц питательных веществ в 1 кг корма | |
| I | II | ||
|
| |||
|
| |||
|
|
Стоимость 1 кг корма I и II соответственно равна 4 и 6 руб. Необходимо составить такой дневной рацион, имеющий минимальную стоимость,в котором содержание каждого вида питательных веществ было бы не меньше установленного предела.
Решение. Составим экономико-математическую модель задачи. Пусть и - количество кормов I и II, соответственно, входящих в дневной рацион. Этот рацион будет включать 
единиц питательного вещества ; 
единиц питательного вещества ; 
единиц питательного вещества . Так как содержание питательных веществ , в рационе должно быть не менее, соответственно 9,8, 12 единицы, получим систему неравенств:
(6)
По смыслу задачи переменные:
(7)
Общая стоимость рациона z составит в руб.:
(2)
Таким образом, получили экономико-математическую модель задачи: составить дневной рацион , удовлетворяющий системе (6) и условию (7), при котором функция (2) принимает минимальное значение.
|
|
|
