Примеры составления задач ЛП

При условиях

При условиях

При условиях

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

Глава 1. Метод линейного программирования

Сведение общей задачи ЛП к равносильной ей основной задаче путём введения добавочных неизвестных.

Общей задачей ЛП является отыскание наибольшего или наименьшего значения линейной функции на множестве неотрицательных решений линейной системы неравенств или системы: неравенства + уравнения.

В основной задаче ЛП линейная система содержит только уравнения:

Минимизировать (максимизировать):

Общая задача ЛП может быть сведена к равносильной ей основной задаче путём введения добавочных неизвестных. Например, дана общая задача

.

Здесь показатель качества и ограничения линейны относительно неизвестных. Сведем общую задачу ЛП к равносильной ей основной задаче:

;

.

Между общей задачей ЛП и соответствующей ей основной существует связь. Если оптимальное решение (оптимальный план) основной задачи, то – оптимальное решение общей задачи и наоборот. Причем оптимальные значения целевых функций совпадают:

Таким образом, удалив из оптимального решений основной задачи значения добавочных неизвестных, получим оптимальное решение общей задачи. Если основная задача не имеет решения, то и общая задача также не имеет решения.

Задача ЛП является задачей максимизации, если находяти минимизации, если находят.

В литературе могут также встретиться и другие формы записи общей и основной задач ЛП [1-4]:

1) Максимизировать (минимизировать) функцию цели

переменные которой подчинены следующим условиям:

.

2) Минимизировать

3) Минимизировать при условиях, где

– вектор-строка; - вектор-столбец; – матрица коэффициентов системы ограничений;

– вектор-столбец.

Формулировка задачи о рациональном питании [2].

Для сохранения здоровья и работоспособности человек должен потреблять в сутки определенное количество питательных веществ (белков, жиров, углеводов, воды, витаминов), запасы которых в различных видах пищи () различны. Ограничимся, например, двумя видами пищи.

Питательные вещества	Норма суточная	Виды пищи
Жиры
Белки
Углеводы
Вода
Витамины

Здесь – запас жиров в единице (например, в 1 кг) пищи вида и т.д. и– стоимость единицы (1 кг) пищи видаи. Требуется так организовать питание, чтобы стоимость его была наименьшей, а организм получил бы не менее минимальной суточной нормы питательных веществ всех видов пищи.

Пусть – количество (например, в кг) пищи видов и, потребляемых человеком в сутки. Тогда общие запасы жиров в двух видах пищи не должны быть меньше минимальной нормы, т.е. и т.д., всего 5 неравенств (обратить внимание на знак). Общая стоимость питания, т.е. имеем следующую задачу ЛП:

при условиях:

;

;

;

;

;

Дата добавления: 2014-01-04