Глава 1. Основы теории линейного программирования

1.1. Виды задач линейного программирования

Общая задача линейного программирования (злп).

Необходимо найти вектор x = ( x₁, x₂, …, x_n )D  R_n

(1)

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

(2)

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

, (3)

где символ R_i – один из возможных знаков отношений

c_j , b_i , a_ij – заданные вещественные числа, .

Числа с_j – коэффициенты целевой функции;

элементы a_ij – коэффициенты матрицы ограничений;

числа b_i – правые части системы ограничений.

Границы изменения переменных α_j и β_j произвольные вещественные числа, _j  –  , _j  + .

Цель решения ЗЛП (1) – (3) найти оптимальный план задачи, т.е. такого плана, на котором достигается наибольшее (или наименьшее) значение целевой функции (1).

Теперь рассмотрим следующую производственную задачу. Пусть предприятие может изготавливать n видов продукции, используя при этом m видов ресурсов, запасы которых ограничены. Прибыль, получаемая от реализации каждого вида продукции, различна. При этом нормативный расход i-го ресурса, затрачиваемого на производство единицы продукции j-го вида, составляет a_ij , . Известны запасы ресурсов каждого вида в количестве b_i . Прибыль, получаемая от реализации единицы продукции j-го вида, составляет с_j денежных единиц.

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

Построим экономико-математическую модель этой задачи. Обозначим x_j количество единиц продукции j-го вида, , запланированных к производству. Тогда прибыль будет выражена в виде целевой функции:

(1.4)

Для изготовления всей продукции потребуется единиц ресурса i-го вида. Поскольку запас i-го ресурса не превосходит величины b_i , , то для всех рассматриваемых ресурсов имеем систему ограничений:

(1.5)

Так как выпуск продукции не может быть отрицательным, то

(1.6)

Система неравенств (1.5) представляет ограничения на используемые ресурсы, а неравенства (1.6) определяют ограничения на выпуск продукции.

Построенная экономико-математическая модель (1.4), (1.5), (1.6) называется многопродуктовой моделью производственного планирования.

Эта же модель может иметь и несколько иную экономическую интерпретацию. А именно, пусть на предприятии выпускается один продукт разными технологическими способами. Количество технологических способов равно n. Величины а_ij характеризуют нормативный расход i-го вида ресурса при применении j-го технологического способа с единичной интенсивностью, например, единичная интенсивность определяет расход ресурсов (трудоемкость изготовления, затраты конкретных материалов и т.п.) при производстве единицы продукта. Аналогично предыдущей модели числа b_i представляют наличие i-го ресурса, а c_j – прибыль от реализации единицы продукции произведенной j-м технологическим способом . Необходимо найти интенсивности использования технологических способов производства (x_j), при которых будет получена наибольшая прибыль.

Экономико-математическая модель этой задачи будет идентична модели (1.4), (1.5), (1.6). В этом случае данная экономическая интерпретация представляет собой однопродуктовую модель производственного планирования.

При этом модель (1.4), (1.5), (1.6) представляет собой стандартную форму записи задачи линейного программирования (ЗЛП).

Характеристика стандартной формы записи ЗЛП:

1. Целевая функция стремится к максимуму.

2. Все непрямые (структурные) ограничения имеют знаки отношений «меньше-равно» ( ≤ ).

3. Все переменные неотрицательны, .

Используя обозначения

– технологическая матрица коэффициентов;

вектор удельной прибыли от реализации продукции ;

вектор запасов ресурсов ; вектор переменных – искомый план производства продукции, получим матричную форму записи стандартной ЗЛП:

,

Здесь (c, x) означает скалярное произведение векторов c и x.

Векторная форма записи стандартной ЗЛП получится, если введем обозначение векторов матрицы системы ограничений

.

Таким образом, векторная форма записи стандартной ЗЛП будет иметь следующий вид:

.

Общая ЗЛП может быть легко сведена к стандартной форме записи при помощи четырех действий (правил), а именно:

1. Структурные ограничения типа ≥ в общей ЗЛП заменяются на ограничения типа  путем их умножения на (-1).

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

