10 — hi -4 < 6 2 < 10 -8 А3 19...
6.4). Общая стоимость брака по первому плану (у) составляла: т п Уі ZZrv =8x2+4x20+3x9+2x10+3x12 + ;=i j=i +2x7 +8 x 12 +5x4 = 309. После улучшения плана стоимость брака Ау уменьшилась на следующую величину: Ау = С2фі — Ciihi + C42hi — С41Й1 = hi (C2i — C22 + C42 — C41) = = (3 - 3 + 5 - 8) 9 = 27. Общая стоимость брака по второму плану (У2) будет: Уг = у\~ - Ау= 309 - 27 = 282. При проверке второго плана на оптимальность устанавливаем, что условие оптимальности не соблюдено в клетках А| и А4Б3, причем последняя из них имеет наибольшую разность между псевдостоимостью и стоимостью. Строим контур относительно указанной клетки (см. табл. 6.5). Величина дополнительного количества рабочих Л2 = 3. После перераспределения рабочих получим третий план (табл. 6.6), который экономичнее второго на величину Ау: Ау = = (С43 - С41 + С21 - С23)й2 = (4 - 8 + 3 - 2) 3 = -9. ' Таблица 6.6 Третий план (оптимальный) Бригады Виды работ Бі 24 Б2 15 Бз 10 Б4 20 Б5 7 «А; Ai 22 8 < 12 8 2 7 < 10 4 20 7 < 9 0 А2 19 3 12 3 = 3 2 7 -1 < 6 2 < 10 -5 А, 19 3 12 3 < 7 2 < 10 -1 < 3 2 = 2 -5 А4 16 5 < 8 5 13 4 3 1< 3 4 < 5 - 3 "Б/ 8 8 7 4 7 Стоимость брака по третьему плану, таким образом, равна: уз = = у2~ Ау = 282 - 9 = 273. Проверка условия оптимальности показывает, что третий план является оптимальным. Заметим, что оптимизация плана распределения рабочих-спе - циалистов по видам работ привела к сокращению брака (по его f309 — 273 ^ стоимости) на 12% I—^^—100 I. И это улучшение качества достигнуто без ввода каких-либо дополнительных ресурсов, исключительно за счет составления обоснованного плана. Пример 6.4 Имеется т (/= 1, 2, ..., т) инвестиционных возможностей (вариантов проектов), которые можно реализовать на п (j= 1, 2,..., п) объектах. Эффективность реализации каждой инвестиции на каждом из объектов (Pj) задана табл. 6.7. Таблица 6.7 Эффективности реализации инвестиционных проектов Инвестицион Объекты (/) ные проекты (/) I II III IV V 1 0,12 0,02 0,50 0,43 0,15 2 0,71 0,18 0,81 0,05 0,26 3 0,84 0,76 0,26 0,37 0,52 4 0,22 0,45 0,83 0,81 0,65 5 0,49 0,02 0,50 0,25 0,27 Целевая функция, подлежащая максимизации (у), будет: т п у II/'V - (б. зб) ;=i j=I где Xjj — искомые распределения инвестиций по объектам. Таким образом, по смыслу, величина у есть ожидаемый результат от осуществления всех инвестиционных проектов. Ограничения в данном случае будут: т І-V к/ 1-2— /п). (6.37) ;=1 означающее, что должны быть реализованы все проекты, и І-V п./ 1.2..../,). (6.38) J=І означающее, что на каждом объекте может быть реализован лишь один проект. Кроме того, очевидно, что Ху > 0. (6.39) Необходимо распределить проекты по объектам таким образом, чтобы суммарная эффективность от реализации всех проектов была максимальной. Решение Оптимизируемая функция, а также ограничивающие ее условия соответствуют данным, приведенным выше, при постановке транспортной задачи. Это дает возможность применить метод по-тенциалов (несколько его видоизменив). По аналогии с транспортной задачей вероятности поражения играют роль стоимости перевозок; каждой ракете соответствует как бы единичный запас груза, каждая цель нуждается в единице груза. Исходя из сказанного, представим условие примера 6.4 в виде табл. 6.8. Вначале составим исходный план, заполняя в первую очередь те клетки, где эффективность выше. Заполнение начинаем с первой строки. Схематическое изображение полученного исходного плана дано на рис. 6.2. Для первого плана математическое ожидание числа пораженных целей Уі = 0,50 + 0,71 + 0,76 + 0,81 + 0,27 = 3,05. Таблица 6.8 Условие примера 6.4 Инвестиционные проекты Объекты I бх= 1 II б2 = 1 III б3 = 1 IV б4 = 1 V б5= 1 а, 1 ai = 1 0,12 0,02 0,50 1 0,43 0,15 1 2 а2 = 1 0,71 1 0,18 0,81 0,05 0,26 1 3 а3 = 1 0,84 0,76 1 0,26 0,37 0,52 1 4 а4 = 1 0,22 0,45 0,83 0,81 1 0,65 1 5 35 = 1 0,49 0,02 0,50 0,26 0,27 1 1 б; 1 1 1 1 1 1 Чтобы улучшить исходный план методом потенциалов, прибегаем к следующему искусственному приему. Внесем дополнительные «перевозки», выраженные в величинах є, в каждую строку плана, одновременно изменив для сбалансирования плана единицы перевозок, стоящие в соответствующих вертикалях и горизонталях. объекты проекты Рис. 6.2 Для того чтобы такие действия не вызывали искажения плана, величина є считается сколь угодно малой, и поэтому для плана добавление или исключение ее оказывается несущественным. Перепишем исходный план с учетом вышеизложенных изменений (табл. 6.9). Проверим первый план на оптимальность аналогично тому, как это делалось в предыдущих задачах. Здесь условие оптимальности не соблюдается в тех клетках, где псевдостоимости меньше, чем стоимости (в клетках 1—II, 1—IV, 1-У, 2—IV, 2-V, 3-V). Наибольшая разность в кле тке 1—IV, в которую нужно внести дополнительную «перевожу» Л|. Относительно указанной клетки строим контур. Величина 1ц = Б. После перераспределения груза в контуре получим второй план, улучшенный по сравнению с исходным (табл. 6.10). Проверим полученный план на оптим
альность. Обнаружив, что он неоптимален, произведем его улучшение путем построения контура относительно свободной клетки 2—V. При ЭТОМ /?2 = Б. Перейдем к третьему плану (табл. 6.11). Дальнейшее улучшение плана выполняется аналогичным путем. Улучшенные планы сведены в таблицы. Четвертый — в табл. 6.12, пятый — в табл. 6.13, шестой — в табл. 6.14. Последний, шестой план является оптимальным, ибо все разности между псевдостоимостями и стоимостями положительные. Перепишем оптимальный план, исключив из него сколь угодно малые величины Б (табл. 6.15). X 5 Таблица 6.15 Оптимальный план Инвестицион Объекты ные проекты I II III IV V 1 1 2 1 3 1 4 1 5 1 Графически оптимальный план распределения проектов показан на рис. 6.3. объекты Рис. 6.3 НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ (ПЛАНИРОВАНИЕ) Нелинейное программирование (планирование) — математические методы отыскания максимума или минимума функции при наличии ограничений в виде неравенств или уравнений. Максимизируемая (минимизируемая) функция представляет собой принятый критерий эффективности решения задачи, соответствующий поставленной цели. Он носит название целевой функции. Ограничения характеризуют имеющиеся возможности решения задачи.
