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

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

В общей постановке задачи линейного программирования формулируется следующим образом.

Имеются какие-то переменные =(x ₁, x ₂,…, x_n) и линейная функция этих переменных, которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции при условии, что переменные удовлетворяют системе линейных равенств и/или неравенств.

Классическими примерами практических задач, сводящихся к задаче линейного программирования, являются задача о диете, а также задача о составлении плана производства.

В задаче о диете составляется наиболее экономный (т.е. наиболее дешевый) рацион питания животных, удовлетворяющий определенным медицинским требованиям. При этом в качестве переменных x ₁, x ₂,…, x_n выступают количества продуктов питания, используемых в рационе.

Задачу о составлении плана производства рассмотрим более подробно.

Пусть некоторая производственная единица (предприятие, цех, отдел и т.д.) может производить n видов товаров G ₁, G ₂,…, G_n, используя при этом m видов сырьевых ресурсов R ₁, R ₂,…, R_m, запасы которых ограничены величинами b ₁, b ₂,…, b_m.

Tехнологией производства товара G_j назовем набор чисел a_ij, показывающий, какое количество i -го ресурса необходимо для производства единицы товара G_j. Это можно записать в виде технологической матрицы, которая полностью описывает технологические потребности производства и элементами которой являются числа a_ij.

	G 1	G 2	…	G тn
R 1	a 11	a 12	…	a 11
R 2	a 21	a 22	…	a 2 n
…	…	…	…	…
R m	am 1	am 2	…	anm

Предположим также, что известны цены реализации единицы каждого товара с ₁, с ₂, …, с_n.

Обозначим через x ₁, x ₂,…, x_n планируемое производство единиц товаров G ₁, G ₂,…, G_n. В силу имеющейся технологической матрицы для этого потребуется:

a ₁₁ x ₁+ a ₁₂ x ₂+…+ a _{1 n} x_n – ресурса R ₁,

a ₂₁ x ₁+ a ₂₂ x ₂+…+ a _{2 n} x_n – ресурса R ₂,

……………………………………….

a _m1 x ₁+ a _m2 x ₂+…+ a _{m n} x_n – ресурса R_m.

С учетом ограничений на запасы ресурсов, а также очевидных условий неотрицательности переменных x ₁, x ₂,…, x_n получим следующую систему линейных неравенств:

Естественно предположить, что целью производственной единицы является получение максимальной выручки за произведенную продукцию, т.е. максимизация функции:

F = c ₁ x ₁+ c ₂ x ₂+…+ c_nx_n.

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

F = c ₁ x ₁+ c ₂ x ₂+…+ c_nx_n ®max

Мы не будем рассматривать примеры других задач линейного программирования. Отметим лишь, что они встречаются очень часто при оптимизации самых разнообразных производственных и экономических задач.

B. Формы задач линейного программирования. Основные понятия и утверждения.

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

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

(1.1)

при условиях

(1.2)

(1.3)

где a_ij, b_i, c_j - заданные постоянные величины и k£ m.

Функция (1.1) называется целевой функцией задачи (1.1)-(1.3), а условия (1.2)-(1.3) - ограничениями данной задачи.

Таким образом, ограничения в общей задаче ЛП заданы в виде линейных неравенств и/или линейных уравнений. При этом заметим, что в неравенствах, вообще говоря, могут применяться оба знака, как "£", так и "³". Однако домножением при необходимости обеих частей какого-либо неравенства на (-1) можно свести их все к единому виду (1.2).

Вектор =(x₁, x₂,..., x_n), компоненты которого удовлетворяют ограничениям (1.2)-(1.3), называется допустимым планом (или допустимым решением).

Совокупность всех допустимых планов задачи линейного программирования образует допустимое множество решений этой задачи. Будем обозначать его через Х.

Допустимый план =(x₁*, x₂*,...x_n*), при котором целевая функция задачи (1) принимает свое максимальное (минимальное) значение, называется оптимальным.

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

Помимо общей формы различают еще две частные задачи линейного программирования - стандартную и основную.

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

(1.4)

Ограничения основной задачи ЛП представляют собой линейные ограничения-равенства, а также условия неотрицательности на переменные:

(1.5)

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

Например, сведение задачи минимизации функции к задаче максимизации осуществляется простым домножением целевой функции на (-1). То есть, если в задаче линейного программирования функция

®min,

то, введя в рассмотрение функцию , получим:

®max.

Переход от стандартной задачи к основной связан с введением дополнительных переменных x_n+i , i= 1, …, m. Покажем это на примере.

Пример 1.1. Исходная задача ЛП имеет вид:

В первом из неравенств левая часть не больше правой части. Поэтому добавлением в левую часть некоторого неотрицательного слагаемого x ₄ можно свести это неравенство к равенству. Аналогично во втором неравенстве левая часть не меньше правой. Следовательно, вычитая из левой части некоторое неотрицательное число x ₅, можно также свести данное неравенство к равенству. Итак, получим новую форму записи задачи ЛП (основную):

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