3. Если в общей ЗЛП целевая функция стремиться к минимуму, то ее следует умножить на (-1). Полученная новая целевая функция будет стремиться к максимуму. При этом оптимальный план исходной задачи не изменится. Геометрическая иллюстрация этого положения представлена на рис.1.1. Максимум функции (-f(x)) будет в той же точке x^*, что и минимум у исходной функции f(x). При этом min f(x) = - max (-f(x)).

4. В общей ЗЛП переменные могут быть как положительными, так и отрицательными, а в стандартной форме записи ЗЛП переменные неотрицательные. Поэтому, если в общей ЗЛП переменная x_s не определена по знаку, то вводятся две новые неотрицательные переменные x_s1 и x_s2 . Тогда переменная x_s представляется как разность этих двух новых переменных

.

f(x)

f(x)

min f(x)

x^*

0 ⁰ x

max(- f(x))

-f(x)

Рис. 1.1. Геометрическая иллюстрация замены знака в целевой функции

П р и м е р. Рассмотрим следующую общую ЗЛП:

Запишем данную задачу в стандартной форме. Так как на переменную x₃ не наложено ограничение неотрицательности, то она может принимать как положительные, так и отрицательные значения. Поэтому введем две новые неотрицательные переменные и выразим через них x₃, а именно . Вычтем из второго ограничения переменную x₄  0 и умножим третье ограничение на (-1). Тогда стандартная форма записи ЗЛП будет следующая.

.

Каноническая форма записи ЗЛП имеет следующий вид:

(1.7)

(1.8)

(1.9)

Характеристика канонической формы записи ЗЛП:

1. Целевая функция стремится к максимуму (см. (1.7)).

2. Непрямые (структурные) ограничения имеют знаки отношений «равно» (см. (1.8)).

3. Все переменные неотрицательны (см.(1.9)).

Каноническая форма записи ЗЛП имеет особенность, принципиально отличающую ее от других форм записи. А именно, если в стандартной форме записи соотношение между количеством переменных n и непрямых ограничений m произвольное, то в канонической ЗЛП всегда число ограничений строго меньше числа переменных, m  n. Это связано со следующими обстоятельствами:

а) если m = n, то каноническая ЗЛП как задача оптимизации теряет смысл, поскольку, если она имеет решение, то это решение единственное.

б) если m  n , то система уравнений переопределена и не имеет решения.

Все вычислительные методы в линейном программировании применяются к канонической форме записи ЗЛП.

Рассмотрим процедуру сведения стандартной формы ЗЛП к канонической. Произвольное неравенство стандартной формы записи ЗЛП имеет вид:

(1.10)

Введем дополнительную переменную x_n+i :

(1.11)

Из (1.10) следует, что x_n+i  0. С учетом (1.11) выражение (1.10) превращается в равенство

.

Таким образом, ограничения-неравенства преобразуются в ограничения-равенства. Матрица коэффициентов этой системы ограничений имеет вид:

.

Итак, введение дополнительных переменных в стандартную форму ЗЛП преобразовывает ЗЛП (1.12) в ЗЛП (1.13).

где x = ( x₁, x₂,…, x_n ) – вектор переменных задачи (1.12);

– вектор переменных ЗЛП (1.13)

_{Основные переменные Дополнительные переменные}

– вектор коэффициентов целевой функции ЗЛП (1.13).

Каноническая ЗЛП включает m уравнений и N = m+ n неизвестных. Дополнительные переменные x_n+1 , x_n+2 ,…, x_n+m рассматриваются наравне с основными переменными, т.е. они участвуют в решении задачи так же, как и основные (естественные) переменные. Дополнительным переменным можно придать определенный экономический смысл, например, в многопродуктовой задаче производственного планирования x_n+i есть величина остатка i-го ресурса при реализации производственного плана x = (x₁ , x₂ ,…, x_n).

Различные формы записи ЗЛП эквивалентны в том смысле, что, если знаем решение одной из них, то легко находится решение другой.