Файл: Математическое моделирование в экологии.doc

р = (p₁, p₂, …, p_n)^T;

b =(b₁, b₂, …, b_m)^T ≥ 0

где Rⁿ — область возможных решений.

Если имеется максимум целевой функции

G(x) = р₁х₁ + р₂х₂ + ... + р_nр_n,

то это равнозначно отысканию минимума функции

Q(x) = -G(x) = (-p_i)x_i + (-р₂)x₂+ ... + (-р_n)x_n.

Если в дополнительных условиях имеется неравенство, например,

а_i1х₁ + а₂х₂ + ... + а_in х_n ≤ b_i

то введением вспомогательного переменного множителя у можно перейти к уравнению

а_i1х₁ + а₂х₂ + ... + а_in х_n= b.

Для нового переменного также справедливо неравенство у ≥ 0; в целевую функцию оно входит с коэффициентом Θ. Если для переменной х_i, не задано условие х ≥ 0, то могут быть введены, например, новые переменные х_j' и х_j" с дополнительными условиями х_j' ≥ 0 и х_j"≥ 0, причем х_j = х_j' - х_j". Поэтому в дальнейшем будем рассматривать в основном, задачи минимизации целевой функции Q(x) при условиях, заданных линейными уравнениями с неотрицательными членами b_i в предположении неотрицательных переменных. Эти задачи и будем называть задачами линейного программирования (ЗЛП). В математической литературе ЗЛП записывается в виде

(10.3)(5.7)

Любая ЗЛП может быть приведена к виду (5.7). Двойственной к выражению (5.7) будем называть задачу

Точка х = (х₁, х₂, …, х_n)^T, удовлетворяющая всем условиям, называется допустимой. Множество всех допустимых точек называется допустимой областью. Если после отбрасывания одного условия допустимая область не меняется, то такое условие называется лишним. В задачах с двумя переменными можно отказаться от перехода от неравенств к уравнениям, так как линейное неравенство а₁х₁+ а₂х₂ ≤ b допускает непосредственную геометрическую интерпретацию: все точки, удовлетворяющие этому неравенству, лежат на прямой а₁х₁+ а₂х₂ = b и в одной из двух полуплоскостей, на которые эта прямая делит всю плоскость.

Множество всех оптимальных решений ЗЛП выпукло. Если допустимая область образована n неравенствами х_j ≥ 0, и т уравнениями, то она может иметь самое большее вершин.

Если допустимая область ограничена и непустая, то она является выпуклым многогранником, и задача ЗЛП в этом случае всегда разрешима, а оптимальное значение целевой функции достигается, по крайней мере, в одной из вершин многогранника.

Если допустимая область пуста, то ЗЛП неразрешима.

Если допустимая область не ограничена, то ЗЛП либо может быть разрешимой, либо нет.

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

Например, каноническая форма 2х₁ – Зх₂ + х₄ = 5, к которой может привести неравенство

2х₁ – Зх₂ ≤ 5,

при x₄ ≥0.

2х₁ – Зх₂ + х₄ = 5

Формулировка задачи представлена в виде

если каждое из уравнений содержит одну переменную х_j такую, что коэффициент перед ней в этом уравнении равен 1, а во всех других уравнениях равен 0. Если при этом все b ≥ 0, то говорят о допустимом каноническом виде. Переменные х_i называют базисными, а остальные — свободными.

Например,

3х₁+ х₂+ 2х₃ = 5;

- х₁+ 3х₃+х₅ = 9;

х₁ – 4х₃+ х₄ = 1.

где х₂, х₄, х₅ – базисные переменные;

х₁,х₃ — свободные переменные.

В целевую функцию должны входить только свободные переменные.

Если целевая функция имеет вид

Q(x) = х₁ + 13х₂ +2x₃ +17х₄ + 3х₅,

то вычитанием из этого выражения первого уравнения, умножен- ного на 13 (так как там выделена переменная х₂, а в целевой функ- ции х₂ имеет коэффициент 13), второго уравнения, умноженного на 3, и третьего — на 17, получим целевую функцию

Q(x) = -52х₁ + 35х₃ + 109.

Тогда окончательно ЗЛП в каноническом виде запишется:

(10.4)(5.8)

При всех х_i = 0 Q_min= 109.

Задача (10.4) (5.8) решается симплекс-методом. Для этого находим базисное решение (10.4) (5.8).

Так как ограничения в виде уравнений представляют собой плоскости в n-мерном пространстве, а также условия х_i ≥ 0, то решение ЗЛП ищется в вершинах образованного в n-мерном пространстве многогранника, который сам по себе представляет область допустимых решений.

