3. Понятие линейного программирования.

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

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

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

Общая форма задачи имеет вид: найти

(1')

при условиях

(2')

где

(3')

Cистема соотношений (1')-(3') –общий вид задачи линейного программирования.

Ограничения (3') называют условиями неотрицательности переменных. В рассматриваемом случае все ограничения имеют вид неравенств. Иногда они могут быть смешанными, то есть неравенства и равенства.

Если все ограничения (2') имеют вид строгих равенств

(2'')

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

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

Допустимый план при котором целевая функция (1') принимает своё максимальное (минимальное) значение называется оптимальным.

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

Среди разных разделов математического программирования наиболее развитым и законченным является линейное программирование (ЛП).

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

Рассмотрим некоторые из них.

Определение оптимального плана производства.

Имеются m видов ресурсов в количествах b₁, b₂, . , b_m и n видов изделий. Задана матрица A=(a_ij), i=1,.,m, j=1,.,n, где a_ij характеризует нормы расхода i-го ресурса на единицу j-го вида изделий. Прибыль от реализации единицы j-го вида изделий характеризуется показателем с_j. Нужно определить такой план выпуска изделий (оптимальный ассортимент), при котором прибыль будет максимальной.

Обозначим количество единиц k-го вида изделий, выпускаемых предприятием, через x_k, к=1,…,n. Тогда математическая модель этой задачи будет иметь такой вид:

Найти максимальное значение функции при ограничениях на ресурсы

Кроме ограничений на ресурсы в эту модель необходимо ввести дополнительные ограничения неотрицательности переменных .

Задача о смесях (о диете)

Имеется 3 вида корма, при сочетании которых в разных пропорциях получают разные смеси. Каждый компонент, а следовательно и смесь, содержит 3 вида питательных веществ. Эти вещества содержатся в трех видах кормов в объеме:

Питательные вещества	Количество питательных веществ в 1 кг корма, единиц
	I	II	III
А	1	3	4
В	2	2	2
С	2	4	3
Цена 1 кг корма	4 грн.	5 грн.	8 грн.

Составить математическую модель задачи определения дневного рациона животного, если необходимо минимизировать стоимость от корма, при условии что каждое животное ежедневно должно получить не менее 50 единиц питательного вещества А, не менее 40 единиц питательного вещества В и не менее 15 единиц вещества С.

Обозначим количество кг k-го вида корма через x_k, к=1,2,3.

Задача о раскрое материалов.

На мебельной фабрике необходимо вырезать не менее чем 24, 28 и 18 заготовок трёх размеров из стандартных листов фанеры. Лист фанеры можно разрезать двумя способами. Количество полученных при этом заготовок и площадь отходов приведены в таблице:

Тип заготовок	Количество заготовок (шт.)
	1 способ	2 способ
1	2	5
2	3	4
3	2	6
Площадь отходов (кв.м.)	10	16

Сколько листов фанеры необходимо разрезать 1-ым способом, а сколько 2-ым, чтобы получить требуемое количество заготовок с минимальными отходами?

Обозначим количество листов фанеры разрезанных первым способом – x₁, вторым способом – x₂.

Математическая модель этой задачи имеет такой вид: найти минимальное значение функции при ограничениях