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

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

Ниже рассматривается задача на ограниченные ресурсы.

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

Таблица 6 – Исходные данные

Характеристика		Продукция		Наличие станков в цехе
		Д1	Д2
Станки	Токарные	1	3	21
	Фрезерные	3	2	21
	Шлифовальные	3	1	18
	Прибыль	30	60
	Количество партий деталей

Сформируем математические соотношения, необходимые для решения задачи.

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

. (28)

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

. (29)

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

Построим графическое изображение системы неравенств (29), для удобства представив ее в форме, аналогичной уравнениям прямой в отрезках:

. (30)

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

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

Представим целевую функцию (1) в форме уравнения прямой с угловым коэффициентом:

.

Обозначим , где - произвольное числовое значение.

Рисунок 25 – Область допустимых решений

Меняя значение , в выражении

можно получить семейство параллельных прямых, называемых линиями уровня. Проведем одну из таких прямых через начало координат (рисунок 26).

Определим вектор градиент линейной функции :

.

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

Рисунок 26 – Нахождение оптимума

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

.

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