Приложение к главе 5 ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Цели изучения

Изучив данное приложение, вы должны уметь:

1. Описать характер задач, решение которых поддается линейному программированию.

2. Построить модель линейного программирования, исходя из описания проблемы.

3. Решать простые задачи линейного программирования, используя графический метод.

4. Использовать симплексный метод для решения задач линейного программирования.

5. Дать интерпретацию результатов компьютерного решения задач линейного программирования.

6. Выполнить анализ чувствительности решения задач линейного программирования.

Содержание

Введение

Модели линейного программирования

Построение модели Графический метод линейного программирования

Содержание графической процедуры

Построение графика ограничений

Определение области возможных решений

Построение графика целевой функции

Решения и угловые точки

Минимизация

Недостаток и избыток Симплексный метод

Построение начальной таблицы

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

Построение второй таблицы

Построение третьей таблицы

Обработка ограничений типа > и =

Резюме процедуры максимизации

Задачи минимизации

диализ чувствительности Компьютерные решения Ключевые термины Решение задач

Вопросы для обсуждения и повторения Задачи

Избранная библиография

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

Введение

Методы линейного программирования (linear programming - LP) представляют собой последовательность операций, ведущих к оптимальному решению определенного вида задач, в тех случаях когда оптимум существует. Имеется целый ряд различных методов линейного программирования; одни являются специализированными или узконаправленными (т.е. они предназначены для решения определенного класса задач), другие носят более общий характер. Материал данного приложения охватывает два аналитических метода общего назначения: графическое линейное программирование и симплексный метод. Графическоелинейное программирование представляет большой интерес, так как обеспечивает визуальное представление о многих важных концепциях линейного программирования. Однако класс задач, к которым могут быть применены графические методы, ограничен задачами только с двумя переменными. Симплексный метод-это математический подход, который не имеет визуальных характеристик графического метода, но может быть применен к задачам, содержащим более двух переменных и, таким образом, более эффективен для решения реальных задач, которые часто содержат большое число переменных.

Линейные модели программирования используются, чтобы помочь производственному менеджеру в принятии решений во многих различных областях деятельности. Сюда могут относиться; распределение ограниченных ресурсов, проблемы назначения и распределения (например, распределение сотрудников по рабочим местам, распределение рабочих операций по видам оборудования), проблемы транспортировки (например, определение планов отгрузки товаров от различных отправных пунктов в различные пункты назначения - например, от 4 складов до 10 розничных потребителей), определение соотношения компонентов различных смесей (например, нефтепродукты, диеты) и другие задачи. Таким образом, линейное программирование имеет самые широкие области применения. Более того, во всех случаях использование линейного программирования гарантирует оптимальное решение математической модели.

Модели линейного программирования

Модели линейного программирования-это математическое представление проблем оптимизации с ограничениями. Эти модели имеют определенные общие характеристики. Знание этих характеристик позволяет нам распознавать проблемы, которые могут быть рещены с использованием линейного программирования. Кроме того, они также могут помочь при создании модели ЛП. Характеристики могут быть сгруппи-

рованы в две категории: ко!мпоненты и посылки. Давайте сначала рассмотрим компоненты.

Четыре компонента обеспечивают структуру линейной модели программирования;

1. Цель.

2. Переменные решения.

3. Ограничения.

4. Параметры.

Алгоритмы линейного программирования требуют определения единой конечной цели, или перспективы (например, получения максимальной прибыли).

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

Переменные величины в решении являются для принимающего решение вариативными параметрами, в единицах входных или выходных параметров.

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

Ограничения - это ограничение числа возможных вариантов, доступных для принимающего решение.

Эти ограничения бывают трех типов: меньше или равно (<), больше или равно (>) или просто равно (=). Ограничения первого типа устанавливают предельное количество некоторого недостаточного ресурса (на- ,.rf. .с. .1 пример, машинного времени, продолжительности рабочего дня или материалов), доступного для использования. Ограничения второго типа определяют минимум, к которому нужно прийти в окончательном решении (например, напиток должен содержать по крайней мере 10% натурального фруктового сока, при передвижении по скоростному шоссе следует заправляться из расчета не менее 30 миль на галлон горючего). Ограничения третьего типа - самые жесткие, в том смысле, что в процессе решения переменная должна иметь точно указанное значение (например, необходимо произвести 200 единиц изделия А). Модель в линейном программировании может иметь одно или более ограничений. В случае нескольких органичений, все они могут иметь один и тот же тип (например, все<), или различные типы (например, три ограничения типа < и одно >). Существует большое количество вариантов. Взятые вместе, ограничения данной проблемы определяют набор всех осуществимых комбинаций переменных данного решения; этот набор представляет собой область возможных решений.

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

Модель ЛП состоит из математического описания цели и математического описания каждого ограниче- e>.?-i----x.i:--<.:n:~:,.:~.;::.:!--:- :>:-: ния. Эти описания содержат символы (например, xj,

Х2), которые представляют переменные решения, и числовые значения, называемые

! Цель - задача модели ЛП: j J. максимизация или миними- зация. I

Целевая функция - мате- 1, магическое значение соот- 1

ношения прибыли, затрат и , т.п. на единицу продукции 1

или вложений. %

Переменные в решении -

величины входных или выходных параметров.

Ограничения - факторы, которые ограничивают возможные варианты решения.

: Область возможных ре-; шений - набор всех осуще-И ствимых комбинаций пере-J менных решения, как они 2 определены ограничиваю-:i щими факторами.