Метод линейного программирования

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

Линейным программированием называется раздел математики, в
котором изучаются методы нахождения минимума или максимума
линейной функции конечного числа переменных при условии, что переменные удовлетворяют конечному числу дополнительных ограничений,
имеющих вид линейных уравнений или неравенств. Таким образом,
задача линейного программирования (ЗЛП) в общем случае формулируется следующим образом: найти такие значения действительных
переменных х ₁, х ₂ ..., х_m для которых целевая функция

Q(x) = р ₁ х ₁+ р ₂ х ₂+... + р_nх_n (10.1)(5.5)

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

(10.2) (5.6)

 

где коэффициенты а_ij, b_j, р_j, (i =1, j =1,n) — действительные числа.

Можно предполагать, что

b ₁≥0, b ₂≥0 ,..., b_n ≥0.

В матричном виде ЗЛПформулируется

АХ= b; х ≥0; Q_min(х) ≥ р^rх,

где х =(х ₁, х ₂,..., x _n)^T Rⁿ, А — матрица размера тn;

р =(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 ₂ — расход ресурса первого вида; 4 x ₁ + 6 х ₂ — расход ресурса
второго вида; 4 x ₁ + 5 х ₂ — доход от реализации продукции.

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

F_max = 4 x ₁ + 5 х ₂

 

при условиях

2х, +х ≤ 8;

4 x ₁ + 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^*

	х 1	х 2	х 3	bj
х 4
х 5	-1		-1
х 6
Pj	-3			F*

 

 

i^*

 

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

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

 

и .

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

Таблица (10.2) 5.2

j*

	х 1	х 2	х 3	ьj
х 4		1/2	1/2	5/2
х 5	-1		-1
х 6
pj	-3			F*

 

 

i^*

 

Для перехода к новой симплекс-таблице необходимо поменять места-
ми х₁ и х₄, а все элементы разрешающей строки умножаем на элемент
а^*₄₁ = 1. Все элементы разрешающего столбца умножаем на - а^*₄₁=- 1,
кроме самого разрешающего элемента, что приведено в табл. 5.3.

Таблица 5.3

j^*

 

	х 1	х 2	х 3	ьj
х 4		1/2	1/2	5/2
х 5	-1		-1/2
х 6			1/2
pj	-3			F*

 

i^*

 

Остальные элементы таблицы вычисляем по формуле, значение
нового элемента равно:

Тогда для элемента а ₅₂

Аналогично для р_j

и для b _i

Так же для F

и т.д.

Заполняем табл. 5.3.
Так как все коэффициенты р_j в табл. 5.3 положительны, решение найдено. Значение F из последней строки табл. 5.3 с противоположным знаком будет решением целевой функции, т.е.

F _min = — 7.

Базисное решение: х ₁ = 2,5; х ₂ = 0; х ₃ = 0;

x ₄=0; х ₅ = 6,5; х ₆ = 5,5.

Проверка: F _min = -3х₁ + х ₂+ 3х₃ = -3 х 5/2 = -7,5.

 

назад