Избранные разделы высшей математики

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

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

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

В общем виде постановка экстремальной задачи состоит в определении наибольшего или наименьшего значения целевой функции F (X) = F (x₁,…, x_n) при условии, что ее переменные x₁,.

…, x_n удовлетворяют системе неравенств и уравнений:

здесь F (x₁,., x_n) и g_i(x₁,., x_n) — известные функции n переменных, bi — заданные числа.

Указанная система неравенств и уравнений определяет некоторую область D в n-мерном пространстве Rⁿ. Среди точек M (x₁,…, x_n) этой области D и ищется экстремальное значение функции F (x₁, x₂,., x_n).

Если F (x₁,…, x_n), g_i(x₁,…, x_n) — линейные функции, то получаем задачу линейного программирования.

Если F (x₁,…, x_n), g_i(x₁,…, x_n) (i = 1,…, m) — нелинейные функции, то получаем задачу нелинейного программирования.

Основные понятия линейного программирования

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

F (X) = ад + c2x2 +. + cnxn (6.2).

при условиях:

где а_i j, bi, cj — заданные постоянные величины, x = (х_ь х2,. xn).

Система неравенств (6.3) определяет некоторое множество, на котором и ищется максимальное (или минимальное) значение F (X).

Функция F (X) — целевая функция, условия (6.3) — ограничения данной задачи.

Совокупность точек Х = (x₁, x₂,…, x_n), удовлетворяющих ограничениям (6.3) задачи ЛП, называется допустимым решением (или планом).

План X* = (x₁, x₂,…, x_n), при котором целевая функция принимает свое максимальное (или минимальное) значение, называется оптимальным. То есть F (X*) > F (X) (при поиске минимального значения целевой функции F (X*) < F (X)).

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

Вершину многогранника решений, в которой целевая функция принимает максимальное значение, найти сравнительно просто, если задача содержит не более двух-трех свободных переменных, т. е. n-r < 2−3, где n — число переменных, г — ранг матрицы А.

Например, найдем решение задачи, состоящей в определении максимального значения функции Б (х_ь х2) = 01×1 + С2×2 (6.4).

при условиях:

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

^ai1 x1 + ai2 x2 = bi, x1 = 0, x2 = 0. (6.6).

В том случае если система неравенств (6.5) совместна, область ее решений есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей выпуклое, то областью допустимых решений задачи (6.5) является выпуклое множество, которое называется многоугольником решений (рис. 6.1). Стороны этого многоугольника лежат на прямых (6.6).

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

Для геометрической интерпретации этого объяснения построим линию уровня С1Х1 + c₂x₂ = h, где h — некоторая постоянная. Пусть эта линия пересекает многоугольник решений и передвигается в направлении вектора C (c₁, c₂) до тех пор, пока она не пройдет через последнюю точку многоугольника решений (см. рис. 6.1).

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

Нахождение минимального значения линейной функции при данной системе ограничений отличается от нахождения ее максимального значения при тех же ограничениях лишь тем, что линия уровня c₁x₁ + с₂х₂ = h передвигается не в направлении вектора С = (c₁, с₂), а в противоположном направлении.

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

• 1. Проведение прямых, уравнения которых получаются в результате замены в ограничениях (6.5) знаков неравенства на знаки точных равенств (6.6).
• 2. Нахождение полуплоскостей, определяемых каждым из ограничений.
• 3. Нахождение многоугольника решений.
• 4. Построение вектора С (с₁, с₂).
• 5. Построение прямой c₁x₁ + с₂х₂ = h, проходящей через многогранник решений.
• 6. Передвижение прямой c₁x₁ + с₂х₂ = h в направлении вектора С. В результате необходимо найти точку (линию), в которой целевая функция принимает максимальное значение, либо установить неограниченность сверху функции на множестве планов.
• 7. Определение координат точки максимума функции и вычисление значения целевой функции в этой точке.

ПРИМЕР 1.

Для производства мороженого и шербета небольшому цеху требуются молоко и сахар.

