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 га.

Требуется составить такой план мероприятий, при котором критерий полезности будет максимальным.

Составим математическую модель задачи. Обозначим неизвестные:

x_1, x₂, x₃, x₄ – объемы мероприятий (га) 1-го – 4-го видов соответственно;

Z – суммарная полезность проведения мероприятий.

Z = 0.6∙x₁+0.7∙x₂+0.6∙x₃+0.5∙x₄ → max (1.7)

Ограничения на материалы:

0.6∙x₁+0.4∙x₂+0.5∙x₃+0.3∙x₄ ≤ 300; (1.8)

0.5∙x₁+0.4∙x₂+0.4∙x₃+0.6∙x₄ ≤ 400; (1.9)

0.5∙x₁+0.4∙x₂+0.6∙x₃+0.5∙x₄ ≤ 500. (1.10)

Ограничение на денежные средства:

40∙x₁+50∙x₂+60∙x₃+40∙x₄ ≤ 26000. (1.11)

Ограничение на объем проведения первого мероприятия.

x₁ ≤ 100. (1.12)

Модель (1.7)-(1.12) относится к математическим моделям линейного программирования.

Задача 1.2. Агро-мелиоративная фирма имеет 1500 га орошаемой пашни; 700000 человеко-часов трудовых ресурсов; дождевальную технику общей производительностью 8000машино-часов рабочего времени за сезон; денежные средства на текущие производственные затраты 650000 денежных единиц (ден. ед.). На участок бригады может быть подано оросительной воды не более 2800 тыс. м³ воды за сезон.

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

Таблица 1.2 – Нормативы затрат и выхода продукции

-------------------------------------------------------------¬

¦Культуры и¦ Нормативы затрат и выхода продукции на 1 га ¦

¦технологии+-------------------------------------------------+

¦их выращи-¦ затраты ¦ затраты ¦ затраты ¦ текущие ¦ выход ¦

¦вания ¦ воды, ¦ труда, ¦ дождева- ¦ затраты,¦ чистого¦

¦ ¦ тыс. м³ ¦ чел.-ч. ¦ льной ¦ ден. ед.¦ дохода,¦

¦ ¦ ¦ ¦ техники ¦ ¦ден. ед.¦

+----------+---------+---------+----------+---------+--------+

¦ОВОЩИ: ¦ ¦ ¦ ¦ ¦ ¦

¦без полива¦ 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 - дополнительный урожай, т; - водоподача на участок в сотнях

тыс. м³.

Цена одной тонны урожая равна 100 ден. ед. Дополнительные затраты, связанные с орошением, в денежных единицах на 1000 м³ по каждому участку соответственно равны 6, 12 и 10. Суммарное количество воды, подаваемой на все три участка, ограничено и равно 37 сотен тысяч м³.

Найти оптимальное распределение воды по участкам. Критерий оптимальности – максимум дополнительного чистого дохода в сумме по трем участкам.

Построим математическую модель задачи. Введем следующие переменные:

количество воды, поданной на первый участок в сотнях тыс. м³;

–количество воды, поданной на второй участок в сотнях тыс. м³;

–количество воды, поданной на третий участок в сотнях тыс. м³.

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

Целевая функция выражает дополнительный чистый доход от орошения участков:

,

. (1.13)

Ограничение на водные ресурсы:

(1.14)

. (1.15)

Задача (1.13)-(1.15) относится к моделям нелинейного программирования.