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

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

 

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

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

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

     а₁₁x₁+a₁₂x₂+a₁₃x₃+…+a_1nx_n=b₁,

    а₂₁x₁+a₂₂x₂+a₂₃x₃+…+a_2nx_n=b₂,

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

    а₃₁x₁+a₃₂x₂+a₃₃x₃+…+a_3nx_n=b₃,

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

    L=c₁x₁+c₂x₂+…+c_nx_n  (2)

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

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

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

• Может оказаться, что уравнения (1) противоречат друг другу;
• Может оказаться, что они имеют решения, но не в области неотрицательных значений х₁, х₂, … , х_n, в этих случаях ОЗЛП не имеет допустимых решений.
• Может оказаться, что допустимые решения ОЗЛП существуют, но среди них нет оптимального.

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

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

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

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

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

    R≤m

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

    R≤n

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

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

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

 

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

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

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

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

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

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

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

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

         (1.1)           Z=C₁x₁+C₂x₂+…+C_nx_n

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

    а₁₁x₁+a₁₂x₂+…+a_1nx_n ≤ b₁,

    а₂₁x₁+a₂₂x₂+…+a_2nx_n ≤ b₂,

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

    а_m1x₁+a_m2x₂+…+a_mnx_n ≤ b_m,

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

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

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

    а₁₁x₁+a₁₂x₂+…+a_1nx_n ≤ b₁,

    а₂₁x₁+a₂₂x₂+…+a_2nx_n ≤ b₂,  х₁ ≥ 0,

    …………………………  х₂ ≥ 0.

    а_m1x₁+a_m2x₂+…+a_mnx_n ≤ b_m,

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

    

    Рисунок 2

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

    Если в системе ограничений (1.2)-(1.3) n = 3, то каждое неравенство геометрически представляют полупространство трехмерного пространства, граничная плоскость которого a_i1x₁+a_i2x₂ +a_i3x₃=b_i (i =1,2,…, m), а условия неотрицательности – полупространства с граничными плоскостями соответственно x_j=0 (j=1, 2, 3). Если система ограничений совместна, то эти полупространства, как выпуклые множества, пересекаясь, образуют в трехмерном пространстве общую часть, которая называется многогранником решений. Многогранник решений может быть точкой, отрезком, лучом, многоугольником, многогранником, многогранной неограниченной областью.

    Пусть в системе ограничений (1.2)-(1.3) n > 3; тогда каждое неравенство определяет полупространство n –мерного пространства с граничной гиперплоскостью a_i1x₁+a_i2x₂+a_inx_n=b_i (i =1,2,…, m), а условия неотрицательности – полупространства с граничными гиперплоскостями x_j=0 (j=1, 2, …, n).

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

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

 

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

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

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

    х₁₁+х₁₂=360,

    х₂₁+х₂₂=360,

    х₃₁+х₃₂=360,

    5х₁₁+6х₂₁+5х₃₁=5х₁₂+2х₂₂+3х₃₂.

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

    L=5х₁₁+5х₁₂+6х₂₁+2х₂₂+5х₃₁+3х₃₂

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

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

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

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