Задача о наилучшем использовании ресурсов

Постановка задачи. Фермер выращивает две культуры Х и Y на площади 160 га. Ему необходимо распределить землю, людей и технику таким образом, чтобы прибыль от реализации урожая названных культур была максимальной. В процессе выращивания каждой из культур необходимо выполнять три операции - вспашку, сев и уборку. В таблице 8.2 эти операции и время, необходимое для их выполнения, даны в привязке к четырем разным периодам производства; там же указано время в пределах каждого из периодов, которое может быть использовано в этих целях.

 

Таблица 8.3- К задаче распределения ресурсов при выращивании двух культур.

 

Пусть x₃ и x₄ обозначают площади, выделенные под культуру X, которые убирают в периоды 3 и 4 соответственно, и пусть y есть площадь, выделенная под культуру Y. Площади, выделяемые под каждую из культур, ограничены общей площадью угодий, то есть

. (8.31)

Для уборки каждой культуры может быть использован самоходный комбайн одного и того же типа. Пусть b_k есть число комбайнов, необходимое для уборки. Это число может быть только целым и неотрицательным. Сформулируем ограничения по общим затратам техники на уборку:

период 3: ; (8.32)

период 4: .

Пусть для вспашки, сева и уборки необходим трактор. Пусть b_t есть неотрицательная целочисленная переменная, обозначающая потребность в тракторах. Тогда

период 1: ≤ 5 * b_t; (8.33)

период 2: ;

период 3: _t;

период 4: .

Потребности в трудовых ресурсах рассчитывается следующим образом. Во время вспашки и сева требуется один человек для управления трактором. Чтобы убрать культуру X, требуется два человека для управления комбайном и один - для управления трактором. Во время уборки культуры Y требуется по одному человеку для управления комбайном и трактором. Пусть b_l есть целочисленная переменная, обозначающая полную потребность в людях. Тогда ограничения по труду (в чел.* ч) можно сформулировать следующим образом:

период 1: ≤ 5 * b_t; (8.34)

период 2: ;

период 3: _t;

период 4: .

Культуру Y можно выращивать на одном и том же поле только один год из двух, а культуру X — два года из трех. Фермер намерен выращивать их ежегодно и поэтому должен предусмотреть в своих планах севооборот. Это можно сделать с помощью ограничений:

(8.35)

Доход, получаемый от культур X и Y, равен 2 и 4 ед/га. Соответствующие ежегодные затраты труда, комбайнов и тракторов равны 15 ед/чел., 3 ед/маш. и 1,5 ед/маш. Целевая функция (функция полезности, доход) F, ед/год, которую необходимо максимизировать, имеет вид

_. (8.36)

Таким образом, задача формализуется по схеме частично-целочисленного линейного программирования, имеет шесть управляемых переменных (x₃, x₄,y, b_l, b_k., b_t) и ограничений (уравнения 8.31 ….8.35):

максимизировать

_. (8.37)

с учетом ограничений:

b_l ≥ 0, b_k. ≥ 0, b_t ≥ 0 - целые числа.

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

F = 204, x₃ = 80, x₄ =0, y = 80, b_l = 16, b_k. = 8, b_t = 8.

 

Транспортная задача

 

Постановка задачи. Пусть имеется m поставщиков некоторой однородной продукции. Считается, что i - ый поставщик располагает a_i единицами продукции, i = 1, 2, …, m. Продукцию поставщиков используют n потребителей, потребности которых равны b₁, b₂ , …, b_n единиц продукции. Все числа a_i и b_j положительны. Кроме того, известна стоимость перевозки единицы продукции от i -го поставщика j -ому потребителю: c_ij, i = 1, 2, …, m; j = 1, 2, …, n. Продукция однородна, поэтому любой поставщик может предложить ее любому потребителю, рис.8.10. Требуется определить такое количество единиц продукции, перевозимой от каждого поставщика к каждому потребителю, чтобы транспортные расходы были минимальны и потребности всех потребителей были удовлетворены. Задача предполагается разрешимой в том смысле, что общий объем поставок должен быть не меньше общего объема потребностей.

Обозначим через x_ij число единиц продукции, перевозимой от i- го поставщика j -ому потребителю. Тогда транспортные расходы этой пары поставщик- потребитель составят c_ij*x_ij, а общая стоимость всех перевозок (от каждого поставщика каждому потребителю) равна:

. (8.38)

 

Тот факт, что потребности каждого потребителя должны быть полностью удовлетворены запишем в виде неравенства:

(8.39)

Условие осуществимости поставок, наличия продукции у поставщика выполняется неравенством:

(8.40)

