2.3. Фирма АгкТес собирает персональные компьютеры для частных клиентов. На следующие четыре квартала имеются заказы на 400, 700, 500 и 200 компьютеров соответственно. Фирма может производить больше компьютеров, чем указано в заказах, но в таком случае приходится платить 100 долл. за хранение одного компьютера в течение квартала. Увеличение производства в следующем квартале, по сравнению с предыдущим, приводит к дополнительному набору работников, что повышает себестоимость одного компьютера на 60 долл. При уменьшении производства в следующем квартале, по сравнению с предыдущим, придется прибегнуть к сокращению персонала, что также увеличивает себестоимость одного компьютера на 50 долл. Как организовать сборку компьютеров, чтобы удовлетворить все заказы?
2.4. Мебельная фабрика осуществляет производство и сборку стульев, столов и книжных полок. Заготовительный цех производит продукцию, которая затем собирается в сборочном цехе фабрики.
Ежемесячная производительность заготовительного цеха составляет 3000 стульев, 1000 столов и 580 книжных полок (несобранных). В сборочном цехе работают 150 рабочих в две 8-часовые смены 5 дней в неделю. Среднее время сборки одной единицы продукции равно 20, 40 и 15 минут соответственно для стульев, столов и книжных полок.
Количество рабочих в сборочном цехе колеблется в зависимости от того, сколько человек в настоящее время находится в ежегодном отпуске. В мае, июне и июле планируют уйти в отпуск соответственно 20, 25 и 45 человек.
Отдел маркетинга фабрики оценил потребность рынка в их продукции на май, июнь и июль следующим образом.
Продукт | Май Июнь | Июль | Остаток на конец апреля |
Стул | 2800 2300 | 3350 | |
Стол | 500 800 | 1400 | |
Книжная полка | 320 300 | | |
Себестоимость продукции и ее отпускная цена показаны в следующей таблице. |
Продукт | Себестоимость (долл.) | Отпускная цена (долл.) |
Стул | | | |
Стол | | | |
Книжная полка | | | |
Если какая-либо продукция не продана в течение того месяца, в каком она произведена, то она может быть продана в следующем месяце. Хранение одной единицы стоит 2% от стоимости этой продукции.
Помогите фабрике разработать план ежегодных отпусков для работников сборочного цеха.
ГЛАВА 3
СИМПЛЕКС-МЕТОД
Графический способ решения задачи ЛП из главы 2 показывает, что оптимальное решение этой задачи всегда ассоциируется с угловой точкой пространства решений (в математике она также называется крайней точкой множества). Это является ключевой идеей при разработке общего алгебраического симплекс-метода для решения любой задачи линейного программирования.
Переход от геометрического способа решения задачи ЛП к симплекс-методу лежит через алгебраическое описание крайних точек пространства решений. Для реализации этого перехода сначала надо привести задачу ЛП к стандартной форме, преобразовав неравенства ограничений в равенства путем введения дополнительных переменных.
Основное свойство симплекс-метода заключается в том, что решение задачи ЛП осуществляется итерационно. На каждой итерации алгоритм переходит к новой угловой точке, которая потенциально может улучшить значение целевой функции. Этот процесс перехода от одной угловой точки к следующей заканчивается, когда дальнейшее улучшение значений целевой функции невозможно.
Процесс реализации симплекс-метода включает большое количество однотипных громоздких и утомительных вычислений. Это делает компьютер незаменимым инструментом для решения задач линейного программирования, поскольку вычислительный алгоритм симплекс-метода позволяет сравнительно легко автоматизировать вычислнения.
3.1. СТАНДАРТНАЯ ФОРМА ЗАДАЧИ ЛП
Стандартная форма записи задачи ЛП предполагает выполнение следующих требований.
1. Все ограничения (включая ограничения неотрицательности переменных) преобразуются в равенства с неотрицательной правой частью.
2. Все переменные неотрицательные.
3.1.1. Преобразование неравенств в равенства
Неравенства любого типа (со знаками неравенств < или >) можно преобразовать в равенства путем добавления в левую часть неравенств дополнительных переменных - остаточных или избыточных1, которые связаны с неравенствами типа "<" и ">" соответственно.
1 Отметим, что в русской язычной математической литературе для этих типов переменных не используются какие-либо специальные названия - они известны просто как дополнительные переменные (хотя иногда их также называют балансными). В неравенствах они различаются тем, что перед остаточной переменной всегда стоит знак " плюс", а перед избыточной - " минус". - Прим. ред.
Для неравенств типа "<" в левую часть неравенства вводится неотрицательная остаточная переменная. Например, в модели компании Reddy Mikks (пример 2.1.1) ограничение на количество сырья Ml задается в виде неравенства 6х, + 4х2 < 24. Вводя новую неотрицательную переменную s,, которая показывает остаток (неспользованное количество) сырья Ml, это ограничение преобразуется в равенство
6x,+4x2 + s1 = 24, s,>0.
Неравенства типа ">" в задачах ЛП обычно устанавливают нижнюю границу чего-либо. Избыточная переменная определяет превышение значения левой части неравенства над этой границей. Так, в модели "диеты" (пример 2.2.2) неравенство х, + х2 > 800 показывает, что суточное производство пищевой добавки не должно быть меньше 800 фунтов. Математически это неравенство эквивалентно равенству
х, + х2 - S, = 800, S, > 0.
Положительное значение избыточной переменной S, показывает превышение суточного производства добавки над минимальным значением в 800 фунтов.
Важно еще раз подчеркнуть, что дополнительные переменные - остаточная s, и избыточная S, - всегда неотрицательные.
Правую часть равенства всегда можно сделать неотрицательной, умножив все равенство на -1. Кроме того, заметим, что неравенство типа "<" также преобразуется в неравенство типа ">" посредством умножения обеих частей неравенства на -1. Например, неравенство -х, + х2 < -3 эквивалентно равенству
-х, + х2 + s, = -3, s, > 0.
Теперь, умножая обе части этого равенства на -1, получим равенство с неотрицательной правой частью: х, - х2 - s, = 3.
УПРАЖНЕНИЯ 3.1.1
1. В модели компании Reddy Mikks (пример 2.2.1) рассмотрите допустимое решение х, = 3 т и х2 = 1 т. Для этого решения найдите недоиспользование сырья Ml и М2.
2. В модели "диеты" (пример 2.2.2) определите превышение над минимальным допустимым объемом производства пищевой добавки, на которую расходуется 500 фунтов кукурузной муки и 600 фунтов - соевой.
3. Дано неравенство 10х,-Зх2>-5. Покажите, что в результате преобразования, когда сначала обе части неравенства умножаются на -1, а затем неравенство преобразуется в равенство, получется такое же равенство, что и в результате преобразования, когда сначала исходное неравенство преобразуется в равенство, а затем умножается на -1.
4. Два изделия, Р1 и Р2, можно произвести на двух различных станках Ml и М2. Время изготовления любого изделия на любом станке одинаково. Производительность станка Ml составляет 200 изделий за смену, а производительность станка М2 - 250 изделий. Мастер планирует сбалансировать рабочее время таким образом, чтобы общее количество изделий, произведенных на одном станке, не превышало более чем на 5 единиц общее количество изделий, изготовленных на другом станке. Доход от одного изделия Р1 составляет 10, а от второго - 15 долл. Запишите эту задачу в стандартной форме линейного программирования.