Значительное развитие теория и алгоритмический аппарат линейного программирования получили с изобретением и распространением ЭВМ и формулировкой американским математиком Дж. Данцингом симплекс-метода.
В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решения. Для решения задач линейного программирования разработано сложное програмное обеспечение, дающее возможность эффективно и надежно решать практические задачи больших объемов. Эти программы и системы снабжены развитыми системами подготовки исходных данных, средствами их анализа и представления полученных результатов.
В развитие и совершенствование этих систем вложен труд и талант многих матеметиков, аккумулирован опыт решения тысяч задач. Владение аппаратом линейного программирования необходимо каждому специалисту в области математического программирования. Линейное программирование тесно связано с другими методами математического программирования (например, нелинейного программирования, где целевая функция нелинейна).
Задачи с нелинейной целевой функцией и линейными ограничениями называют задачами нелинейного программирования с линейными ограничениями. Оптимизационные задачи такого рода можно классифицировать на основе структурных особенностей нелинейных целевых функций. Если целевая функция Е - квадратичная функция, то мы имеем дело с задачей квадратичного программирования; если Е – это отношение линейных функций, то соответствующая задача носит название задачи дробно-линейного программирования, и т.д. Деление оптимизационных задач на эти классы представляет значительный интерес, поскольку специфические особенности тех или иных задач играют важную роль при разработке методов их решения.
Современные методы линейного программирования достаточно надежно решают задачи общего вида с несколькими тысячами ограничений и десятками тысяч переменных. Для решения сверхбольших задач используются уже, как правило, специализированные методы.
1. ПОСТАНОВКА ЗАДАЧИ ОПТИМИЗАЦИИ
Вариант 80.
В цехе имеется токарный станок и станок-автомат. Цех выпускает детали 1,2 и 3 в комплекте: на каждую деталь 1 – по 2 детали 2 и 3. Часовая производительность станков по каждой из деталей приведена в таблице:
Станки | Детали | ||
1 | 2 | 3 | |
| 1.Токарный | 5 | 5 | 10 |
| 2.Автомат | 15 | 15 | 10 |
Таблица 1. Часовая производительность станков
Составить программу работы станков, при которой в течение смены (8 часов) будет выпускаться максимальное количество комплектов деталей.
2. ПОСТРОЕНИЕ АНАЛИТИЧЕСКОЙ МОДЕЛИ
Составим аналитическую модель задачи. Для этого сначала введем переменные, которые требуется определить:
X1 – время, которое работал токарный станок над деталями типа 1 в течение рабочей смены;
X2 – время, которое работал токарный станок над деталями типа 2 в течение рабочей смены;
X3 – время, которое работал токарный станок над деталями типа 3 в течение рабочей смены;
X4 – время, которое работал станок-автомат над деталями типа 1 в течение рабочей смены;
X5 – время, которое работал станок-автомат над деталями типа 2 в течение рабочей смены;
X6 – время, которое работал станок-автомат над деталями типа 3 в течение рабочей смены.
Система ограничений состоит из двух групп. Первая группа устанавливает, что каждый из станков может работать не более 8 часов в смену.
Ограничение времени работы токарного станка:
X1 + X2 + X3 £8;
Ограничение времени работы станка-автомата:
X4 + X5 + X6 £8.
Вторая группа ограничений направлена на выполнение требования о комплектации деталей: на каждую деталь 1 должно приходиться по 2 детали 2 и 3. Но перед тем, как вводить это ограничение, определим, сколько деталей каждого типа у нас будет производиться за смену:
5X1 + 15X4- будет произведено за смену деталей типа 1;
5X2 + 15X5- будет произведено за смену деталей типа 2;
10X3 + 10X6- будет произведено за смену деталей типа 3.
Теперь введем сами ограничения:
2(5X1 + 15X4) = 5X2 + 15X5;
2(5X1 + 15X4) = 10X3 + 10X6.
Очевидно, что все переменные в задаче неотрицательные (объем продукции не может быть отрицательным):
X1 , X2 , X3 , X4 , X5 , X6≥0.
Целевая функция в нашей задаче должна выражать количество комплектов деталей, выпускаемых за смену, поэтому сложим все выпускаемые детали и поделим на 5 (в комплект, как уже упоминалось, входят 1 деталь типа 1 и по 2 детали типа 2 и 3):
E=(5X1 + 15X4 + 5X2 + 15X5 + 10X3 + 10X6)/5 Þ max
или, если упростить это выражение, то получим:
E= X1 + X2 + 2X3 + 3X4 + 3X5 + 2X6 Þ max
Целевую функцию надо максимизировать.
Таким образом, формальная постановка задачи оптимизации имеет следующий вид:
X1 + X2 + X3 £8;
X4 + X5 + X6 £8;
2(5X1 + 15X4) = 5X2 + 15X5;
2(5X1 + 15X4) = 10X1 + 10X6;
X1 , X2 , X3 , X4 , X5 , X6≥0.
E= X1 + X2 + 2X3 + 3X4 + 3X5 + 2X6 Þ max
3. ОБОСНОВАНИЕ И ОПИСАНИЕ ВЫЧИСЛИТЕЛЬНОЙ ПРОЦЕДУРЫ
3.1. ПРИВЕДЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ К СТАНДАРТНОЙ ФОРМЕ
Любая задача линейного программирования приводится к стандартной (канонической) форме основной задачи линейного программирования, которая формулируется следующим образом: найти неотрицательные значения переменных X1 , X2 , Xn , удовлетворяющих ограничениям в виде равенств:
A11X1 + A12X2 + … + A1nXn = B1;
A21X1 + A22X2 + … + A2nXn = B2;
……………………………………
Am1X1 + Am2X2 + … + AmnXn = Bm;
Xj ≥0, j=1,…,n
и обращающих в максимум линейную функцию этих переменных:
E = C1X1 + C2X2 + … + CnXnÞ max
При этом также требуется, чтобы правые части равенств были неотрицательны, т.е. должны соблюдаться условия:
Bj ≥ 0, j=1,…,n
Приведение к стандартной форме необходимо, таккакбольшинство методов решения задач линейного программирования разработано именно для стандартной формы. Для приведения к стандартной форме задачи линейного программирования может потребоваться выполнить следующие действия:
- перейти от минимизации целевой функции к ее максимизации;
- изменить знаки правых частей ограничений;
- перейти от ограничений-неравенств к равенствам;
- избавиться от переменных, не имеющих ограничений на знак.
Для решения нашей задачи воспользуемся симплекс-методом, так как этот метод предназначен для решения задач линейного программирования любой размерности.
3.2. ОСНОВНАЯ ИДЕЯ СИМПЛЕКС-МЕТОДА
Экстремум целевой функции всегда достигается в угловых точках области допустимых решений. Симплекс-метод, называемый также методом последовательного улучшения плана, реализует перебор угловых точек области допустимых решений в направлении улучшения значения целевой функции. Основная идея этого метода следующая. Прежде всего, находится какое-либо допустимое начальное (опорное) решение, т.е. какая-либо угловая точка области допустимых решений. Процедура метода позволяет ответить на вопрос, является ли это решение оптимальным. Если "да", то задача решена. Если "нет", то выполняется переход к смежной угловой точке области допустимых решений, где значение целевой функции улучшается, т.е. к нехудшему допустимому решению. Если некоторая угловая точка имеет несколько смежных, то вычислительная процедура метода обеспечивает переход к той из них, для которой улучшение целевой функции будет наибольшим. Процесс перебора угловых точек области допустимых решений повторяется, пока не будет найдена точка, которой соответствует экстремум целевой функции Е.
При построении начального базиса в заданной задаче использовался метод искусственного базиса, поэтому найденное решение не является допустимым. В этом случае для решения задачи необходимо использовать двухэтапный симплекс-метод.
3.3. ДВУХЭТАПНЫЙ СИМПЛЕКС-МЕТОД
Задача с помощью этого метода решается в два этапа: сначала отыскивается начальное допустимое решение, не содержащее искусственных переменных, а затем на основе найденного решения ищется оптимальное решение исходной задачи. Основные шаги, реализации метода следующие.
1. Задача линейного программирования сводится к стандартной форме.
2. Строится искусственный базис.
3. Составляется искусственная целевая функция: сумма всех искусственных переменных.
4. Реализуется первый этап двухэтапного метода: с помощью обычных процедур симплекс-метода выполняется минимизация искусственной целевой функции. Если ее минимальное значение равно 0, то соответствующее решение является допустимым решением исходной задачи. Очевидно, что при нулевом значении искусственной целевой функции все искусственные переменные также нулевые (так как искусственная целевая функция - их сумма, и все они неотрицательны). Если минимальное значение искусственной целевой функции оказывается отличным от нуля, это означает, что задача не имеет допустимых решений.
5. Реализуется второй этап двухэтапного метода: найденное на шаге 4 допустимое решение используется в качестве начального решения исходной задачи для поиска ее оптимального решения.