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

все неизвестные должны быть неотрицательными:

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

Следовательно, целевая функция поставленной перед нами задачи расширения парка оборудования будет иметь следующий вид:

Таким образом, задача оптимального расширения парка оборудования математически формулируется следующим об­ разом.

воряющие ограничениям (1.1)—(1.5) и минимизирующие ли­ нейную функцию (1.8).

4 —460

тельности) двухсторонние ограничения вида

личества изготовляемых деталей /-го вида.

Замечание 1.2. Если на йбременные а,- не накладывать условия целочнсленности, то корректность постановки задачи

не нарушится, так как под дробным количеством оборудова­ ния можно понимать его приобретение не позднее определен­ ного срока в течение планируемого периода. Такая интерпре­

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

Отметим, что частный случай рассматриваемой задачи (при L = l) исследован в работе [11], в которой формулирует­ ся задача оптимального проектирования машинно-тракторно­ го парка, предназначенного для очистки земельных площадей, засоренных твердыми включениями.

Легко заметить, что при фиксированных значениях вели­ чин о.) ограничение (1.3) станет лишним (это означает, что директивно указывается количество приобретаемого обору­ дования всех видов). Если одновременно фиксировать и Ьеличины Qi, то задача 1.1 будет частным случаем известной многоиндексной задачи (см., например [63]).

Перейдем теперь к рассмотрению случая, когда в дейст­ вующем парке и в снабженческой базе имеется только обо­ рудование специального назначения. Тогда экономико-мате­ матическая модель оптимального расширения парка обору­ дования будет иметь достаточно простую структуру. В случае наличия специализированного оборудования каждая техно­ логическая операция будет определять единственный вид оборудования. Это будет означать совпадение индексов i и /. Ясно, что при этом вместо двойного индекса (ij) можем использовать один индекс. Следовательно, если ввести но­ вые обозначения Cji (взамен с,уг), АОт (взамен Ni}i) и tji

50

(взамен tyi), то задача о тимального расширения парка обо­ рудования сформулируется следующим образом.

Задача 1.2 по своей структуре уже достаточно близка к обобщенной распределительной задаче (рассмотренной в ра­

боте [65]), в которой отсутствует только ограничение вида

<1.3').

Замечание 1.3. Величина

£ с, Фу.

у- 1

входящая в выражения целевых функций (1.8) и (1.8')» яв­ ляется постоянной. Следовательно, ее можно исключить из этих выражений. Однако целесообразно в системах нера­ венств (1.1) и (1.Г) соответственно добавить переменные отклонения

и

51

Именно такие представления целевых функций будем иметь в виду при дальнейшем рассмотрении задач 1.1 и 1.2.

§ 2. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧ ОПТИМАЛЬНОГО РАСШИРЕНИЯ ПАРКА ОБОРУДОВАНИЯ

1°. Необходимость разработки специальных алгоритмов. По существу поставленные нами задачи являются задачами линейного программирования*. В принципе их можно решать любым из известных методов решения общей задачи линейно­ го программирования. Однако для этого необходимо приве­

денные здесь задачи заранее привести к канонической форме. В результате таких изменений размеры задач чрезмерно уве­

личиваются, а при больших значениях т, п и L полученная задача может стать практически неразрешимой (в смысле хра­ нения промежуточной информации) даже на современных ЭВМ, обладающих большим объемом запоминающих ус­ тройств. Для ясного представления указанного увеличения размеров матрицы условий задачи рассмотрим процесс при­ ведения задачи 1.1 к общей задаче линейного программиро­ вания. В этой задаче участвуют mnL \-n-\-L неизвестных. Что­ бы ограничения (1.1) и (1.3) представить в виде равенств, необходимо добавить еще п+1 неизвестных отклонения. Та­ ким образом, в задаче будут участвоватьmnL-{-2n-\-L + \ не­ известных величин. Ясно, что можно без особых затруднений ввести единую нумерацию неизвестных с одним индексом.

* Здесь пока не учитываются условия целочисленноети неизвестных.

52

задаче линейного программирования получим матрицу усло­

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

ответствующей задачи линейного программирования будут гро­ моздкими. Так, например, для решения задачи 1.1 симплекс­ ным методом при т — 7 , п—20, L —200, только для хранения

элементов текущей симплексной таблицы потребуется при­ мерно 6,5 млн. ячеек памяти ЭВМ. Эту задачу невозможно решать даже на такой ЭВМ, как «Раздан-3», так как для хранения указанной информации потребуется более двадца­ ти лентопротяжных устройств (в полном комплексе ЭВМ «Раздан-3» имеется 16 лентопротяжных устройств с суммар­ ным объемом 5,12 млн. чисел).

Отметим еще одно важное обстоятельство, показывающее нецелесообразность приведения задачи 1.1 к общей задаче линейного программирования. При увеличении размеров ма­ трицы сильно возрастает не только трудоемкость каждого шага симплексной процедуры*, но и количество шагов. Сле­ довательно, сильно возрастает и необходимое машинное время для решения задачи. А продолжительность процесса решения в определенной степени влияет на надежность работы ЭВМ (особенно на внешние накопители), что во многих случаях приводит к неверным результатам. Кроме того, вследствие ■ограниченности разрядной сетки ячеек памяти, в процессе выполнения арифметических операций возникают и постепен­ но накапливаются неизбежные ошибки. Ясно, что при увели­

* Относительно оценки трудоемкости одного шага симплексной про­

цедуры в зависимости от размеров матрицы см., например, [4].

53