 |
Математическая формулировка транспортной задачи
|
|
|
|
Лабораторная работа № 13
Решение транспортной задачи средствами Excel
Введение
В различных областях своей деятельности человеку практически ежедневно приходится сталкиваться с проблемой принятия решений для достижения тех или иных целей. В экономике целями могут быть увеличение прибыли, снижение затрат, повышение производительности труда, рациональное использование оборудования, повышение эффективности инвестиций и многие другие. Задача достижения экономических целей приводит к проблеме рационального использования ограниченных ресурсов (материальных, сырьевых, энергетических, финансовых, трудовых и других.) Для решения этой проблемы человеку необходимо принимать определенные решения. Естественно, что в процессе принятия решений человеку, как правило, свойственно стремление выбрать наилучшее для него решение.
В работе рассматриваются практические вопросы, связанные с принятием рациональных решений в экономике на основе использования EXCEL.
Выполнение приводимых заданий, позволит Вам приобрести практические навыки, необходимые для решения на компьютере важных и актуальных экономических задач.
Основные определения
Определение 1. Наилучшее решение, с точки зрения принимающего это решение человека, будем называть оптимальным.
С незапамятных времен человек в процессе принятия решений использовал свой опыт и интуицию.
Для принятия оптимальных решений в современных условиях к опыту и интуиции человека добавляется возможность использования ЭВМ. ЭВМ позволяет в короткий срок обработать большой объем данных, необходимых для принятия решения, выработать рекомендации по принятию оптимального решения, оценить последствия от принимаемого решения, которые могут произойти в будущем.
|
|
|
Следует заметить, что такого рода расчеты ЭВМ может выполнить только с использованием специальных компьютерных программ. Представителем которых является, например, EXCEL [1], реализующая функции электронной таблицы. Среди функций EXCEL имеются математические функции, предназначенные для решения экстремальных задач.
Определение 2. Экстремальная задача – это задача по поиску наилучшего (оптимального) решения из множества (набора) допустимых решений.
Теория и методы решения экстремальной задачи на ЭВМ необходимо средствами математической символики описать заданную цель (например, получение максимальной прибыли), а также запас имеющихся ресурсов и условия их использования для достижения цели. При таком описании выделяют следующие два понятия:
- Математическую модель;
- Целевую функцию.
Определение 3. Математическая модель – это приближенное описание какого-либо класса явлений средствами математической символики. Анализ математической модели дает возможность проникнуть в сущность изучаемых явлений.
Математическая модель экстремальной задачи задает множество допустимых решений Х. Множество Х определяется имеющимися запасами ресурсов и условиями их использования для достижения цели.
В EXCEL множество допустимых решений называют также ограничениями задачи.
Определение 4. Целевая функция представляет собой числовую характеристику, большему или меньшему значению которой соответствует лучшее решение, с точки зрения принимающего это решение человека. Будем обозначать целевую функцию через f(x), где 
Определение 5. Вектор 
, где а Х- множество допустимых решений будем называть решением экстремальной задачи.
Математическая формулировка транспортной задачи
Одним из примеров экстремальной задачи может служить задача максимизации прибыли предприятия в условиях ограниченных ресурсов. Пусть некоторое предприятие, применяя имеющуюся технологию, может выпускать n видов продукции, используя m видов ресурсов. Целью предприятия является получение максимальной прибыли.
|
|
|
Построим математическую модель и целевую функцию для решения задачи определения наиболее прибыльного объема выпуска продукции. То есть такого объема, который может обеспечить предприятию получение максимальной прибыли.
Для построения математической модели введем следующие обозначения. Обозначим через 
количество выпускаемой продукции j-го вида. Тогда объем всей выпускаемой продукции можно обозначить с помощью вектора Обозначим через 
запас i-го вида ресурса, имеющийся на предприятии, а через 
- количество i-го ресурса, необходимого для выпуска продукции, определяемой вектором х.
Заметим, что функция 
, как правило, определяются используемой на предприятии технологией.
Очевидно, что выпуск продукции будет ограничен имеющимися запасами ресурсов. Математически эти ограничения можно записать в следующем виде:
(1)
Обозначим через 
верхние ограничения, обусловленные спросом, на продукцию j-го вида, а через 
, нижние ограничения обусловлены спросом, на ту же продукцию. Очевидно, что выпуск продукции должен удовлетворять условиям спроса. Математически эти условия можно записать следующим образом:
(2)
Естественно также, что выпуск продукции удовлетворяет условиям неотрицательности, а именно:
(3)
Обозначим через f(x) прибыль, получаемую предприятием от реализации продукции. Тогда задача определения объема выпуска продукции, обеспечивающего предприятию максимальную прибыль, может быть записана следующим образом.
Найти
max f(x) (4)
при условии (1), (2), (3).
При этом функция f(x) называется целевой функцией, вектор х – вектором переменных, система неравенств (1), (2), (3) представляет собой математическую модель задачи. Иногда систему неравенств вида (1)-(3) называют также задачей математического программирования или задачей оптимизации.
Дадим интерпретацию экстремальной задачи (4), (1)-(3) как задачи принятия решения. Компоненты вектора переменных моделируют принятие конкретного решения. Целевая функция f(x) моделирует эффективность принимаемого решения. Ограничения (1)-(3) задачи моделируют связи, накладываемые на компоненты вектора переменных способами использования ресурсов.
|
|
|
В общем случае экстремальную задачу можно определить, например, следующим образом.
Дано множество Х и функция f(x), определенная на множестве Х. Требуется найти (если они существуют) точки максимума или минимума функции f(x) на множестве Х. Условимся записывать задачу максимизации функции f(x) на множестве Х следующим образом:
max f(x) (5)
При этом функцию f(x) будем по-прежнему называть целевой функцией, вектор х - вектором переменных, множество Х будем называть множеством допустимых решений.
Множество Х определяется неравенствами (1), (2), (3).
Конкретизируем рассмотренную выше задачу.
|
|
|
