Формулировка задачи - Линейное программирование

Даны линейная функция

Z=С1 х1 +С2 х2 +...+СN xN (1.1)

И система линейных ограничений

A11 x1 + a22 x2 +... + a1N ХN = b1

A21 x1 + a22 x2 +... + a2N ХN = b2

...............

AI1 x1 + aI2 x2 +... + aIN ХN = bI (1.2) ...............

AM1 x1 + aM2 x2 +... + aMN ХN = bM

XJ 0 (j = 1, 2, ..., n) (1.3)

Где аIj, bJ и СJ - заданные постоянные величины.

Найти такие неотрицательные значения х1, х2, ..., хN, которые удовлетворяют системе ограничений (1.2) и доставляют линейной функции (1.1) минимальное значение.

Общая задача имеет несколько форм записи.

Векторная форма записи. Минимизировать линейную функцию Z = СХ при ограничениях

А1 х1 + А2 x2 +... + АN xN = АО, X0 (1.4)

Где С = (с1, с2, ..., сN ); Х = (х1, х2, ..., хN ); СХ - скалярное произведение; векторы A1 = A2 =, ..., AN состоят соответственно из коэффициентов при неизвестных и свободных членах.

Матричная форма записи. Минимизировать линейную функцию, Z = СХ при ограничениях АХ = А0 Х0, где С = (с1, с2, ..., сN ) - матрица-cтрока; А = (аIj ) - матрица системы; Х =(xIj )- матрица-столбец, А0 = (аI ) матрица-столбец

Запись с помощью знаков суммирования. Минимизировать линейную функцию Z = СJ хJ при ограничениях

    0пределение 1. Планом или допустимым решением задачи линейного программирования называется Х = (х1, х2, ..., хN ), удовлетворяющий условиям (1.2) и (1.3). 0пределение 2. План Х = (х1, х2, ..., хN ) называется опорным, если векторы А (i = 1, 2, ..., N), входящие в разложение (1.4) с положительными коэффициентами х, являются линейно независимыми.

Так как векторы А являются N-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать М.

    0пределение 3. Опорный план называется невырожденным, если он содержит М положительных компонент, в противном случае опорный план называется вырожденным. 0пределение 4. Оптимальным планом или оптимальным решением задачи линейного программирования называется план, доставляющий наименьшее (наибольшее) значение линейной функции.

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

Похожие статьи




Формулировка задачи - Линейное программирование

Предыдущая | Следующая