Геометрическая интерпретация ОЗЛП как метод оптимизации

Таблица 2              План распределения работы станков

Никакого дополнительного расхода каких-либо ресурсов не потребовалось. Те же станки, те же детали, те же станочники работают то же время. Не меняется и производительность станков.

6.           Расчет легко проверить, ведь условия задачи выполняются 2610=2610, каждый станок загружен и не простаивает.

1.3. Обоснование выбора методов решения задачи

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

Основная задача линейного программирования (ОЗЛП) ставится следующим образом: имеется ряд переменных х1, х2, …, хn, требуется найти такие неотрицательные значения этих переменных, которые удовлетворяли бы системе линейных уравнений:

а11x1+a12x2+a13x3+…+a1nxn=b1,

а21x1+a22x2+a23x3+…+a2nxn=b2,

………………………………                                          (1)

а31x1+a32x2+a33x3+…+a3nxn=b3,

Которые, кроме того, обращали бы в минимум линейную функцию:

L=c1x1+c2x2+…+cnxn                            (2)

Допустимое решение ОЗЛП –это любая совокупность неотрицательных переменных, удовлетворяющая уравнениям (1).

Оптимальное решение- это то из допустимых, при котором линейная функция (2) обращается в минимум.

ОЗЛП не обязательно должна иметь решение.

            Может оказаться, что уравнения (1) противоречат друг другу;

           Может оказаться, что они имеют решения, но не в области неотрицательных значений х1, х2, … , хn, в этих случаях ОЗЛП не имеет допустимых решений.

           Может оказаться, что допустимые решения ОЗЛП существуют, но среди них нет оптимального.

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

Ранг матрицы- наибольший порядок отличного от 0 определителя, который можно получить вычеркивая из матрицы какие-то строки и столбцы.

Для совместности системы линейных уравнений (1) необходимо и достаточно, чтобы ранг матрицы системы был равен рангу матрицы ее расширенной матрицы.

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

1)           Ранг системы r не может быть больше числа уравнений m

R≤m

2) Ранг системы не может быть больше общего числа переменных n

R≤n

Структура задачи линейного программирования существенно зависит от ранга системы ограничений, при R=n, система уравнений ограничений ОЗЛП имеет единственное решение.

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

В дальнейшем будем рассматривать случаи, когда R<n, т.е. когда число независимых уравнений, которым должны удовлетворять переменные х1, х2, … , хn, меньше числа самих переменных, тогда если система совместна – у нее существует бесчисленное множество решений, при этом n-R переменным мы можем придавать произвольные значения (так называемые свободные переменные), а остальные R переменных выразятся через них (эти R переменных мы будем называть базисными).

1.4.Описание выбранного алгоритма решения

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

Свойство решения ОЗЛП для случая, когда m=n-2.

1.           Решение ОЗЛП, если оно существует, не может лежать внутри Области Допустимых Решений (ОДР), а только на ее границе.

2.           Решение ОЗЛП может быть и не единственным. Это произойдет в том случае, если основная прямая параллельна той стороне многоугольника допустимых решений, где достигается минимум L'. В этом случае минимум достигается на всей этой стороне и ОЗЛП имеет бесчисленное множество решений.

3.           ОЗЛП может не иметь решения, даже в случае, когда существует ОДР. Это бывает тогда, когда в направлении стрелок ОДР не ограничено.

4.           Решение ОЗЛП минимизирует функцию L (оптимальное решение) всегда достигается в одной из вершин ОДР.

Решение, лежащее в одной из вершин ОДР называется опорным решением, а сама вершина – опорной точкой.

5.           Для того чтобы найти оптимальное решение, можно перебрать все вершины ОДР (опорные точки) и выбрать ту из них, где функция L достигает минимума.

6.           Если число свободных переменных в ОЗЛП равно двум, а число базисных m, и решение ОЗЛП существует, то оно всегда достигается в точке, где, по крайней мере, хотя бы две из переменных обращаются в нуль.

Рассмотрим задачу линейного программирования, система ограничений которой задана виде неравенств.

Найти минимальное значение линейной функции

         (1.1)                        Z=C1x1+C2x2+…+Cnxn

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

а11x1+a12x2+…+a1nxn ≤ b1,

