Комплексные задачи 93

2.2. 9 Сталелитейная компания имеет литейный цех и два прокатных стана. Литейный цех производит три типа стальных заготовок, которые, прежде чем попасть на прокатные станы, обрабатываются в механическом цехе.

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

т,.г, ттп, . Длина заготовки Внутренняя цена Цена на рынке

j ип заготовки . . .

(футы) (в долл. на одну заготовку) (в долл. на одну заготовку)

1 800 90 108

2 1200 130 145

3 1650 180 194

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

Составьте оптимальный производственный график для механического цеха.

9 Взято из S. Jain, К. Stott, Е. Vasold. Orderbook Balancing Using a Combination of Linear Programming and Heuristic Techniques , Interfaces, Vol. 9, No. 1, November 1978, pp. 55-67.

2.3. Фирма АгкТес собирает персональные компьютеры для частных клиентов. На следующие четыре квартала имеются заказы на 400, 700, 500 и 200 компьютеров соответственно. Фирма может производить больше компьютеров, чем указано в заказах, но в таком случае приходится платить 100 долл. за хранение одного компьютера в течение квартала. Увеличение производства в следующем квартале, по сравнению с предыдущим, приводит к дополнительному набору работников, что повышает себестоимость одного компьютера на 60 долл. При уменьшении производства в следующем квартале, по сравнению с предыдущим, придется прибегнуть к сокращению персонала, что также увеличивает себестоимость одного компьютера на 50 долл. Как организовать сборку компьютеров, чтобы удовлетворить все заказы?

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

Ежемесячная производительность заготовительного цеха составляет 3000 стульев, 1000 столов и 580 книжных полок (несобранных). В сборочном цехе работают 150 рабочих в две 8-часовые смены 5 дней в неделю. Среднее время сборки одной единицы продукции равно 20, 40 и 15 минут соответственно для стульев, столов и книжных полок.

Количество рабочих в сборочном цехе колеблется в зависимости от того, сколько человек в настоящее время находится в ежегодном отпуске. В мае, июне и июле планируют уйти в отпуск соответственно 20, 25 и 45 человек.

Отдел маркетинга фабрики оценил потребность рынка в их продукции на май, июнь и июль следующим образом.

Если какая-либо продукция не продана в течение того месяца, в каком она произведена, то она может быть продана в следующем месяце. Хранение одной единицы стоит 2% от стоимости этой продукции.

Помогите фабрике разработать план ежегодных отпусков для работников сборочного цеха.

ГЛАВА 3

СИМПЛЕКС-МЕТОД

Графический способ решения задачи ЛП из главы 2 показывает, что оптимальное решение этой задачи всегда ассоциируется с угловой точкой пространства решений (в математике она также называется крайней точкой множества). Это является ключевой идеей при разработке общего алгебраического симплекс-метода для решения любой задачи линейного программирования.

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

Основное свойство симплекс-метода заключается в том, что решение задачи ЛП осуществляется итерационно. На каждой итерации алгоритм переходит к новой угловой точке, которая потенциально может улучшить значение целевой функции. Этот процесс перехода от одной угловой точки к следующей заканчивается, когда дальнейшее улучшение значений целевой функции невозможно.

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

3.1. СТАНДАРТНАЯ ФОРМА ЗАДАЧИ ЛП

Стандартная форма записи задачи ЛП предполагает выполнение следующих требований.

1. Все ограничения (включая ограничения неотрицательности переменных) преобразуются в равенства с неотрицательной правой частью.

2. Все переменные неотрицательные.

3.1.1. Преобразование неравенств в равенства

Неравенства любого типа (со знаками неравенств < или >) можно преобразовать в равенства путем добавления в левую часть неравенств дополнительных переменных - остаточных или избыточных1, которые связаны с неравенствами типа < и > соответственно.

1 Отметим, что в русской язычной математической литературе для этих типов переменных не используются какие-либо специальные названия - они известны просто как дополнительные переменные (хотя иногда их также называют балансными). В неравенствах они различаются тем, что перед остаточной переменной всегда стоит знак плюс , а перед избыточной - минус . - Прим. ред.