^j

 

Рис.8.10- Поставщики и потребители продукции.

 

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

 

(8.41)

x_ij ≥ 0, i = 1, 2, … n; j = 1, 2, …m.

В этой задаче m*n переменных и m+n ограничений (не считая условий неотрицательности пременных).

Если суммарные возможности поставок совпадают с требуемой суммарной потребностью

(8.42)

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

Если

(8.43)

то спрос потребителей будет удовлетворен, но у поставщиков останется лишняя продукция.

Случай

(8.44)

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

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

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

В районе имеются два склада зерна (два хозяйства по производству зерна) и два элеватора. Ежедневно с первого склада вывозят 50 т зерна, а со второго - 70 т на элеваторы, причем на первый - 40 т, а на второй - 80 т. Обозначим через с_ij стоимость перевозки 1 т зерна с i- го склада на j -й элеватор (i, j = 1,2). Пусть

с₁₁ = 1,2, с₁₂ = 1,6, с₂₁ = 0,8, с₂₂ = 1.0.

Как нужно спланировать перевозки, чтобы их стоимость была минимальной?

Придадим задаче математическую формулировку. Обозначим через x₁ и x₂ количество зерна, которое надо перевезти с первого склада на первый и второй элеваторы, а через x₃ и x₄ - со второго склада на первый и второй элеваторы соответственно. Тогда:

x₁ + x₂ = 50,

x₃ + x₄ = 70,

x₁ + x₃ = 40,

x₂ + x₄ = 80. (8.45)

Общая стоимость всех перевозок определяется формулой:

F = 1,2x₁ + 1,6x₂ + 0,8x₃ + x_4.

С математической точки зрения, задача заключается в том, чтобы найти четыре числа x₁, x₂, x₃ и x₄, удовлетворяющие всем заданным условиям и дающие минимум функции F. Решим систему уравнений (8.45) относительно x_i (i = 1, 2, 3, 4) методом исключения неизвестных. Получим, что

x₁ = x₄ – 30,

x₂ = 80 – x₄,

x₃ = 70 – x₄,

а x₄ не может быть определено однозначно. Так как x_i > 0 (i = 1, 2, 3, 4), то из вышеприведенных уравнений следует, что 30 < x₄ < 70. Подставляя выражение для x₁, x₂, x₃ в формулу для F, получим:

F = 148 – 0.2x₄ .

Минимум этой функции достигается при максимально возможном значении x₄ = 70. Соответствующие значения других неизвестных составят: x₁ = 40, x₂ = 10, x₃ = 0.

Контрольные вопросы к главе 8

1. Дайте определение временного ряда.

2. Назовите этапы этапы анализа временного ряда при прогнозировании.

3. Для чего при анализе временного ряда используют его тренд?

4. Какие виды уравнений используют для аналитической модели полета зерна?

5. Как решаются системы неоднородных дифференциальных уравнений?

6. Дайте определение методу моделирования, использующего линейное программирование.

7. Перечислите типы задач, решаемые с помощью линейного программирования.

8. Дакйте определение целевой функции в задаче линейного программирования.

9. В чем назначения ограничений и условий при решении задач линейного программировыания?

10. Назовите оператор в Matlab, с помощью которого можно существляют решение задачи линейного программирования.

11. Каким образом задачу на максимум целевой функции превратить на ее минимум.

 

 

Источники информации к главе 8

1. Каюмов М.К. Программирование урожаев сельскохозяйственных культур. – М.: Агропромиздат, 1988.- 320 с.:ил.

2. Мухин О.И.

3. Иозайтис В.С., Львов Ю.С. Экономико-математическое моделирование производственных систем: Учебное пособие для инженерно-экономических спец. вузов.- М.: Высш. шк., 1988.- 192 с.: ил.

4. Орлов А.И. Прикладная статистика М.: Издательство «Экзамен», 2004.

5. Рыжиков Ю.И. Имитационное моделирование. Теория и технология.- СПб.: КОРОНА принт; М.: Альтекс- А, 2004.- 384 с., ил.

6. Тихонов А.И., Кальнер Н.К., Класко П.М. Математическое моделирование технологических процессов. Минск: Наука и техника, 1980, - 256 с.

7. Трахтенгерц Э.Л. Компьютерная поддержка принятия решений. М., Синтэг, 1988.

8. Франс Дж., Торнли Дж.Х.М. Математические модели в сельском хозяйстве/ Пер. с англ. А.С.Каменского; под ред.Ф.И.Ерешко. Предисл.Ф.И.Ерешко и А.С. Каменского.- М.: Агропромиздат, 1987.400 с.