Программные продукты и системы

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

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

В таблицу я поместил основные характеристики ЭВМ (стоимость и объем оперативного запоминающего устройства) и число дефицитных БИС, необходимых для изготовления одной машины:

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

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

БИС № 1 и 2 — это центральные процессоры ЭВМ, БИС № 3 и 4 — блоки памяти, БИС № 5 входит в состав узлов сопряжения с внешними устройствами — дисплеями, принтерами, дисководами.

В последнем столбце таблицы показан максимальный выпуск только одной машины, выпуск которой лимитируется запасом БИС. Это связано с тем, что заводу выделены фонды наполучение 100 БИС № 1, 20 БИС № 2, 500 БИС № 3, 100 БИС № 4 и 1200 БИС № 5. Диктуемые этими ограничениями выкладки и дают цифры, приведенные в последнем столбце таблицы.

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

Во-первых, необходимо насытить рынок компьютерами. Это задача государственной важности. В этом случае нужно максимизировать функцию вида:

К1+К2+КЗ+К4

Здесь К1, К2, КЗ, К4 — план выпуска ЭВМ в штуках по различным четырем типам.

Во-вторых, нужно не забывать и об интересах завода, финансовое положение которого, фонды поощрения и стимулирования зависят от выполнения плана в рублях. Этот показатель ругают все по делу и без дела. Я лично подхожу к этому по-философски и радуюсь, что у нас план в рублях, а не в тоннах, как в некоторых других отраслях промышленности. Не могу даже представить, какие ЭВМ тогда бы мы выпускали. Целевая функция по критерию стоимости имеет вид:

600*К1 +2500*К2+25000*КЗ+60000*К4 Можно, наконец, выпускать компьютеры с максимальной общей емкостью оперативных запоминающих устройств. Этот показатель наряду с быстродействием машины для потребителей часто оказывается определяющим при покупке ЭВМ. Соответствующая целевая функция такова:

16*К1 +32*К2+64*КЗ+512*К4

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

K1+K2s=100

К3+К4=£20

4*К1+8*К2^500

4*КЗ+8*К4=£100

3*К1 +8*К2+15*КЗ+64*К4«:1200

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

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

Программу для решения этой задачи я взял из комплекта программ, приложенного к нашей «Искре-226». Я привожу здесь ее текст на случай, если кто-то любопытный захочет в ней разобраться. Для того, кто работает с ней, особой необходимости в таком разборе нет. Программа сама подсказывает пользователю, что ему надо делать. На дисплее сначала появляется: ЧИСЛО ПЕРЕМЕННЫХ, ОГРАНИЧЕНИЙ? В нашей задаче их 4 и 5. Набираем эти числа. 1-Е ОГРАНИЧЕНИЕ — гласит надпись на дисплее. Потом поочередно в ряд загораются символы переменных с приписанным справа знаком умножения. После появления каждого символа необходимо набрать на клавиатуре значение коэффициента, который на эту переменную умножается. Так постепенно на дисплее выписывается левая часть формулы 1 -го ограничения. Затем следует указать знак неравенства в этой формуле и значение ее правой части (запрос о ней тоже появляется на дисплее).

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

Задача, как я и предполагал, осталась фактически нерешенной. Как истолковать тысячные доли ЭВМ и совет поставлять компьютеры россыпью?

Откуда берутся эти тысячные доли, сообразить нетрудно. Возникают они потому, что некоторые вершины нашего многогранника имеют нецелочисленные координаты. Дробные результаты расчета надо округлять. Но в какую сторону?

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

Эту мысль мне подсказал один простой пример, запомнившийся со студенческой поры. Нужно найти наибольший член последовательности ^гТ, где N — числа натурального ряда. Методы математического анализа требуют заменить последовательность -$ТТ функцией ^Х и искать ее максимум традиционным способом: взять производную и определить ее корень. Он будет равен числу е, основанию натуральных логарифмов — 2,718... Ответ исходной задачи лежит в одной из соседних точек с целочисленными координатами — 2 или 3. Проверим, что подходит, л/2 = 1.4142, а ^3 = 1.4422. Это значит, что ответ равен трем.

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

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

Вот программа, реализующая такой подход. Целевая функция — суммарный объем выпуска ЭВМ. Ее следует максимизировать.

В программе — три вложенных друг в друга цикла, параметры которых — количество выпускаемых ЭВМ второго, третьего и четвертого типов. В строках 20-^80 для каждого сочетания этих параметров определяется возможное число машин первого типа с учетом остатка ресурсов по БИС.

В строке 90 проверяется выполнение ограничений. Они, как и сама целевая функция, могут быть и нелинейными.

В строке 100 каждый раз подсчитывается значение целевой функции. Если новый результат окажется больше найденного ранее, то он выводится на дисплей. Таким образом получается несколько вариантов оптимального плана выпуска ЭВМ. В них мне уже нужно разбираться самому, какой из этих планов самый оптимальный: тут мне ЭВМ вряд ли поможет.

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

Какие выводы можно сделать, глядя на нее?

Самая дефицитная БИС — четвертая. Она почти во всех случаях ограничивает выпуск ЭВМ. Нужно добиться выделения на нее дополнительных фондов или у кого-то на что-то обменять.

Симплекс-метод плохо приспособлен для работы с целочисленными переменными. При поиске оптимального плана с максимальным числом машин данный метод утаил очень выгодные для завода варианты. Можно, оказывается, выпускать те же 120 компьютеров, но с большей общей стоимостью (сравните позиции 1 и 3 итоговой таблицы). При планировании выпуска ЭВМ, если не удастся достать дополнительных БИС, нужно руководствоваться позициями 3 и 8. При этом можно максимально учесть и интересы потребителей (выпуск большого числа недорогих ЭВМ), и интересы производства (вал в рублях).

Позиция 6 с отрицательным числом ЭВМ первого типа получилась по недоразумению. Во второй программе величина К1 не проверялась на неотрицательность, что вообще-то следовало бы сделать. Вот машина и выдала на первый взгляд чепуху. Но только на первый! Компьютер тут выступает в роли беса-соблазнителя, нашептывая плановику крамольную идею: «Купи где-нибудь на стороне 27 дешевых ЭВМ первого типа, разбери их, а дефицитные БИС пусти на производство более дорогих машин. План по валу в рублях будет перевыполнен!»

И теперь о моих мечтах плановика-экономиста.

Хорошо бы, если бы моя ЭВМ соединялась с аналогичной машиной моего коллеги на заводе, выпускающем БИС, — так, как она, например, соединяется со своим дисководом. Это, я знаю, можно сделать через телефонный кабель. Я передал бы моему товарищу описание задачи с таблицей результатов расчета. Как человек разумный, он сделал бы те же выводы, что и я, и сказал бы, вероятнее всего, так: «Для нашего завода ничего не стоит изменить номенклатуру поставок. Мы просто толком не знаем, что нужно нашим потребителям, и гоним тот же вал, опираясь на цифры, взятые с потолка каким-то дядей в министерстве».

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