Введение

Задачи математического программирования

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

Моделирование позволяет из множества вариантов возможных решений выбрать один, и этот выбор должен быть обоснован. Вы уже знакомы с ситуационным моделированием (этому была посвящена 1 часть учебного пособия), сейчас вашему вниманию предлагается еще одна технология системного анализа – математическое моделирование. Умение построить математическую модель задачи в некоторых случаях является единственным способом решить ее.

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

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

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

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

Слово программирование заимствовано из зарубежной литературы, где использовалось в смысле «планирование».

В лабораторных работах мы будем заниматься решением задач линейного программирования, поскольку это наиболее распространенные задачи и для их решения достаточно встроенных возможностей математического моделирования среды Microsoft Excel. Для решения же задач из других разделов математического программирования требуется хорошая математическая подготовка и умение работать в специально ориентированных математических пакетах MathCAD 8 (Maple 6).

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

1. показатель эффективности L представляет собой линейную функцию от элементов решения ;

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

В общей форме записи модель задачи линейного программирования имеет вид:

целевая функция

,

при ограничениях

(1)

Допустимое решение (или план) - это совокупность чисел , удовлетворяющих ограничениям задачи (1).

Оптимальный план - это план , при котором целевая функция принимает свое максимальное (минимальное) значение.

Целевая функция L, максимум (минимум) которой требуется определить, вместе с системой неравенств и условием неотрицательности образуют математическую модель задачи.

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

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

Лабораторная работа 1

Решение типовых задач линейного программирования

С помощью этой лабораторной работы Вы сможете:

• научиться строить математические модели для задач линейного программирования;

• освоить технологию решения типовых задач линейного программирования (ЛП) в табличном редакторе Microsoft Excel.

1. Решение задачи о дневном рационе

   1. Постановка задачи

Для сохранения здоровья и работоспособности человек должен потреблять в сутки определенное количество белков, жиров, углеводов, воды и витаминов (см. табл. 1). Предположим (для простоты решения задачи), что дневной рацион человека составляется из трех продуктов — П₁, П₂, П₃. Стоимость этих продуктов задана в табл. 1. Запасы ингредиентов в различных продуктах различны (см. табл. 1). Следует таким образом определить дневной рацион, чтобы стоимость рациона была наименьшей, но при этом в рационе содержалось необходимое количество питательных веществ.

Таблица 1