- •Экономико-математические методы
- •1 Общая задача математического
- •1.1 Модель математического программирования
- •1.2 Математическая формулировка задач линейного
- •1.3 Примеры построения простейших моделей математического
- •1.4 Геометрическая интерпретация задач линейного
- •1.4.1 Графический метод решения
- •1.4.2 Схема решения задачи графическим методом
- •1.4.3 Особые случаи решения задач линейного
- •1.5 Контрольные вопросы к разделу 1
- •2 Симплекс-метод решения задач линейного
- •2.1 Симметричный симплекс-метод
- •2.2 Экономический анализ оптимального плана по последней
- •2.3 Симплекс-метод с искусственным базисом
- •2.4. Схема решения задач линейного программирования
- •2.5. Особые случаи при решении задач симплекс-методом
- •2.6 Контрольные вопросы к разделу 2
- •3 Двойственные задачи линейного
- •3.1 Понятие о двойственных задачах
- •3.2 Теоремы двойственности в линейном программировании
- •3.3 Экономическая интерпретация двойственных задач
- •3.4. Примеры построения двойственных задач
- •3.5 Контрольные вопросы к разделу 3
- •4 Транспортная задача линейного
- •4.1 Математическая постановка транспортной задачи
- •4.2 Метод потенциалов решения транспортной задачи
- •Числаui являются потенциалами строк, аvj – потенциалами столбцов. Из теоремы следует, что для того, чтобы план был оптимальным, необходимо выполнение следующих условий:
- •Если хотя бы одна незанятая клетка не удовлетворяет условию (б), то план не оптимален.
- •4.3 Схема решения транспортной задачи
- •4.4 Контрольные вопросы к разделу 4
- •5 Методы решения задач нелинейного
- •5.1 Классификация задач математического программирования
- •5.2 Метод Лагранжа
- •5.3 Метод динамического программирования
- •5.4 Применение динамического программирования для решения задач о замене оборудования и эффективного использования
- •5.5 Контрольные вопросы к разделу 5
- •6 Наиболее распространенные модели
- •Содержание
- •Литература
- •Экономико-математические методы Учебное пособие
1 Общая задача математического
ПРОГРАММИРОВАНИЯ
1.1 Модель математического программирования
Модель общей задачи математического программирования состоит из целевой функции (1.1) и ряда ограничений (1.2-1.3):
(1.1)
(1.2)
, (1.3)
где – известные функции,
а – заданные коэффициенты.
Функция выражает в аналитической форме критерий экономической эффективности в зависимости от планируемых параметров производства и называетсяцелевой функциейиликритерием оптимальности.
Ограничения (1.2) называются технологическими; их правые части представляют собой фиксированные объемы имеющихся в распоряжении ресурсов.
Значения , удовлетворяющие ограничениям (1.2-1.3), называются допустимым планом.
Решение задачи математического программирования называется оптимальным планом. Это такой набор значений, при котором выполняются ограничения (1.2-1.3) и целевая функция (1.1) принимает максимальное значение.
Задача минимизации целевой функции может быть сведена к решению задачи нахождения ее максимума, так как
.
Часто в задачах, возникающих на практике, система технологических ограничений (1.2), содержит, кроме неравенств со знаком «≤», равенства и неравенства «≥». Однако это не сказывается на общности постановки задачи (1.1-1.3), поскольку такие ограничения легко преобразуются в стандартный вид вычитанием из левых частей дополнительных неотрицательных переменных.
В зависимости от вида функций задачи математического программирования делятся на две большие группы – линейные и нелинейные. Если хотя бы одна из функций, входящих в математическую модель нелинейна, то задача относится к нелинейному программированию.
1.2 Математическая формулировка задач линейного
программирования
Если в задаче (1.1-1.3) функциилинейны, она относится к классу линейного программирования. Математическая модель линейного программирования имеет вид:
(1.4)
(1.5)
(1.6)
Коэффициенты и матрицазаданы.
Требуется определить оптимальные значения , т.е. такие, при которых целевая функция (1.4) максимальная и выполняются ограничения (1.5)-(1.6).
1.3 Примеры построения простейших моделей математического
программирования
Задача 1.1 На участке лесо-паркового массива города требуется выполнить четыре вида мероприятий. Для их проведения используются три вида материалов и денежные средства. Затраты ресурсов на 1 га проведения мероприятий и коэффициенты относительной полезности мероприятий приведены в таблице 1.1.
Таблица 1.1 – Удельные затраты ресурсов на проведение мероприятий
Ресурсы |
Объем ресурсов |
Мероприятие 1 |
Мероприятие 2 |
Мероприятие 3 |
Мероприятие 4 |
Материалы 1 |
300 |
0,6 |
0,4 |
0,5 |
0,3 |
Материалы 2 |
400 |
0,5 |
0,4 |
0,4 |
0,6 |
Материалы 3 |
500 |
0,5 |
0,4 |
0,6 |
0,5 |
Денежные средства |
26000 |
40 |
50 |
60 |
40 |
Коэффициенты полезности |
– |
0,6 |
0,7 |
0,6 |
0,5 |
Максимально допустимый объем первого мероприятия равен 100 га.
Требуется составить такой план мероприятий, при котором критерий полезности будет максимальным.
Составим математическую модель задачи. Обозначим неизвестные:
x1, x2, x3, x4 – объемы мероприятий (га) 1-го – 4-го видов соответственно;
Z – суммарная полезность проведения мероприятий.
Z = 0.6∙x1+0.7∙x2+0.6∙x3+0.5∙x4 → max (1.7)
Ограничения на материалы:
0.6∙x1+0.4∙x2+0.5∙x3+0.3∙x4 ≤ 300; (1.8)
0.5∙x1+0.4∙x2+0.4∙x3+0.6∙x4 ≤ 400; (1.9)
0.5∙x1+0.4∙x2+0.6∙x3+0.5∙x4 ≤ 500. (1.10)
Ограничение на денежные средства:
40∙x1+50∙x2+60∙x3+40∙x4 ≤ 26000. (1.11)
Ограничение на объем проведения первого мероприятия.
x1 ≤ 100. (1.12)
Модель (1.7)-(1.12) относится к математическим моделям линейного программирования.
Задача 1.2. Агро-мелиоративная фирма имеет 1500 га орошаемой пашни; 700000 человеко-часов трудовых ресурсов; дождевальную технику общей производительностью 8000машино-часов рабочего времени за сезон; денежные средства на текущие производственные затраты 650000 денежных единиц (ден. ед.). На участок бригады может быть подано оросительной воды не более 2800 тыс. м3 воды за сезон.
В таблице 1.2 даны характеристики вариантов технологии выращивания культур на орошаемом массиве бригады: затраты и выход чистого дохода на 1 га овощей, кукурузы на зерно и сахарной свеклы.
Таблица 1.2 – Нормативы затрат и выхода продукции
-------------------------------------------------------------¬
¦Культуры и¦ Нормативы затрат и выхода продукции на 1 га ¦
¦технологии+-------------------------------------------------+
¦их выращи-¦ затраты ¦ затраты ¦ затраты ¦ текущие ¦ выход ¦
¦вания ¦ воды, ¦ труда, ¦ дождева- ¦ затраты,¦ чистого¦
¦ ¦ тыс. м3 ¦ чел.-ч. ¦ льной ¦ ден. ед.¦ дохода,¦
¦ ¦ ¦ ¦ техники ¦ ¦ден. ед.¦
+----------+---------+---------+----------+---------+--------+
¦ОВОЩИ: ¦ ¦ ¦ ¦ ¦ ¦
¦без полива¦ 0 ¦ 300 ¦ 0 ¦ 600 ¦ 200 ¦
¦2 полива ¦ 2 ¦ 320 ¦ 6 ¦ 600 ¦ 450 ¦
¦КУКУРУЗА ¦ ¦ ¦ ¦ ¦ ¦
¦НА ЗЕРНО: ¦ ¦ ¦ ¦ ¦ ¦
¦1 полив ¦ 0,8 ¦ 80 ¦ 2 ¦ 230 ¦ 300 ¦
¦2 полива ¦ 1,6 ¦ 90 ¦ 4 ¦ 260 ¦ 350 ¦
¦САХАРНАЯ ¦ ¦ ¦ ¦ ¦ ¦
¦СВЕКЛА: ¦ ¦ ¦ ¦ ¦ ¦
¦1 полив ¦ 1 ¦ 210 ¦ 3 ¦ 330 ¦ 250 ¦
¦3 полива ¦ 3,5 ¦ 225 ¦ 8 ¦ 400 ¦ 400 ¦
+----------+---------+---------+----------+---------+---------
Необходимо определить такую структуру посевных площадей на орошаемом массиве и выбрать такие варианты технологии выращивания культур, при которых фирма, используя свои ресурсы, получит максимум чистого дохода.
Запишем математическую модель задачи.
x1 - площадь (га) овощей без полива;
x2 - площадь (га) овощей с двумя поливами;
x3 - площадь (га) кукурузы с одним поливом;
x4 - площадь (га) кукурузы с двумя поливами;
x5 - площадь (га) свеклы с одним поливом;
x6 - площадь (га) свеклы с тремя поливами;
Целевая функция имеет смысл чистого дохода.
max Z= 200∙x1 + 450∙x2 + 300∙x3 + 350∙x4 + 350∙x5 + 400∙x6.
Огpаничения:
- на площадь пашни
x1 + x2 + x3 + x4 + x5 + x6 ≤ 1500;
- на трудовые ресурсы
300∙x1 + 320∙x2 + 80∙x3 + 90∙x4 + 210∙x5 + 225∙x6 ≤ 700000;
- на затраты времени дождевальной техникой
0∙x1 + 6∙x2 + 2∙x3 + 4∙x4 + 3∙x5 + 8∙x6 ≤ 8000;
- на текущие затраты
600∙x1 + 600∙x2 + 230∙x3 +260∙x4 + 330∙x5 + 400∙x6 ≤ 650000;
- на затраты воды
2∙x2+ 0.8∙x3 +1.6∙x4 + x5 + 3.5∙x6 ≤ 2800.
Получена математическая модель линейного программирования.
Задача 1.3. Имеется три орошаемых участка площадью по 100га, разные по производственным характеристикам. Для каждого участка задана функция дополнительного урожая от объема подаваемой оросительной воды:
,
,
,
где уi - дополнительный урожай, т; - водоподача на участок в сотнях
тыс. м3.
Цена одной тонны урожая равна 100 ден. ед. Дополнительные затраты, связанные с орошением, в денежных единицах на 1000 м3 по каждому участку соответственно равны 6, 12 и 10. Суммарное количество воды, подаваемой на все три участка, ограничено и равно 37 сотен тысяч м3.
Найти оптимальное распределение воды по участкам. Критерий оптимальности – максимум дополнительного чистого дохода в сумме по трем участкам.
Построим математическую модель задачи. Введем следующие переменные:
количество воды, поданной на первый участок в сотнях тыс. м3;
–количество воды, поданной на второй участок в сотнях тыс. м3;
–количество воды, поданной на третий участок в сотнях тыс. м3.
Выпишем математическую модель оптимизации водораспределения с учетом дополнительных затрат, связанных с орошением.
Целевая функция выражает дополнительный чистый доход от орошения участков:
,
. (1.13)
Ограничение на водные ресурсы:
(1.14)
. (1.15)
Задача (1.13)-(1.15) относится к моделям нелинейного программирования.