Рассмотрим пример, когда ЗЛП решается при двух переменных х₁ и х₂, поэтому может быть интерпретирована геометрическими построениями на плоскости.

Пример. Имеется два вида ресурсов в количестве 8 и 24, из которых изготавливается два вида изделий. На единицу изделия первого вида расходуются ресурсы в количестве два и четыре, а второго вида — один и шесть. Цена первого изделия четыре, второго — пять.

Ставится задача, в каких количествах следует изготавливать изделия, чтобы обеспечить максимальный доход?

Р е ш е н и е. Построим математическую модель задачи. Обозначим через х₁ и x₂ числа производимых изделий первого и второго видов, тогда 2х₁ + x₂ — расход ресурса первого вида; 4x₁ + 6х₂ — расход ресурса второго вида; 4x₁ + 5х₂ — доход от реализации продукции.

Учитывая ограничения на используемые материалы, сформулируем ЗЛП: максимизировать доход

F_max = 4x₁ + 5х₂

при условиях

2х, +х ≤ 8;

4x₁ + 6х₂ ≤ 24;

x₁ ≥ 0, х₂ ≥ 0.

Этой ЗЛП можно дать геометрическую интерпретацию ( рис. 5.1).

Каждое из неравенств системы определяет полуплоскость, их пересечение (заштрихованная часть) — это ресурсно-обеспеченная область допустимых решений (ОДР).

Для определения точки максимума ОДР возьмем какую-либо функцию F, например F = 20.

Тогда

F= 4х₁ + 5х₂, или 20 = 4х₁ + 5х₂ .

Проводим на рис. 10.1 данную линию (штриховую), которая показывает направление к точке максимума при движении по ОДР. П ри движении слева направо последней точкой на ОДР является точка k. Она и дает решение задачи. Решая совместно уравнения

2х₁+х₂ = 8

и

4х₁+6х₂ = 24,

находим х₁ = 3, х₂ = 2.

Тогда F_max = 4 х 3 + 5 х 2 = 22.

Рис. 10.1 Схема определения области допустимых решений

Вершинами ОДР в этой задаче являются точки О, А, К и В. Теперь рассмотрим задачу более чем с двумя переменными. Так как решение ЗЛП достигается (по крайней мере) в вершинах ОДР, то достаточно не определять ОДР, а рассмотреть значения целевой функции только в вершинах.

Допустимой симплекс-таблице соответствует точка минимума, если все коэффициенты целевой функции неотрицательны. Тогда минимальное значение целевой функции равно Y_min. Если критерий выполнен, т.е. не все коэффициенты целевой функции положительны, то следует перейти от одного допустимого базисного решения к соседнему допустимому в котором множество базисных и свободных переменных изменены на один элемент. В невырожденном случае этому геометрически соответствует переход от одной вершины к другой вдоль ре бра ОДР (обе вершины принадлежат одному ребру). Этот процесс называется симплекс-шагом или заменой базиса. Рас- смотрим это на примере.

Пример. Задана целевая функция

F= -3х₁ +х₂ +3х₃ => min,

при ограничениях

2х₁ + х₂ + х₃ + х₄ < 5;

-х₁+ 3х₂ - х₃ < 4;

х, + 2х,+ х,+х < 8;

x₁=0, x₂=0, x₃> 0

Р е ш е н и е. Запишем задачу в каноническом виде

F= -3х₁ +х₂ +3х₃ => min.

Ограничения:

2х₁ + х₂ + х₃ + х₄ = 5;

-х₁+ 3х₂ - х₃+x₅ = 4;

х₁ + 2х₂+ х₃+х₆ =8;

x_i=0,

где х₁, х₂, х₃ — свободные переменные, а х₄, х₅, х₆ — базисные. Запишем симплекс-таблицу (табл. (10.1)5.1).

Таблица (10.1)5.1

j^*

i^*

Так как в последней строке имеется отрицательный член, от данного базиса переходим к соседнему. Для этого выбираем разрешающий столбец с отрицательным членом (если имеется несколько отрицательных членов, то для разрешающего столбца выбирается наименьшее значение). В нашем случае разрешающий столбец j^* будет для х_i.

Для выбора разрешающей строки берутся коэффициенты при х_i с положительным знаком. Делим свободные члены b_i на эти коэффициенты

и .

Для разрешающей строки выбираем наименьшее из получен- ных значений, т.е. выбираем строку i^* для х₄. Тогда разрешающий элемент а_ij = а^*₄ = 2. Для удобства вычислений разрешающий элемент принимаем равным 1, для чего все элементы разрешающей строки разделим на 2. Тогда таблица будет записана в виде табл. (10.2)5.2.

Таблица (10.2)5.2

j*