16.2. Этапы решения проблемы линейного программирования

Проблема линейного программирования решается в три этапа:

1. Определение цели. Целевая функция выражает определенную цель, которая должна быть максимизирована (например, операционная прибыль) или минимизирована (например, операционные затраты).

2. Определение основных взаимосвязей. Эти взаимосвязи вклю­чают ограничения, выраженные как линейные функции. Ограничение — это математическое неравенство (или равенство), которому должны удовлетворять все переменные в математической модели.

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

На данных нашего примера опишем три этапа решения проблемы ЛП. Напомним, что А — это количество произведенных моторов для снегохо­дов, а В — количество произведенных лодочных моторов.

Этап 1. Определение цели. Главная цель — найти комбинацию продуктов, которая максимизирует суммарную маржинальную прибыль. Линейная функция, которая выражает эту цель, такая:

суммарная маржинальная прибыль = 200 ДЕ • А + 250 ДЕ • В.

Этап 2. Определение основных взаимосвязей. Взаимосвязи мо­гут быть описаны неравенствами:

ограничение по цеху 1 (сборка) 1.5 • А + 2,0 • В ≤ 300;

ограничение по цеху 2 (контроль и испытание) 1,0 • А+0,5 • В ≤ 120;

ограничение из-за недостатка материалов

для изделия В В ≤ 126;

Так как отрицательное производство невозможно, A ≥ 0 и В ≥ 0.

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

Линейное программирование — графическое решение

Этап 3. Нахождение оптимального решения. Для нахождения оптимального решения рассмотрим метод проб и ошибок, а затем гра­фический метод.