Файл: Математическое программирование и производственные задачи..pdf

ции второго вида требуется 10,6 станко-часов работы обору­ дования третьей группы. Сумма элементов каждого столбца

означает, что дЛя изготовления единицы продукции третье­ го вида используется 153,7 станко-часов по всем группам оборудовайия).

Т а б л и ц а 3 .J*

Трудоемкость выпускаемой продукции (в станко-часах)

. . .

* Таблица 3.1 (как и табл. 3.2) приведена в сокращенном виде. Строки от четвертой до двадцать первой и столбцы от четвертого до тридцатого оцущены.

7 7

В табл. 3 2 приведены расходы сырья, основных и вспомо­ гательных материалов, а также покупных полуфабрикатов и малоценных изделий (/=121) для изготовления единицы про­ дукции (я=31). Так например, число 2,3, стоящее на пересе­ чении 119-ой строки и третьего столбца, показывает, что для изотовления единицы продукции третьего вида требуется из­

расходовать 2,3 ед. материала 119-го вида. В последнем столбце приведены запасы материалов (по видам).

В результате решения задачи получаем, что объем реали­ зуемой продукции по оптимальному плану составляет 40,2 мил­ лиона рублей вместо 36,8 миллиона рублей, т. е. увеличивает­ ся на 9,2%. Прибыль предприятия по оптимальному плану увеличивается на 11,3%, а фондоотдача по реализуемой про­ дукции—на 8,7%. Коэффициент использования основных фондов от 62,3% повысился до 81,2%, а для активной части (технологического оборудования) фондов—от 68,7 до 91,8%.

Примерно такая же картина наблюдается на остальных предприятиях исследуемой отрасли.

Вышеприведенные задачи с некоторыми упрощениями ре­ шались методом целочисленного линейного программирова­ ния на ЭВМ «Раздан-2». Метод решения и вычислительная схема приведены в следующем параграфе.

§4. АЛГОРИТМ РЕШЕНИЯ ОБЩЕЙ ЦЕЛОЧИСЛЕННОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Многие задачи оптимального планирования дискретного производства по существу являются целочисленными задача­ ми линейного программирования. Часто для решения нелиней­ ных (особенно многоэкстремальных) задач возникает необхо­ димость решать серию целочисленных задач линейного про­ граммирования.

Р. Гомори дал алгоритм решения целочисленной задачи линейного программирования [19, 20] при следующих пред­ положениях:

1) известно базисное допустимое решение двойственной задачи, причем все элементы преобразованной внебазисной матрицы целочисленны;

78

2) двойственные задачи, используемые в процессе реше­ ния, невырождены.

Легко показать, что, пользуясь способом преодоления возможных зацикливаний при решении вырожденных (в двойственном смысле) задач, можно избавиться от предпо­ ложения 2). Но предположение 1) довольно сильно сужает

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

Алгоритм решения общей целочисленной задачи, предло­ женный Мещеряковым [ 7 ], содержит довольно большой объ­ ем вычислений и, кроме того, требует дополнительной проце­ дуры нахождения всех допустимых базисных решений задач линейного программирования.

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

при условиях

79

чтй эти предположения не нарушают общности постановки задачи).

Как известно, задача (4.1) — (4.4) без условия (4.4) явля­ ется обШей задачей линейного программирования и лег­ ко решается так называемым Л1-методом. Поэтому естественно задачу (4.1) — (4.4) называть общей целочисленной задачей линейного программирования^

Сформулируем расширенную задаНу (М —задачу), соот­ ветствующую задаче (4.1) — (4.4). Для простоты дальнейшего изложения здесь :не будем отличать искусственные и основ­ ные переменные. Поэтому все переменные расширенной задачи будем обозначать символом х с единой нумерацией

логична связи между общей задачей линейного программиро­

(4.Г) — (4.4') содержит искусственные переменные). Основы­

80

сводится к последовательному применению симплексных пре­

торой применяем один шаг симплексного преобразования. В

является целочисленной неотрицательной переменной при лю­

Опишем произвольный шаг алгоритма решения задачи (4.Г) — (4.4'). Проверяем признак оптимальности. При его обеспечении анализируем коэффициент при М в выражении целевой функции (4.Г ). Если этот коэффициент отличен от нуля, то задача (4.1) — (4.4) не имеет решения, в противном случае получено оптимальное решение. Если признак опти­ мальности не обеспечен, то генеральный столбец выбираем так, как в обычном методе последовательного улучшения плана. Отсутствие положительного элемента в генеральном столбце

тельно, и функция (4.1) не ограничена на множестве допусти-

81

6—450