Нормы расхода продуктов для производства 1 порции мороженого или шербета представлены в таблице.

Найти количество порций мороженого x^ шербета x₂, выпуск и реализация которых обеспечат максимальную прибыль цеху.

Решение.

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

найти MAX (lx₁ + 1,2х₂) при ограничениях:

• 0,15 * x₁ + 0,05 * x₂ < 50;
• 0,1 * x₁ + 0,15 * x₂ < 60.

Решение задачи представлено на рисунке ниже.

Графическое решение задачи дает x₁ = 260, x₂ = 220.

СИМПЛЕКС-МЕТОД Одним из основных методов решения задачи ЛП является симплекс-метод. Метод основан на том, что решением задачи ЛП является одна из вершин выпуклого многогранника (оптимальный опорный план). Следовательно, решение задачи ЛП следует искать среди вершин этого многогранника решений.

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

Пусть на первом этапе выбрана вершина В_к (координаты которой называются базисным решением задачи). Тогда переход из вершины В_к в соседнюю вершину выбирают в направлении того из ребер, выходящих из В_к, вдоль которого целевая функция F (x) быстрее всего возрастает. Например, если функция F (x) быстрее всего возрастает вдоль ребра В_к В_к+1, то переход осуществляется в вершину В_к+1, и на следующем этапе рассматривается значение функции в этой вершине (рис. 6.2).

Рис. 6.2 Геометрическая интерпретация симплексметода

Алгоритм продолжается до определения вершины В*, координаты которой и являются решением задачи ЛП: F (B*) > F (B).

ТРАНСПОРТНАЯ ЗАДА ЧА Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления A₁, A₂,…, A_m в n пунктов назначения В₁, B₂,…, B_n.

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

Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок груза. Обозначим через Су тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через ai — запасы груза в i-м складе, через bj — потребности в грузе в j-м пункте назначения. Пусть также Ху — количество груза, перевозимого из iго склада в j-й пункт назначения (рис. 6.3).

Пункты отправления груза.

Тогда математическая формулировка транспортной задачи состоит в определении минимального значения функции Всякое неотрицательное решение системы линейных уравнений (6.8), определяемое матрицей Х = (xij), называется планом транспортной задачи. План X*, при котором функция (6.7) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные транспортной задачи записываются в виде следующей таблицы.

Таблица 6.1.

Очевидно, что общее количество груза у поставщиков Ј ^ai,.

а общая потребность в этом грузе в пунктах назначения Ј bi.

Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т. е.

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

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

ТЕОРЕМА Для разрешимости транспортной задачи необходимо, чтобы запасы груза на складах были равны потребностям в грузе в пунктах назначения.

Замечание. В случае превышения запасов над потребностью вводится фиктивный (п+1)-й пункт назначения, потребности которого полностью «закрывали» бы транспортную задачу, а соответствующие тарифы в этот пункт назначения считались бы равными нулю.

В случае превышения потребностей над запасами вводится фиктивный склад с запасами, покрывающими потребности потребителей. Тарифы по поставкам груза с этого склада считываются равными нулю.

ЗАДАНИЕ Задача 1. На ферме выращивают лисиц и песцов. Для их выращивания требуются три вида кормов. Нормы расхода кормов в месяц представлены в таблице. Требуется определить количество лисиц и песцов, выращивание которых обеспечит максимальную прибыль ферме.

Таблица условий задачи.

Задача 2. Песок поставляется с двух карьеров на 3 комбината по производству строительных конструкций.

Тарифы на перевозку грузов одинаковы и пропорциональны расстояниям. Производительность карьеров: К1= 60 т/сутки и К2 = 80 т/сутки.

Потребности комбинатов:

С1= 30 т/сутки, С2 = 50 т/сутки, С3 = 60 т/сутки.

Расстояния между карьерами (первый индекс) и комбинатами (второй индекс) равны: г₁₁ = 5 км, г₁₂ = 6 км, г₁₃ = 8 км; г₂₁ = 7 км, г₂₂ = 5 км, г₂₃ = 5 км.

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