Линейное программирование. Некоторые примеры экономических задач, приводящих к модели линейного программирования. Геометрическая интерпретация и графическое решение задачи ЛП, страница 6

     Графический метод решения задач ЛП с  n = 3 переменными используется очень редко, так как соответствующие построения в пространстве значительно сложнее и менее наглядны, чем на плоскости (при n = 2). При n>3 наглядность пропадает совсем. Тем не менее с помощью геометрической интерпретации удалось разработать методы решения  задач ЛП в общем случае. При  n = 2  и  n = 3 из геометрических соображений очевидно, что для решения задачи ЛП достаточно найти все оптимальные среди конечного числа планов, соответствующих вершинам многоугольной (многогранной) области допустимых планов.

      При n > 3 роль вершин играют  опорные планы, которые определяются  аналитически, на языке уравнений и неравенств, по аналогии с аналитическим описанием вершин при  n = 2  и  n = 3 (см. упр.11). Основная идея решения задач ЛП симплекс-методом, который будет изложен ниже, заключается в целенаправленном переборе (последовательном улучшении) опорных планов.

     Замечание. В п. 2 показано, что исключение ограничений-равенств в общей задаче  ЛП  с  n   переменными  сводит  ее  к задаче   ЛП  с        переменными,

где  r - ранг, т. е. число независимых уравнений системы всех ограничений–равенств. Поэтому общая задача ЛП, в которой  , сводится к задаче вида (23)-(24) и, следовательно, допускает графическое решение.

Упражнения

4.  Каждая из деталей А и В должна пройти обработку на каждом из трех станков. Затраты времени на обработку одной детали  и максимальное допустимое время работы каждого из станков заданы в таблице:

Деталей А требуется произвести не менее 300, деталей В не более 200. Прибыль при реализации детали А составляет 10 руб., детали В – 16 руб. Определить производственную программу, максимизирующую прибыль.

5.  На мебельной фабрике из стандартных листов фанеры вырезаются заготовки трех типов А, В, С. Используются два способа раскроя листа. Количество получаемых из одного листа заготовок и отходы для каждого способа раскроя, а также минимальная потребность в заготовках заданы в таблице:

Как получить необходимое количество заготовок типов А, В, С с минимальными отходами?

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

      Сколько лисиц и песцов надо содержать на ферме для получения  максимальной прибыли?