§ 2. Простейшие задачи линейного программирования

Задача о наилучшем использования ресурсов.

Для трёх видов продукции , и используется три вида сырья и . Предприятие может израсходовать 32 т сырья , не менее 40 т сырья и не более 50 т сырья . Нормы расхода сырья на единицу продукции того или иного вида, а также трудовые и энергетические затраты на производство единицы продукции , и приведены в таблице.

Сырьё	Запасы (т)	Нормы расхода на единицу продукции (т)
	32	2	3	0
	40	4	1	2
	50	3	1	3
Расходы (руб.)		4	5	6

Определить количества продукции видов , и , которые следует производить при минимальных затратах энергетических и трудовых ресурсов.

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

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

Задача о максимальном доходе производственного предприятия.

При производстве трёх видов продукции , и используется три вида сырья и . Запасы каждого вида сырья составляют 32 т, 40 т и 50 т соответственно. Количество единиц сырья, необходимого для изготовления единицы продукции, а также прибыль, получаемая от реализации единицы продукции каждого вида приведены в таблице.

Сырьё	Запасы (т)	Виды продукции
	32	2	3	0
	40	4	1	2
	50	3	1	3
Прибыль (руб.)		4	5	6

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

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

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

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

Задача о рационе питания.

Для сохранения здоровья и работоспособности человек должен употребить в пищу в течение суток определённое количество белков, жиров, углеводов, витаминов, микроэлементов и др.

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

Питательные вещества	Суточная Потребность 1 человека	Виды продукции
	32	2	3	0
	40	4	1	2
	50	3	1	3
Стоимость 1 единицы продукта (руб.)		4	5	6

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

Обозначим через количества единиц продуктов видов , и .

Математическая модель данной задачи будет иметь вид

Задача о структуре товарооборота.

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

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

Математическая модель этой задачи строится следующим образом.

Пусть – план товарооборота предприятия: предлагается реализовать единиц товара первой группы, единиц товара второй группы, …, единиц товара -й группы. Тогда необходимо максимизировать прибыль от реализации всех этих товаров:

.

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

… ,

Геометрический способ решения задачи линейного программирования (графический метод)

Рассмотрим задачу линейного программирования с двумя переменными

(3.1)

Такая задача может быть решена графическим методом ввиду того, что в этом случае легко строить ОДР.

Каждое неравенство системы (3.1) геометрически определяет плоскость с граничной прямой, а сама полуплоскость является полуплоскостью решений.

Все полуплоскости решений, если система (3.1) совместна, пересекаясь образуют некоторую общую часть, которая является ОДР системы (3.1). Эта область может не существовать, состоять из одной точки, отрезка, полупрямой, многоугольника или представлять собой неограниченную область.

Область называется выпуклой, если для любых двух точек, принадлежащих этой области, и весь отрезок, соединяющий эти точки, тоже принадлежат данной области. Например, область, изображённая на рис.3.1. а) является выпуклой, а на рис.3.1. б) – не выпуклой.

А

В

А В

а) б)

Рис. 3.1.

Теорема 3.1. область допустимых решений системы ограниченный (3.1) является выпуклой.

ОДР системы ограниченный (3.1) представляет собой выпуклый многоугольник.

Уравнение , где – некоторое действительное число, определяет одну линию уровня целевой функции . Задавая числу различные значения, получим семейство параллельных прямых (линий уровня).

Линия уровня, имеющая хотя бы одну общую точку с ОДР, расположенной по одну сторону от неё, называется опорной прямой.

Точка, для которой любой отрезок, содержащий её внутри себя, не принадлежит целиком ОДР, называется угловой точкой.

Нижней и верхней опорными прямыми называются крайние линий уровня целевой функции, имеющие общие точки с ОДР.

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

Из математического анализа известно, что направление наибольшего возрастания функции определяется градиентом этой функции, представляющим собой вектор, координаты которого являются частные производные этой функции:

Этот вектор называют ещё нормальным вектором или просто нормалью.

Очевидно, что направление наибольшего убывания функции определяется вектором противоположным градиенту

который называется антиградиентом.

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

1. Построить ОДР.

2. Построить нормаль вектор .

3. Построить нижнюю и верхнюю опорные прямые .

4. Определить координаты экстремальных точек и вычислить значение целевой функции в них.