Линейное программирование. Общие понятия

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

Таким образом, задачи линейного программирования относятся к за­дачам на условный экстремум функции. Казалось бы, что для исследова­ния линейной функции многих переменных на условный экстремум дос­таточно применить хорошо разработанные методы математического ана­лиза. Однако, невозможность их применения показывают простейшие примеры. Пусть необходимо исследовать на экстремум линейную функцию Z = Z (x₁; x₂;…x_n) =  при линейных ограничениях

Так как Z – линейная функция, то в общем случае , а, следовательно, внутри области экстремальных точек не существует. Значит, min (mах) значения линейной функции находятся на границе области, которая образована системой ограничений. Для отыскания этих значений потре­бовалось создание специальных методов. Особенно широкое распростра­нение математическое программирование получило в экономике, так как исследование зависимостей между величинами, встречающимися во мно­гих экономических задачах, приводит к линейной функции с линейными ограничениями.

 

Построение математических моделей простейших

Экономических задач

1. Задача использования сырья

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

 Рассмотрим задачу на конкретном примере. Для изготовления двух видов продукции Р₁, Р₂ используют три вида сырья S₁, S₂, S₃. Запасы сырья, количество единиц продукции, а также величина прибыли, получаемая oт реализации единицы продукции, приведены в табл. 1.

Таблица 1

Виды сырья	Запас сырья	Количество единиц сырья, идущих на изготовление единицы продукции
		Р1	Р2
S1 S2 S3	20 40 30	2 8 5	5 5 6
Прибыль от единицы продукции, (руб.)		50	40

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

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

Также на х₁ и х₂  должно быть наложено ограничение неотрицатель­ности х₁ ³ 0, х₂ ³ 0. Конечную цель решаемой задачи – получение макси­мальной прибыли при реализации продукции, выразим как функцию цели Z = 50х₁ + 40х₂ (руб.). Числа х₁, х₂ могут быть и дробными, так как в задаче не оговорены условия целочисленности.

 Итак, мы построили ма­тематиче­скую модель задачи использования сырья (ресурсов): найти max значение целевой функции Z = 50 х₁ + 40 х₂ при ограничениях

при условии х1 ³ 0, х2 ³ 0.

Обобщим эту задачу (табл. 2).              

Таблица 2

Виды сырья	Запас сырья	Количество единиц сырья, идущих на изготовление единицы продукции
		Р1	Р2	…	Рn
S1 S2 … Sm	В1 В2 … Вm	a11 a21 … am1	a12 a22 … am2	… … … …	a1n a2n   amn
Прибыль		c1	c2	…	cn

Математическая модель задачи

Пусть дан план = {x₁, x₂, … x_n} где x_j – количество изготовленной единиц   j продукции. Тогда требуется найти целевую функцию Z = c₁x₁ + c₂x₂ + … + c_nx_n при ограничениях (условиях):

2. Задача о смесях.

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

При откорме каждое животное ежедневно должно получить не менее 9 единиц питательного вещества S₁, не менее 8 единиц вещества S₂ и не менее 12 единиц вещества S₃. Для составления рациона используют два вида корма. Содержание количества единиц питательных веществ в 1 кг каждого вида корма и стоимость 1 кг корма приведены в табл. 3.

Таблица 3

Питательные вещества	Количество единиц питательных веществ в 1 кг корма
	Корм 1	Корм 2
S1 = 9 S2 = 8  S3 = 12	3 1 1	1 2 6
Стоимость 1 кг корма (в руб.)	4	6

Необходимо составить дневной рацион нужной питательности, причем затраты на него должны быть min.

Для составления математической модели обозначим через x₁, x₂ – количество килограммов корма соответственно 1 и 2 в дневном рационе:

Цель данной задачи – добиться min затрат на дневной рацион, поэтому общую стоимость рациона можно выразить целевой функцией Z = 4x₁ + 6x₂.

Задачу составления рациона можно обобщить, если предусмотреть в рационе т видов питательных веществ в количестве не менее В _i (i = ) и использовать n видов кормов. Обозначим через а _ij − количество единиц i-го питательного вещества, содержащего-ся в единице j-го корма, c _j − стоимость единицы j корма, x _j – количество единиц j-го корма в дневном рационе. Тогда, требуется найти min Z = с₁х₁ + с₂х₂ + … + с_n х_n, при ограничениях:

Помимо этих задач, можно привести примеры задач о раскрое мате­риалов, о размещении заказа, транспортной задачи и т. д.