Формулировка задачи

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

=С1х1+С2х2+ .+СNxN (1.1)

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

11x1 + a22x2 + . + a1NХN = b121x1 + a22x2 + . + a2NХN = b2

. . . . . . . . . . . . . . .i1x1 + ai2x2 + . + aiNХN = bi (1.2) . . . . . . . . . . . . . . .M1x1 + aM2x2 + . + aMNХN = bMj 0 (j = 1, 2, . ,n) (1.3)

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

где аij, bj и Сj - заданные постоянные величины.

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

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

Векторная форма записи. Минимизировать линейную функцию Z = СХ при ограничениях А1х1 + А2x2 + . + АNxN = Ао, 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 при ограничениях

пределение 1. Планом или допустимым решением задачи линейного программирования называется Х = (х1, х2, ., хN), удовлетворяющий условиям (1.2) и (1.3).

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

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

пределение 3. Опорный план называется невырожденным, если он содержит М положительных компонент, в противном случае опорный план называется вырожденным.

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

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