Теоретическое обоснование. Решение задачи линейного программирования в MS Excel

Лаб. Раб. №14

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

1. Цель и содержание: изучение методики решения задачи линейного программирования с использованием табличного процессора Excel.

Теоретическое обоснование

2.1. Постановка задачи линейного программирования. Задача линейного программирования является достаточно распространенной задачей принятия оптимальных решений, особенно в экономике. Решение этой задачи рассмотрим на примере задачи распределения ресурсов.

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

(1)

где F – функция цели;

– количество выпускаемой продукции j -го типа;

– количество располагаемого ресурса i- говида;

– норма расхода i- го ресурса для выпуска единицы продукции j -го типа;

– прибыль, получаемая от реализации единицы продукции j -го типа.

2.1.1. Задача распределения ресурсов. Частным случаем задачи линейного программирования является задача распределения ресурсов. Если финансы, оборудование, сырье и даже людей считать ресурсами, то значительное число задач в экономике можно рассматривать как задачи распределения ресурсов. Достаточно часто математической моделью таких задач является задача линейного программирования.

Рассмотрим следующий пример.

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

Таблица 1

Как видно из таблицы 1, для выпуска единицы Прод1 требуется
6 единиц сырья, значит, для выпуска всей продукции Прод1 требуется 6 x₁ единиц сырья, где x₁ – количество выпускаемой продукции Прод1. С учетом того, что для других видов продукции зависимости аналогичны, ограничение по сырью будет иметь вид:

(2)

В этом ограничении левая часть равна величине требующегося ресурса, а правая показывает количество имеющегося ресурса.

(3)

Аналогично можно составить ограничения для остальных ресурсов и написать зависимость для целевой функции. Тогда математическая модель задачи будет иметь вид: (3).

Аналитическое решение задачи линейного программирования осуществляется с помощью симплекс-метода. В Excel имеется математический аппарат, реализующий основные идеи данного метода. Решение задачи с помощью Excel будем рассматривать на примере задачи, математическая модель которой имеет вид (3).