Теоретическая часть. «Использование надстроек табличного процессора Excel

Лабораторная работа №3

«Использование надстроек табличного процессора Excel

для решения задач оптимизации»

Цель работы: освоение процедур математического моделирования и оптимизации решений в задачах экономического прогнозирования, планирования, диагностики и управления с использованием табличного процессора Excel

Теоретическая часть

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

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

Линейная математическая модель – модель задачи, в которой требуется найти такие значения переменных Х1, Х2, …, Хn, при которых некоторая линейная функция от этих переменных принимает максимальное (max) или минимальное (min) значение.

Такая линейная функция называется целевой функцией.

F(X) = C1X1+C2 X2 +…+CnXn→ max

или

F(X) = C1X1+C2 X2 +…+CnXn→ min

при выполнении ограничений на переменные Х1, Х2, …, Хn. Ограничения задаются в виде уравнений или неравенств:

А11Х1+А12Х2+…+А1nXn ≥ ≤ B1

А21Х1+А22Х2+…+А2nXn ≥ ≤ B2

……………………………………..

Аp1Х1+Аp2Х2+…+АpnXn ≥ ≤ Bp

Допустимые решения модели – любые значения переменных Х1, Х2, …, Хn, удовлетворяющие ограничениям задачи.

Оптимальное решение модели – допустимые значения переменных Х1, Х2, …, Хn, при которых целевая функция принимает максимальное или минимальное значение.

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

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

Для решения большого круга задач линейного программирования имеется практически универсальный алгоритм - симплексный метод, позволяющий за конечное число итераций находить оптимальное решение подавляющего большинства задач. Тип используемых ограничений (равенства или неравенства) не сказывается на возможности применения указанного алгоритма. Дополнительной проверки на оптимальность для получаемых решений не требуется. Как правило, практические задачи линейного программирования отличаются весьма значительным числом независимых переменных. Поэтому для их решения обычно используют вычислительные машины, необходимая мощность которых определяется размерностью решаемой задачи.

Типовые задачи линейного программирования:

1) «задача о раскрое» - как с наименьшими отходами использовать материал при производстве заданного количества изделий;

2) «задача о смесях» (еще одно название данного типа задач – «задача о рационе») – определение такого рациона, который удовлетворял бы потребностям человека или животного в питательных веществах или минимальной общей стоимости используемых продуктов;

3) «задача о назначениях» - каким образом распределить рабочих по станкам для получения максимальной прибыли от производства;

4) задача об определении оптимального ассортимента – найти такую структуру выпускаемой продукции, чтобы получать максимальную прибыль;

5) транспортная задача – найти такой оптимальный план перевозок, чтобы все заявки были удовлетворены при минимальных затратах на перевозку;

6) построение оптимального портфеля ценных бумаг – получение максимального дохода от вложений в ценные бумаги при минимальном риске.

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

Общая постановка транспортной задачи следующая. Имеются M поставщиков некоторого товара. Количество товара, имеющееся у поставщиков, составляет A ₁, A ₂,..., A_M единиц. Имеются N потребителей этого товара; их спрос составляет B ₁, B ₂,..., B_N единиц. Сумма запасов товара, имеющихся у поставщиков, равна сумме величин спроса всех потребителей:

Известны затраты на перевозку единицы товара от каждого поставщика каждому потребителю (стоимости перевозок): Cij, i = 1,..., M,

j = 1,..., N. Требуется составить оптимальный план перевозок, т.е. определить, сколько товара каждый поставщик должен доставлять каждому из потребителей, чтобы общие затраты на перевозки были минимальными. При этом, конечно, каждому потребителю должно быть доставлено необходимое количество товара.

Рассмотрим пример построения линейной математической модели для решения транспортной задачи.