Общие понятия о методах линейного программирования и определения

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

Н апример, одной из задач линейного программирования является т.н. “транспортная задача”, когда имеется n поставщиков и m потребителей некоторого вида продукции:

1

.

. .

. .

. .

Пусть n поставщиков располагают a₁, a₂,..., a_n единицами продукта (груза) и этот груз должен быть доставлен m потребителям в количествах b₁, b₂,..., b_m . Известны стоимости c_ij перевозки единицы груза от i-го поставщика j-му потребителю. Следует определить план перевозок, т.е. указать количество груза, которое каждый поставщик должен доставить каждому потребителю, так чтобы суммарные транспортные затраты были наименьшими:

, где x_ij - искомые количества единиц груза, перевозимые от

i-го поставщика j- му потребителю.

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

Возможны следующие сокращенные обозначения матриц:

A= {a_ij} _{n x m}

A= ||a_ij|| _{n x m}

A= (a_ij) _{n x m}.

Частные случаи матриц - векторы:

вектор-столбец n х 1:

и вектор- строка 1 х n: C = (с₁, с₂, с₃,..., с_n).

Например, план перевозок транспортной задачи можно представить в виде матрицы:

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

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

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

В общем виде задача линейного программирования (ОЗЛП) представляется в математическом виде следующим образом:

, (19)

где F - целевая функция, при следующих условиях:

, (20)

, (21)

, (22)

, (23)

где x_j - искомые неизвестные значения.

Равенства и неравенства (20)-(22) называются ограничениями или граничными условиями и определяются постановщиком задачи;

(23) - условие неотрицательности переменных при решении задач.

Набор значений x_j, удовлетворяющих условиям (20)-(23) называется допустимым планом (решением).

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

В матричных обозначениях задача может быть представлена следующим образом:

максимизировать (минимизировать) функцию

F = C X

при заданных ограничениях

A X  (=,) B.

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

F = 4x₁ + 3x₂  min,

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

x₁ + 2x₂  10

5x₁ + 3x₂ + 4x₃ = 60

x₁ - x₂  2

x₁  0, x₂  0, x₃  0.

Таблица

No.	Значение неизвестных			Основные ограничения			Условия неотрицатель-	Значение целевой функции F
п/п	X1	X2	X3	1	2	3	ности
1	5	1	8	+	+	-	+	(не надо считать)
2	1	5	10	-	+	+	+	(не надо считать)
3	2	2	11	+	+	+	+	14 + (допустимый)
4	0	-2	16	+	+	+	-	(не надо считать)
5	4	2	8,5	+	+	+	+	22 + (допустимый)
6	2	0	12,5	+	+	+	+	8 + (допустимый)
7	0	0	15	+	+	+	+	0 + (оптимальный)

Анализируя результаты, приведенные в таблице, приходим к выводу: из рассмотренных 7-ми вариантов планов, варианты 1, 2, 4 являются недопустимыми, варианты 3, 5, 6, 7 являются допустимыми планами. Оптимальным является план N 7.

Планы 3, 5, 6 являются допустимыми, но не оптимальными.