Постановка задачи линейного программирования

 

Пусть дана система т линейныхуравнений и неравенств с п переменными:

 

(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) принимает минимальное значение.

 

⇐ Предыдущая1234Следующая ⇒

Поделиться:

Популярное:

1. I. Постановка и состояние темы
2. I. ЦЕЛИ И ЗАДАЧИ ВЫПУСКНОЙ КВАЛИФИКАЦИОННОЙ РАБОТЫ
3. I.6. Педагогика как учебный предмет и задачи профессионального
4. III.10 Задачи на сцепление генов
5. III.2 Задачи на моногибридное скрещивание
6. III.8 Задачи на взаимодействие неаллельных генов
7. Q Задача об аренде оборудования: постановка задачи и методы решения
8. Административно-процессуальное право: предмет, метод и задачи. Источники административно-процессуального права. Система а-п права. Административно-процессуальные нормы в системе норм права.
9. Административное расследование: задачи, место и сроки проведения.
10. Асинхронные задачи интерфейса с устройствами ввода/вывода.
11. Билет № 28. Комбинаторные задачи. Виды и формулы для подсчёта числа возможных комбинаций.
12. Блок программирования, регуляции и контроля двигательной деятельности