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

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

     Таблица 3  Табличный алгоритм замены шаг 1

 
    Перепишем Таблицу № 3 в Таблицу № 4, заменив:

    - х₁₂ на х₃₁ и обратно;

    - элементы разрешающей строки  и столбца – числами, стоящими  в нижних частях тех же ячеек;

    - каждый из остальных элементов  – суммой чисел, стоящих в верхней и нижней части той же ячейки.

    Т.к. коэффициент в первой строке при  х₃₁ положителен, значит переменную х₃₁ нужно вывести из числа свободных. В качестве разрешающего берем тот из положительных элементов столбца х₃₁, для которого  отношение к нему свободного члена минимально. Отношения равны 4/5/72=0,011; 1/360=0,0027. Минимальное из них 0,0027. Значит в качестве разрешающего нужно взять элемент 1 в столбце х₃₁, строке х₃₂. Произведем замену х₃₁↔х₃₂. (см.Таблицу № 4).

    Таблица 4  Табличный алгоритм замены шаг 2

    Перепишем Таблицу № 4 в Таблицу № 5, заменив:

    - х₃₁ на х₃₂ и обратно;

    - элементы разрешающей строки  и столбца – числами, стоящими  в нижних частях тех же ячеек;

    - каждый из остальных элементов  – суммой чисел, стоящих в  верхней и нижней части той  же ячейки.

     Таблица 5  Табличный алгоритм замены шаг 3

    Выбираем  из свободных членов отрицательный  (х₁₁) и смотрим на строку элементов, выбирая из элементов отрицательный. Смотрим на столбец, те элементы, которые имеют один знак со свободным членом, выбираем разрешающим элементом тот, отношение которого меньше при делении свободного члена на элемент. В данном случае это элемент столбца х₃₂ и строки х₁₁. выделим в таблице разрешающий элемент -4/5. Вычислим его обратную величину -5/4 и запишем ее в нижней части той же ячейки (в нижнем углу). Все элементы разрешающей строки (кроме самого –4/5) умножим на -4/5, результат запишем в нижней части той же ячейки. Все элементы разрешающего столбца (кроме самого -4/5) умножим на 4/5, результат запишем в нижней части той же ячейки. Подчеркнем (или выделим иным способом) в разрешающей строке все верхние числа (прежние элементы), за исключением самого разрешающего элемента ячейки, а в разрешающем столбце – все нижние числа (новые элементы), за исключением самого разрешающего элемента.

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

    Получим Таблицу № 6.

    Таблица 6  Табличный алгоритм замены шаг 4, итог

 
    В первой строке Таблицы № 4 нет ни одного положительного элемента, значит, оптимальное решение достигнуто, оно будет:

    х₁₁=0; х₁₂=360; х₂₁=360; х₂₂=0; х₃₁=90; х₃₂=270.

    При таких значениях переменных линейная функция L достигает своего минимального значения, равного L_min=-5220.

    Итак, оптимальными являются значения переменных х₁₁; х₁₂; х₂₁; х₂₂; х₃₁; х₃₂, а максимальное значение линейной функции равно L_min=-L_max=5220.

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

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

    MICROSOFT EXCEL– табличный процессор, в нем выполняется построение таблиц и диаграмм, набор и использование формул, набор и использование логических выражений и функций, имеет широкий выбор вычислительных инструментов, обеспечивает автоматический перенос построенных выражений по ячейкам таблицы, обеспечивает всем необходимым для аналитического и наглядного представления информации, поддерживает основные действия, характерные для систем управления базами данных (СУБД),  импорт в другие приложения Microsoft Office и экспорт из других приложений Microsoft Office информации.

Таблица 7 Минутная производительность станков

 
    1) Формулировка математической модели задачи:

• Переменные для решения задачи: х_ij – время работы i–го станка, занятого производством j–той детали.
• Определение функции цели (критерии оптимизации). Суммарная суточная прибыль от производства продукции равна L.
• Ограничения на переменные:

    - время работы каждого станка не должно быть отрицательным, т.е. х_ij≥0;

    - станки не должны простаивать, т.е.

    х₁₁ +х₁₂=360_,

    х₂₁ +х₂₂=360_,

    х₃₁ +х₃₂=360_,

    - количество произведенной продукции на станке А должно равняться количеству произведенной продукции на станке Б, т.е.

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

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

    х₁₁ +х₁₂=360_,

    х₂₁ +х₂₂=360_,

    х₃₁ +х₃₂=360_,

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

    2) Подготовка листа рабочей книги MS Excel для вычислений – на рабочий лист вводим необходимый текст, данные и формулы в соответствии с рисунком 6. Переменные задачи х_11, х_12, х_21, х_22, х_31, х₃₂ находятся, соответственно, в ячейках C6, D6, C7, D7, C8, D8. Целевая функция находится в ячейке E9 и содержит формулу: =СУММПРОИЗВ(C2:D4;C6:D8)↔C2*C6+C3*C7+C4*C8+D2*D6+D3*D7+D4*D8. Ограничения на задачу учтены в ячейках E5, E6, E7, E8.