Файл: Курс лекций.doc

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

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

- методы выпуклого программирования;

- исследование операций;

- геометрическое программирование и др.

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

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

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

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

2 Методика построения оптимизационной модели

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

Все условия задачи необходимо записать в виде уравнений или неравенств. Поэтому, в первую очередь необходимо опре­делить систему переменных величин, которые могут для конк­ретной задачи обозначить искомый объем производства про­дукции на предприятии, количество перевозимого груза по­ставщиками конкретным потребителям и т. д. Как правило, для обозначения переменных величин используются буквы: х, у, z, а также их модификации. Например, модификация пере­менной х: и т. д. Аналогичные модификации могут быть и для других переменных, используемых в модели. Переменные х₁, х₂, …, х_n могут обозначать объемы производ­ства или реализации продукции соответственно первого, второго и так далее n-го вида. Переменные х_ij могут обозначать объемы производ­ства продукции i-го вида j-м технологическим способом. Для индексации, как правило, используются латинские буквы: i, j, s, l. Количество перемен­ных может обозначаться буквами n, k, m. По каждой перемен­ной для конкретной задачи дается словесное пояснение.

Целевую функцию (цель задачи) чаще всего обозначают буквами f, F, Z. Постоянные величины обычно обозначают бук­вами: а, b, с, d и т. д.

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

Итак, в упрощенном виде экономико-математическая модель представляет собой:

1) систему ограничений - равенства, неравенства вида больше или равно (), меньше или равно ();

2) условия неотрицательности переменных, исходя из экономической или физической сущности переменных (х_j >0), ();

3) целевую функцию.

Математически общую модель задачи можно представить в виде:

найти значения n переменных х₁, х₂, …, х_n, которые удовлетворяют системе ограничений

f_i (х₁, х₂, …, х_n) {<,=,>} b_i () (2.2)

и максимизируют или минимизируют целевую функцию

Z = f (х₁, х₂, …, х_n)  (max/min). (2.3)

Если на переменные налагается условие неотрицательности, тогда в модель задачи вводится условие

(х_j >0), ().(2.4)

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

x_j = 0, или 1, или 2, или 3 и т. д.

3 Основные типы линейных экономико-математических моделей

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

1. модель общей задачи линейного программирования;

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

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

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

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

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

1.1 Модель оптимального планирования товарооборота. Торговое предприятие реализует товары нескольких групп: А, В, С. Для реализации единицы товара группы А затраты рабочего времени составляют a₁₁ чел.-ч., товара группы В – a₁₂ чел.-ч., товара группы С – a₁₃ чел.-ч. Площадь торгового зала, занимаемая единицей товара А, составляет а₂₁ м², товара В – а₂₂ м², товара С – а₂₃ м². Расходы (издержки обращения) при продаже единицы товара группы А составляют а₃₁ ден. ед., группы В – а₃₂ ден. ед., группы С – а₃₃ ден. ед. Известны величины ресурсов: рабочее время – b₁ чел.-час., площадь торгового зала b₂ м², издержки обращения b₃ ден.ед. Доход при реализации единицы товара группы А равен c₁ ден. ед., товара группы В – c₂ ден. ед., товара группы С – c­₃ ден. ед.

Требуется составить экономико-математическую модель задачи, пользуясь которой, можно найти план товарооборота по кри­терию максимума дохода f.

Экономико-математическая постановка задачи. Известно, что величина дохода линейно связана с объемом продажи товаров х₁, х₂ и х₃. В связи с этим целевую функцию можно записать таким образом:

f = (c₁ x₁ + c₂ х₂ + c₃ х₃) → max. (2.5)

Очевидно, что объем продажи товаров не может быть отрицатель­ной величиной. Поэтому x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0. Учитывая нормы за­трат рабочего времени и то, что общие затраты в целом не должны превышать имеющихся ресурсов, запишем следующее ограничение:

_(2.6)

Исходя из торговой площади и общей площади запишем следую­щее ограничение:

_(2.7)

Поскольку известны ограничения по издержкам обращения, запи­шем последнее ограничение

_(2.8)

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

Экономико-математическая постановка задачи. Допустим, имеется набор продуктов: мясо, рыба, молоко, сахар, яйца, картофель, овощи, фрукты, хлеб, мука по цене соответственно: с₁, …, с_n, причем запасы этих продуктов ограничены: а₁, …, а_n.

Содержание питательных веществ – белков, жиров, углеводов, витаминов и минеральных солей – в 1 кг каждого продукта известно и составляет соответственно: q₁₁, q₂₁, …, q_i1, …, q_mn. Кроме того, известны нормы суточной потребности человека в каждом питательном веществе: b₁, b₂, …, b_m.

Перечисленные показатели можно записать в виде системы линейных ограничений:

(2.9)

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

(2.10)

В задаче необходимо определить такое количество закупаемых продуктов, которое бы обеспечило потребность человека в питательных веще­ствах при минимальной стоимости набора и описывалось бы линейной формой связи целевой функции:

. (2.11)