- •Линейное программирование
- •1. Общая задача линейного программирования
- •1.1. Задачи математического и линейного программирования
- •1.2. Математические модели простейших экономических задач
- •2. Каноническая форма
- •2.1. Определение и формы записи
- •2.2. Приведение общей задачи линейного
- •3. Графический метод решения задач
- •3.1. Общие понятия, примеры
- •4. Свойства решений задач линейного
- •4.1. Отрезок в . Понятие выпуклого множества. Гиперплоскость и полупространство, их выпуклость
- •4.3. Теорема о достижении линейной функцией
- •4.4. Опорное решение задачи линейного программирования,
- •5. Симплексный метод решения задач
- •5.1. Нахождение начального опорного плана и переход к новому опорному решению
- •5.2. Метод искусственного базиса
- •6. Теория двойственности
- •6.1. Построение двойственной задачи
- •6.2. Одновременное решение прямой и двойственной задач
- •7. Транспортная задача
- •7.1. Постановка задачи и её математическая модель
- •7.2. Построение первоначального опорного плана
- •7.3. Метод потенциалов
- •Образец типового расчета
- •Реализация задач лп на пк в Exсel
5.1. Нахождение начального опорного плана и переход к новому опорному решению
Предположим, что необходимо найти минимум целевой функции при следующей системе ограничений:
(5.1.1)
Запишем систему (5.1.1) в векторной форме:
(5.1.2)
, ,…, , ,..., .
Векторы , ,.., образуют базис в . Поэтому в соотношении (5.1.2) за базисные переменные принимаем , ,…, , а остальные переменные
(будем называть их свободными) приравниваем нулю. Учитывая, что , получаем, что опорное решение задачи (5.1.1) имеет вид
Рассмотрим, как, исходя из начального опорного решения, можно построить другое опорное решение, которое будет более близким к оптимальному, т.е. на котором значение целевой функции будет меньше. Систему ограничений (5.1.1) перепишем в виде:
(5.1.3)
Выражая значения , ,…, через свободные неизвестные, целевую функцию получим в виде:
. (5.1.4)
Итак, первоначальный опорный план , а соответствующее значение . Возможны следующие ситуации:
1) все , , …, . Тогда минимум достигается при , т.е. план является оптимальным и ;
2) среди чисел , , …, имеются положительные. Пусть , где одно из чисел , ,..;, . Тогда полагаем все , , …, равными нулю, кроме . Из (5.1.3) следует, что
(5.1.5)
и .
Здесь, в свою очередь, могут представиться два случая:
а) все числа , , …, , тогда для любого все значения , ,…, . В этом случае не достигается, так как при функция ;
б) среди чисел , , …, имеются положительные. Пусть, например, . Так как все компоненты плана должны быть положительны, то нельзя увеличивать более, чем ( иначе станет отрицательным ).
Поэтому найдём называется разрешающим элементом. Положим ,…, , , ,…, . Найдём значения остальных неизвестных:
Получено новое опорное решение: .
Значение целевой функции при этом уменьшается:
.
Идея симплекс-метода заключается в том, что на каждом этапе один из векторов выводится из базиса, а вместо него вводится другой – . При этом удобно, чтобы он стал бы единичным. Поэтому в системе ограничений -е уравнение, содержащее разрешающий элемент , делим на . Исключаем из всех остальных уравнений, т.е. осуществляем преобразование Жордана-Гаусса.
Итак, алгоритм симплекс-метода состоит в следующем:
1. Приводим систему к виду, содержащему единичных векторов, и определяем первоначальный опорный план.
2. Выражаем через свободные переменные в виде:
.
Если при этом все коэффициенты , ,.., не являются положительными, то найденный первоначальный план является оптимальным.
3. Пусть среди чисел , ,.., имеются положительные. Берём любой из них, например, , и просматриваем весь соответствующий столбец . Он называется разрешающим столбцом. Если все числа этого столбца отрицательны, то Задача решения не имеет.
4. Если в этом столбце есть положительные числа, то находим разрешающий элемент – это элемент, для которого отношение минимально. Пусть это элемент .
5. Выводим переменную из числа свободных и меняем её с базисной переменной .
6. Эту процедуру выполняем до тех пор, пока все коэффициенты при свободных неизвестных станут неположительными, (это признак
оптимальности плана) либо неположительными станут все элементы в разрешающем столбце ( т.е. ).
Замечание. На практике этот алгоритм реализуется с помощью симплекс-таблиц (см. пример 5.1.).
Пример 5.1. Строительное управление ведёт капитальный ремонт жилых домов. Перегородки внутри этих домов могут быть изготовлены гипсобетонными или каркасными ( с обшивкой листами сухой штукатурки ). Ресурсы на месяц заданы в таблице:
Потребности на площади перегородок
Гипсобетон Пиломатериалы Сухая штукатурка Трудоресурсы |
Каркасные |
Гипсобетонные |
―
чел. дней |
― чел. дней |
Рассчитать общее количество как каркасных, так и гипсобетонных перегородок, которые следует возвести в текущем месяце, чтобы их площадь была наибольшей, если строительное управление имеет в наличии гипсобетона – , пиломатериалов – , сухой штукатурки – , трудоресурсов – .
Решение. Составим математическую модель задачи. Пусть требуется возвести каркасных и гипсобетонных перегородок. Из условия на это уйдёт: гипсобетона , пиломатериалов , сухой штукатурки , трудоресурсов . Учитывая лимиты материалов и трудоресурсов, составляем систему ограничений – неравенств:
Для решения задачи симплекс-методом вводим дополнительные переменные:
Полагаем . Принимаем , в качестве свободных переменных, , , , в качестве базисных. Начальный опорный план имеет вид: , . Составляем симплекс-таблицу (в сокращённой форме), соответствующую начальному опорному плану. Обратим внимание, что коэффициенты при свободных переменных пишутся с противоположным знаком.
|
Выбираем какой-либо положительный элемент в последней строке симплекс-таблицы ( среди коэффициентов при и в целевой функции) и соответствующий столбец объявляем ведущим. Например, объявим ведущим второй столбец и поставим стрелку вверх. Подсчитаем отношения свободных членов к положительным элементам ведущего |
столбца:
, , .
Элемент ведущего столбца, для которого отношение минимально ( в нашем случае 0,25) объявляем ведущим. Строка, в которой находится элемент, также называется ведущей и помечается стрелкой слева.
Теперь запишем правила перехода к новой симплекс-таблице, соответствующие приведённому выше алгоритму симплекс-метода:
1. Базисная переменная, находящаяся в ведущей строке, и свободная переменная, находящаяся в ведущем столбце, меняются местами.
2. Ведущий элемент заменяется величиной, ему обратной.
3. Все элементы ведущей строки (включая свободный член), кроме ведущего элемента, заменяются их отношениями к ведущему элементу.
4. Все элементы ведущего столбца (кроме ведущего элемента) заменяются взятыми с обратными знаками их отношениями к ведущему элементу.
5. Остальные элементы заменяются по «правилу 4 элементов»: любой такой элемент умножается на ведущий и из произведения вычитается произведение двух других элементов, составляющих с первыми вершины прямоугольника, после чего результат делится на ведущий элемент.
Проводя вычисление по этим правилам, получаем следующую симплекс-таблицу:
|
Значение -1200 ещё не является минимальным для функции , т.к. в последней строке ещё есть положительный коэффициент. |
Аналогично составляем следующую симплекс-таблицу:
|
И значение -2200 не является минимальным для . Составим ещё одну симплекс-таблицу: |
||||||||||||||||||||||||
|
Пересчитывая последнюю строку, сразу убеждаемся, что значение -2400 является минимальным для функции . Нам ещё следует пересчитать свободные члены при и . Поскольку в опорном плане, соответствующем симплекс-таблице, свободные неизвестные равны 0, то найденные значения свободных членов при и дадут оптимальный план производства: |
,
.