а21x1+a22x2+…+a2nxn ≤ b2,

(1.2)                           …………………………

аm1x1+am2x2+…+amnxn ≤ bm,

(1.3)                            хj≥0 (j=1,2,… n).

Совокупность чисел х1, х2, … , хn, удовлетворяющих ограничениям(1.2) и (1.3), называется решением. Если система неравенств (1.2) при условии (1.3) имеет хотя бы одно решение, она называется совместной, в противном случае – несовместной.

Рассмотрим на плоскости х1Ох2 совместную систему линейных неравенств

а11x1+a12x2+…+a1nxn ≤ b1,

а21x1+a22x2+…+a2nxn ≤ b2,                            х1 ≥ 0,

…………………………                            х2 ≥ 0.

аm1x1+am2x2+…+amnxn ≤ bm,

Это все равно, что в системе (1.2) – (1.3) положить n = 2. Каждое неравенство этой системы геометрически определяют полуплоскость с граничной прямой ai1x1+ai2x2=bi (i =1,2,…, m). Условия неотрицательности определяют полуплоскости соответственно с граничными прямыми х1 = 0, х2 = 0. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы (рисунок 2). Совокупность этих точек (решений) будем называть многоугольником решений. Он может быть точкой, отрезком, многоугольником, неограниченной многоугольной областью.

Рисунок 2

Область допустимых решений

Если в системе ограничений (1.2)-(1.3) n = 3, то каждое неравенство геометрически представляют полупространство трехмерного пространства, граничная плоскость которого ai1x1+ai2x2 +ai3x3=bi (i =1,2,…, m), а условия неотрицательности – полупространства с граничными плоскостями соответственно xj=0 (j=1, 2, 3). Если система ограничений совместна, то эти полупространства, как выпуклые множества, пересекаясь, образуют в трехмерном пространстве общую часть, которая называется многогранником решений. Многогранник решений может быть точкой, отрезком, лучом, многоугольником, многогранником, многогранной неограниченной областью.

Пусть в системе ограничений (1.2)-(1.3) n > 3; тогда каждое неравенство определяет полупространство n –мерного пространства с граничной гиперплоскостью ai1x1+ai2x2+ainxn=bi (i =1,2,…, m), а условия неотрицательности – полупространства с граничными гиперплоскостями xj=0 (j=1, 2, …, n).

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

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

2. ОПЫТНО-ЭКСПЕРИМЕНТАЛЬНАЯ ЧАСТЬ

2.1. Описание реализации алгоритма решения задачи

Составим систему уравнений, описывающую условия задачи:

х11+х12=360,

х21+х22=360,

х31+х32=360,

5х11+6х21+5х31=5х12+2х22+3х32.

И линейную функцию L, которую необходимо максимизировать.

L=5х11+5х12+6х21+2х22+5х31+3х32

Где хij- время работы i-го станка, занятого производством j-ой детали.

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

Основную задачу линейного программирования можно решать с помощью геометрической интерпретации, когда число переменных (хij) на два больше, чем число независимых уравнений m, которым они должны удовлетворять.

В нашей задаче число переменных n (6) на два больше, чем число независимых уравнений m (4), которым они должны удовлетворять: n-m=2.

    х11+х12=360,

(2.1)              х21+х22=360,

              х31+х32=360,

5х11+6х21+5х31=5х12+2х22+3х32.

Выберем  в качестве свободных переменных, например, x12 и x22 и выразим через  них остальные (базисные) переменные: х11, х21, х32, х31. Из первого уравнения имеем:

х11=360-х12                                                        (2.2)

Из второго:

х21=360-х22                                                        (2.3)

Из третьего:

х31=360-х32.                                                        (2.4)

Подставляя (2.2), (2.3.) и (2.4.) в последнее уравнение и разрешая его относительно  х32, имеем:

х32=720-1,25х12-х22,                                          (2.5)

х31=-360+1,25х12+х22.                                          (2.6)

Геометрическая интерпретация задачи представлена на рисунке 3 (прямые х12=0, х22=0 – оси координат; остальные ограничивающие прямые х31=0, х32=0, х11=0 и х21=0; штриховкой помечены допустимые полуплоскости).