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

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

1. требуется найти максимум (или минимум) линейной функции;

2. на неизвестные накладываются ограничения в виде линейных неравенств или уравнений;

3. все неизвестные (в экономических задачах) должны быть неотрицательными.

Общая теория

Определение 1: задачей линейного программирования называется задача, в которой необходимо найти минимум или максимум некоторой линейной функции

f (x) = с₁x₁+с₂x₂ +с₃x₃+…+с_nx_n

при заданных ограничениях (условиях):

x_j  0, j = 1,2,...n

где a_{ij ,} b_{i ,} с_j ( i = 1..m; j = 1..n) – заданные постоянные величины;

x_j ( j = 1..n) – неизвестные.

Определение 2: функция, наибольшее или наименьшее значение которой отыскивается при решении З.Л.П. называется целевой функцией.

Определение 3: вектор = (x_1, x_2, x _3,…x_n), удовлетворяющий системе ограничений З.Л.П., называется допустимым решением или планом З.Л.П.

Определение 4: совокупность всех допустимых решений З.Л.П. называется

областью допустимых решений З.Л.П.

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

Замечание

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

1. Построение математической модели экономической задачи (формулировка задачи линейного программирования).

2. Решение задачи линейного программирования.

3. Интерпретация полученного результата.

Построение математической модели экономической задачи Сформулируем конкретную экономическую задачу и построим математическую модель, адекватную исходным данным.

Задача: Механический цех выпускает три вида взаимозаменяемых деталей: А, В, С.

Каждая из деталей проходит последовательную обработку на трех станках: №1, №2, №3. Запас мощности станков составляет соответственно 220, 400 и 100 часов.

Отпускная цена деталей и время их обработки на каждом из станков приведены в таблице.

Вид детали	Время обработки детали на каждом из станков (в минутах)			Отпускная цена (в у.е.)
	№1 станок	№2 станок	№3 станок
А	12	15	6	30
В	10	18	4	32
С	9	20	4	29

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