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

Задача составления рациона (задача о диете).

Для откорма животного используется n видов кормов, содержащих m видов питательных веществ. Пусть- содержание i- го питательного вещества в одном килограмме j - го вида корма - стоимость одного килограмма j-ro вида корма Минимальная суточная потребность животного в i-ом питательном веществе равна . Необходимо составить наиболее дешевый рацион нужной питательности.

Обозначим через x_j количество килограммов корма j-го вида.

Очевидно, математическая модель задачи такова.

f = → min

при ограничениях:

Линейным ограничением, наложенным на переменные , называется соотношение одного из следующих трех типов:

где - действительные числа.

Например, соотношения 2х -≤ 1 или ≥ 0 являются

линейными, а соотношения ≥ 3 или sin x₁ ≤ не являются линейными.

Общая постановка задачи линейного программирования (ЗЛП) состоит в следующем.

Дана некоторая линейная функция

f =_n (2.1)

и некоторая система линейных ограничений, наложенных на переменные :

(2.2)

Требуется найти такие значения переменных , которые

удовлетворяли бы ограничениям (2.2) и при этом условии обращали бы в оптимум (max и min) функцию (2.1).

Функция (2.1) называется целевой. Каждый набор значений переменных, при которых удовлетворяются ограничения (2.2), называется допустимым решением или допустимым планом ЗЛП. Совокупность всех допустимых решений называется областью допустимых решений (ОДР).

Приведенные в параграфах 2.1, 2.2, 2.3 задачи являются, очевидно, задачами линейного программирования.

Допустимое решение, обращающее целевую функцию в оптимум, называется оптимальным решением или оптимальным планом.

Говорят, что ЗЛП разрешима, если она имеет оптимальный план. В противном случае задача называется неразрешимой.

ЗЛП может быть неразрешимой только по следующим двум причинам:

а) ОДР пуста;

б) ОДР непуста, но целевая функция не ограничена на ОДР сверху, если в ЗЛП ищется ее максимум, или - не ограничена снизу, если в ЗЛП ищется минимум целевой функции.

Например, задача: f =min

при ограничениях

неразрешима из-за пустоты ОДР.

Задача же f =max при ограничениях

неразрешима из-за того, что целевая функция не ограничена сверху на ОДР. (Чтобы убедиться в этом, рассмотрите такие допустимые решения: и т.д.).

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