Основные теоретические сведения

     1 ОСНОВНЫЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

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

     Для практического решения экономической  задачи математическими методами ее, прежде всего следует записать с  помощью математических выражений (уравнений и неравенств), то есть составить экономико-математическую модель. Можно наметить следующую общую схему формирования модели:

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

     В общем виде математическая формулировка задачи линейного программирования (ЗЛП) следующая: найти значения переменных х_i (i = 1, ..., n), при которых достигается максимум (минимум) целевой функции:

                                  F = c₁x₁ + c₂x₂ + ... + с_nх_n ® max (min)                                   (1.1)

и выполняются  ограничения: 

а11х1 + а12х2 + … + а1nхn {£, =, ³} b1; а21х1 + а22х2 + … + а2nхn {£, =, ³} b2; … аm1х1 + аm2x2 + … + аmnхn {£, =, ³} bm; xj ³ 0, (i = 1, …, n),

(1.2)

 

где а_ij, b_i, c_j — заданные постоянные величины;

m —  число уравнений;

n —  число переменных. 

     Запись {£, =, ³} в ограничениях (1.2) означает, что возможен один из знаков (£, = или ³).

     Решение Х = (х₁, х₂, …, х_n), при котором выполняются все ограничения, называется допустимым. Допустимое решение, при котором функция F принимает оптимальное значение (максимум или минимум), называется оптимальным.

       Для производства продукции n типов требуются ресурсы m видов. Нормы расхода ресурсов на производство одной единицы продукции каждого типа заданы матрицей {a_ij}, где a_ij - количество ресурса i-го вида, необходимое для производства одной единицы продукции j-го типа. Известно количество ресурсов (b_i, где i = 1, ..., m) каждого вида, которое имеется в наличии у предприятия. Известны также величины прибыли (С_j), которую получит предприятие при реализации одной единицы продукции j-го типа. Требуется найти оптимальный план производства продукции, т. е. количество продукции каждого типа, которое нужно произвести, чтобы получить наибольшую прибыль.

     Обозначим через x_j количество продукции j-го типа, которое планируется выпустить (j = 1, ..., n). Тогда математическая модель задачи будет выглядеть следующим образом:

                                                                                (1.3)

                                       (1.4)

                                                     (1.5)

     Целевая функция задачи (1.3) представляет собой общую прибыль от производства всей продукции. Ограничения (1.4) выражают условие, при котором потребление ресурса i-го вида не должно превышать запаса этого ресурса (b_i). Условия неотрицательности переменных (1.5) вытекают из смысла переменной x_j: количество продукции не может быть отрицательным.

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

     Чтобы привести к виду равенства ограничение вида

,

в левую  часть неравенства прибавляют дополнительную переменную:

.

     Аналогично, чтобы привести к каноническому  виду ограничение  вида

,

из левой  части неравенства вычитают дополнительную переменную:

.

     Дополнительные  переменные вводятся в целевую функцию  с коэффициентами, равными 0:

.

     Таким образом, задача (1.3)–(1.5) может быть записана в следующем каноническом виде:

             (1.6)

             (1.7)

             (1.8)

             (1.9)

     Экономический смысл переменных y_i (i = 1, …, m) следующий: это остатки ресурсов каждого вида. Если при оптимальном решении какой-либо ресурс будет использован полностью, то ограничение исходной задачи (1.4) будет выполнено в виде равенства, а y_i = 0. Такое ограничение в отчетах Exсel называется связанным. 

     С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной. Первоначальная задача при этом называется исходной, или прямой. Связь этих задач заключается, в частности, в том, что решение одной из них может быть получено непосредственно из решения другой (табл. 1.1). 

   Таблица 1.1 Двойственная задача

Исходная  задача	Двойственная  задача
(1.3)	(1.6)
(1.4)	(1.7)
(1.5)	(1.8)

 

     Эта задача составляется по следующим правилам:

1. Поскольку исходная задача составляется на максимум, то двойственная - на минимум целевой функции;
2. В исходной задаче ограничения имеют знаки неравенств «£», а в двойственной – «³»;
3. Каждому ограничению исходной задачи соответствует переменная двойственной задачи, а каждой переменной исходной задачи - ограничение двойственной задачи;
4. Матрица системы ограничений двойственной задачи является транспонированной матрицей системы ограничений исходной задачи;
5. Правые части ограничений в двойственной задаче равны коэффициентам при переменных в целевой функции исходной задачи;
6. Коэффициенты при переменных в целевой функции двойственной задачи равны правым частям ограничений исходной задачи;
7. В двойственной задаче, как и в исходной, накладываются ограничения на не отрицательность переменных.