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

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

- х31 на х32 и обратно;

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

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

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

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

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

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

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

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

х11=0; х12=360; х21=360; х22=0; х31=90; х32=270.

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

Итак, оптимальными являются значения переменных х11; х12; х21; х22; х31; х32, а максимальное значение линейной функции равно Lmin=-Lmax=5220.

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

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

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

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

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

                        Переменные для решения задачи: хij – время работы i–го станка, занятого производством j–той детали.

                        Определение функции цели (критерии оптимизации). Суммарная суточная прибыль от производства продукции равна L.

                        Ограничения на переменные:

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

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

х11 +х12=360,

х21 +х22=360,

х31 +х32=360,

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

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

      Найти максимум следующей функции:

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

      При ограничениях вида:

х11 +х12=360,

х21 +х22=360,

х31 +х32=360,

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

2) Подготовка листа рабочей книги MS Excel для вычислений – на рабочий лист вводим необходимый текст, данные и формулы в соответствии с рисунком 6. Переменные задачи х11, х12, х21, х22, х31, х32 находятся, соответственно, в ячейках 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.

Рисунок 6

Рабочий лист MS Excel для решения задачи планирования производства деталей

3) Работа с надстройкой Поиск решения – воспользовавшись командой Сервис/ Поиск решения, вводим необходимые данные для рассматриваемой задачи (установка данных в окне Поиск решения приведена на рисунке 7). Результат работы по поиску решения помещен на рисунках 7-11.

Рисунок 7

Установка необходимых параметров задачи планирования деталей в окне Поиск решения

Описание отчетов о решении задачи

           Отчет по результатам (рисунок 9) – таблица Целевая ячейка выводит сведения о целевой функции; таблица Изменяемые ячейки показывает значения искомых переменных, полученных в результате решения задачи; таблица Ограничения отображает результаты оптимального решения для ограничений и для граничных условий.

В поле Формула приведены зависимости, которые были введены в окно Поиск решения (рисунок 6), в поле Разница – величины использованного времени. Если время используется полностью, то в поле Статус указывается Связанное, при неполном использовании времени в этом поле указывается, не связан. Для граничных условий приводятся аналогичные величины с той лишь разницей, что вместо величины неиспользованного времени показана разность между значением в найденном оптимальном решении и заданным для нее граничным условием.

Рисунок 8

Результат расчета надстройки Поиск решения

Рисунок 9

Отчет по результатам поиска решения

           Отчет по устойчивости (рисунок 10) – в таблице Изменяемые ячейки приводится результат решения задачи. В таблице Ограничения выводятся значения для ограничений, при которых сохраняется оптимальный набор переменных, входящих в оптимальное решение.

Рисунок 10

Отчет по устойчивости поиска решения

           Отчет по пределам (рисунок 11) – в отчете показано, в каких пределах может изменяться количество времени, вошедшее в оптимальное решение, при сохранении структуры оптимального решения; приводятся значения переменных в оптимальном решении, а также нижние и верхние пределы изменения значений переменных; здесь также указаны значения целевой функции при производстве данной детали на верхнем и нижнем пределах.

Рисунок 11

Отчет по пределам поиска решения

2.2. Результаты, полученные в ходе решения задачи

Решив задачу, мы получили следующие результаты: для получения оптимального решения необходимо загрузить работу станков следующим образом: станок № 1 - 0 минут над деталью А и 360 минут над деталью Б, станок № 2 - 360 минут над деталью А и 0 минут над деталью Б, станок № 3 - 90 минут над деталью А и 270 минут над деталью Б, при этом производительность будет максимальной и равняться 5220 деталей за смену.

3. ВЫВОДЫ И ЗАКЛЮЧЕНИЕ

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

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