Постановка задачи линейного программирования. Геометрическая интерпретация.

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

Определение оптимального ассортимента. Имеется р видов ресурсов в количествах а1, а2,..., аi,..., аp и q видов изделий. Задана матрица А=||aik||, где аik характеризует нормы расхода i-го ресурса на единицу k-го изделия (k = 1, 2,..., q).

Эффективность выпуска единицы k-го изделия характеризуется показателем сi, удовлетворяющим условию линейности.

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

Количество единиц k-го изделия, выпускаемых предприятием, обозначим хk. Тогда математическая модель задачи имеет такой вид: найти (1.3)

при ограничениях (1.4)

Кроме ограничения по ресурсам (1.3), в модель могут быть введены дополнительные ограничения на планируемый выпуск продукции xj³xj0, условия комплектности для сборки xi: хj: xk. = bi: bj: bk для всех i, j, k и т. д.

Оптимальное распределение взаимозаменяемых ресурсов. Имеются т видов взаимозаменяемых ресурсов а1, а2,..., аi,..., аm используемых при выполнении п различных работ в объеме b1, b2, …, bn.

lЗаданы числа ij, указывающие, сколько единиц j-й работы можно получить из единицы i-го ресурса, а также сij — затраты при изготовлении единицы j-го продукта из i-го ресурса.

Требуется распределить ресурсы по работам таким образом, чтобы суммарная эффективность была наибольшей (или суммарные затраты — наименьшими).

Данная задача называется общей распределительной задачей.

Количество единиц i-го ресурса, которое выделено для выполнения работ j-то вида, обозначим xij.

Математическая модель задачи такова: найти (1.5) при ограничениях

(1.6) (1.7)

Ограничение (1.6) означает, что план всех работ должен быть выполнен полностью, а ограничение (1.7) — что ресурсы должны быть израсходованы целиком.

2. Математическая модель задачи линейного программирования (ЗЛП). Задачу линейного программирования можно сформулировать так Найти

(2.1)при условиях

(2.2)

и (2.3)

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

Определение 3. Допустимым множеством решений задачи (2.1)—(2.3) называется множество R(х) всех векторов х, удовлетворяющих условиям (2.2) и (2.3).

Очевидно множество R(х) представляет собой выпуклое многогранное множество или выпуклый многогранник.

Отметим, что поскольку minF(х) эквивалентен max[-F(х)], то задачу ЛП всегда можно свести к эквивалентной задаче максимизации.