«• Ерин В.Г. • Ткаченко О.В. • Христиановский В.В. МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ Методическое пособие и контрольные задания ( для студентов-заочников экономических специальностей ) Донецк, ДонНУ-2000 УДК 519.85/075.8/ ...»

Таблица 9. В целевой строке табл. 9.11 получено:

- для столбика - для столбика - для столбика Чтобы найденное решение X Б оставалось оптимальным, надо, чтобы относительные данциговские оценки во внебазисных столбиках A2 и A оставались неотрицательными, т.е. чтобы параметр t1 удовлетворял неравенствам В итоге должно быть t1 0.

Т.к. 1-я цена равна 9 + t1, то диапазон устойчивости по 1-й цене :

Аналогичное в анализе проделывается и для второй цены. Копируется таблица 9.10, но с новым обрамлением для цены 2-го товара. Именно эта цена считается равной Делается также новый расчет элементов (m + 1)-й строки. Получаем таблицу 9.12.

Таблица 9. Элементы целевой строки (относительные данциговские оценки) для табл. 9. равны:

Для столбика Для столбика Видно, что зависимость от t2 имеет место лишь по столбику A2.

Для сохранения признака оптимальности должно быть соблюдено неравенство (-t2) 0 или t2 0. А т.к. цена 2-го товара равна 6 + t2, то c2 ограничено сверху первоначально заданной ценой c2 = 6.

Итак, диапазон устойчивости равен - < c2 6. В силу того, что цена не может быть отрицательной, имеем реальный диапазон устойчивости:

Вывод. Оптимальный план выпуска товаров x0 = (14, 0) остается оптимальным, если фиксирована цена c2 = 6 и 9 c1 < +, или если фиксирована цена c1 = 9 и

§ 10. ЗАДАЧИ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ

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

Плановую целочисленную задачу линейного программирования можно поставить следующим образом: найти такие значения переменных xj (j = 1,n ), которые удовлетворяют следующим условиям :

и приносят требуемый экстремум целевой функции Если в условии (10.2) K = n, то мы имеем дело с полностью целочисленной задачей, если же К < n, то задача (10.1) - (10.4) является частично целочисленной.

В зависимости от содержания задачи целевая функция (10.4) или максимизируется, или минимизируется. Модель поставленной задачи отличается от модели задачи линейного программирования только наличием дополнительного условия (10.2).

Для решения целочисленных задач используются две группы методов:

методы отсечения и комбинаторные методы. Мы рассмотрим методы отсечения.

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

Рассмотрим алгоритм решения полностью целочисленной задачи.

- Умножением каждого из неравенств (10.3) на необходимое число добиваемся, чтобы в системе (10.3) все коэффициенты и свободные члены стали целыми числами.

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

превосходящее b, через [b], то дробной частью числа b называется разность b – [b], которую мы обозначим через. Например, пусть b = -3,7, тогда [b] = -4 и = -3,7 - (-4) = 0,3; пусть b = -0,3, тогда [b] = -1 и = -0,3 + 1 = 0,7; b = 2,3, тогда [b] = 2 и = 2,3 - 2 = 0,3. Усвоив понятие дробной части числа, можно осваивать дальнейшие пункты алгоритма.

- Итак, пусть среди координат оптимального решения имеются дробные.

Выберем ту из них, дробная часть которой самая большая. Пусть это будет координата xS = bS, соответствующая S-й строке таблицы, в которой получен оптимальный, но не целочисленный результат. В силу коэффициентов этой строки и будет построено отсечение. Для строки c bS справедлива следующая общая запись:

Для всех чисел bSK и bS определяем их дробные части SK и S. Тогда отсечение примет вид следующего неравенства:

или с введением дополнительной балансирующей переменной запишется в виде уравнения которое как раз и будет добавляться в последнюю таблицу для продолжения решения. Переменная 1 уже будет (n + 1) - й переменной нашей задачи. Эта переменная будет взята в качестве базисной и для нее будет введен дополнительный столбик. Введение указанной строки как раз делает недопустимым полученный результат в расширенном пространстве переменных (х1, х2, …, хn, 1 ). Ведь в этом решении, если считать все свободные переменные равными нулю, имеем 1 = - S < 0, но 1 введена с условием своей неотрицательности.

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

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

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

и приносить минимум целевой функции Так как в неравенствах коэффициенты и свободные числа суть целые числа, то мы сразу же приводим нашу задачу к каноническому виду:

Здесь переменные x3, x4 - балансирующие и их тоже можно считать целочисленными. Отобразим нашу задачу в табл. 10.1.

Таблица 10.1.

Этой таблице соответствует базисное решение (0, 0, 5, 2), которое отвечает требованиям целочисленности, но не является оптимальным. Наметив разрешающий элемент, делаем пересчет к новой табл. 10.2.

Таблица 10. Табл. 10.2 соответствует то же целочисленное решение (0, 2, 1, 0), но оно oпять-таки не является оптимальным. Наметив разрешающий элемент, делаем пересчет к табл. 10.3.

Таблица 10. Итак, в табл. 10.3 получен оптимальный результат x = (1/3, 2, 0, 0). К сожалению, первая компонента этого ответа не отвечает требованию целочисленности. Поэтому нам придется вводить отсечение. Для базисной переменной x1 в первой строке табл. 10.3 мы имеем следующее уравнение:

По отношению к этому уравнению, т.е. по отношению к первой строке табл. 10.3, мы будем вводить отсечение. Дробная часть коэффициента при x1 равна 0, при x - тоже равна 0, при x3 дробная часть равна 1/3, при x4 дробная часть равна 1/3.

Дробная часть свободного члена первой строки равна 1/3. Учитывая это, в силу (10.7) получаем дополнительное уравнение введение которого в табл. 10.3 приводит к табл. 10.4.

Таблица 10. В расширенном пространстве переменных x1, x2, x3, x4, 1 в соответствии с табл.

10.4 мы имеем дело с решением (1/3, 2, 0, 0, -1/3), которому соответствует признак оптимальности, но которое не являете допустимым из-за отрицательности пятой компоненты. Строка A1 выбирается в качестве разрешающей. В этой строке согласно принципам двойственного симплексметода можно в качестве разрешающего элемента взять либо (- 1/3) в столбце А или (-1/3) в столбце А4. Пусть в качестве разрешающего элемента в табл. 10. взят элемент (- 1/3) в столбце А3. Симплексный пересчет приводит нас к табл.

10.5.

Таблица 10. Этой таблице уже соответствует оптимальный целочисленный ответ Х цч = (0, 2, 1, 0). При этом zmin = -2. Кстати, если бы мы в качестве разрешающего элемента в табл. 10.4 взяли элемент (-1/3) из столбца А4, то пришли бы также к оптимальному решению (1, 1, 0, 0).

§ 11. РЕШЕНИЕ МАТРИЧНЫХ ИГР Пусть рассматривается матричная игра в которой так называемый строчный игрок имеет m различных стратегий (m строк), а столбцевой - n стратегий (n столбцов), причем каждое число aij (i=1, m; j=1, n ) - это платеж строчному игроку, если строчный выбрал i-ю стратегию, а столбцевой j-ю стратегию. Ясно, что если строчный игрок выбрал iю строку (стратегию), столбцевой j-й столбец (стратегию) и при этом aij=0, то это ничейный результат, т.е. ни один из игроков не получает какого-либо выигрыша.

Если aij положительное число, то в выигрыше строчный игрок. Если же aij отрицательное число, то в выигрыше столбцевой игрок и он получает выигрыш [aij].

Решение игры состоит в поиске оптимальных стратегий для каждого из игроков. Поскольку элементы матрицы A - это платежи строчному игроку, то строчный игрок является максимизирующим в выборе своей строки, а столбцевой – минимизирующим в выборе столбца. Но это не значит, например, что строчный игрок сориентируется на r-ю строку (стратегию), в которой находится самый большой элемент матрицы ars. Ведь предполагается, что противник (т.е. в данном случае столбцевой игрок) столь же разумен и выбирает в качестве своей стратегии не s-й столбик, а другой какой-либо p-й столбик и элемент arp будет даже проигрышным для строчного игрока. Учитывая сказанное, строчный игрок сначала в каждой строке находит минимальный элемент, а потом выбирает ту строку для реализации, в которой находится самый большой элемент из минимальных. Величина этого элемента будет гарантированным выигрышем для строчного игрока. Итак, строчный игрок для каждой i-й строки определяет а затем находит максимальный элемент из i (i=1, m ). Пусть этим элементом оказался элемент из k-й строки, т.е.

Тогда строчному игроку ясно, что если он будет ориентироваться на выбор kй строки, то ему обеспечен выигрыш не менее =k. Кстати, эту величину в теории матричных игр называют нижней ценой игры, заданной матрицей A. В силу сказанного для нижней цены справедлива следующая синтезирующая запись:

Столбцевой игрок (т.е. игрок, имеющий право выбирать столбцы) поступает столь же разумно. Понимая, что элементы aij матрицы A суть платежи строчному игроку, столбцевой игрок в каждом своем столбике j находит максимальный элемент j:

а затем выбирает тот столбик, которому соответствует наименьшее из чисел j (j1, n ). Пусть таким столбиком оказался l-й, т.е.

Такими своими действиями столбцевой игрок не позволит получить строчному выигрыш, превышающий l =. Величину называют верхней ценой игры, причем можно записать В теории игр строго доказано, что всегда имеет место соотношение Особый класс составляют те игры, для которых величины максимина и минимакса совпадают, т.е. когда =. Говорят, что в таких случаях игра имеет седловую точку. Если = k и = l, то в качестве седловой точки выступает элемент akl платежной матрицы A. Или говорят, что akl - седловой элемент. В матричной игре седловых точек (элементов) может быть более одной (одного).

Рассмотрим матричную игру В этой игре строчный игрок имеет 4 стратегии (строки), столбцевой – стратегий (столбцов). Строчный игрок определяет свои минимально возможные выигрыши при выборе каждой из строк:

Соответственно находим Итак, нижняя цена игры Столбцевой игрок определяет свои максимальные проигрыши в столбцах:

а затем ориентируется на такой столбик (стратегию), чтобы строчный выиграл как можно меньше. Для этого находится Итак, верхняя цена игры Для рассматриваемой игры мы можем констатировать совпадение максимина и минимакса, т.е. = = 3 = 2 = a32. По определению элемент a будет называться седловым. В нашей игре мы имеем одну седловую точку. В общем случае игра может не иметь седловых точек или иметь более одной седловой точки.

Если игра имеет седловую точку, например akl, то решение игры состоит в выборе так называемых чистых стратегий: строчному игроку следует выбирать kю строку (стратегию), а столбцевому l-й столбец (стратегию). В противном случае строчный игрок всегда может поступить так, что он получит более высокий выигрыш или по крайней мере не меньший чем akl, а столбцевой игрок может поступить так, что он проиграет меньше или по крайней мере не больше чем akl.

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

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

(Отдельная партия состоит в том, что строчный называет некоторую стратегию, а столбцевой - µ-ю стратегию и соответственно строчному идет платеж aµ). При проведении серии партий возникает вопрос о том, насколько часто следует пользоваться игрокам своими стратегиями. Обозначим через pi - вероятность выбора i-й строки строчным игроком и qj - вероятность выбора j-го столбца столбцевым игроком. Задача состоит в определении таких значений pi (i=1, m ) для строчного игрока и таких qj (j1, n ) для столбцевого игрока, чтобы строчному игроку в среднем за одну партию получить выигрыш более, а столбцевому игроку проигрывать менее. Этот проигрыш-выигрыш назовем ценой игры и обозначим через v, причем < v <. С помощью введенных вероятностей выбора стратегий матричную игру можно свести к паре двойственных задач линейного программирования.

Итак, рассматриваем платежную матрицу (11.1) размерности m n без седловой точки. Будем считать все элементы этой матрицы неотрицательными.

Если это условие не выполняется, то ко всем элементам матрицы прибавляем одно и то же достаточно большое число k, переводящее платежи в область неотрицательных значений. При этом сущность решения задачи не изменится и лишь цена игры увеличится на величину k. Итак, можно считать, что цена игры v Наборы вероятностей выбора каждой стратегии для строчного и столбцевого игроков будем называть смешанными стратегиями этих игроков: p0 = (p1, p2, …, pm) - для строчного и q0 = (q1, q2, …, qn) - для столбцевого игрока. При этом для дальнейшего следует не забывать, что p1 + p2 + …+ pm=1 и q1 + q2 + …+ qn =1.

Применение строчным игроком оптимальной смешанной стратегии гарантирует ему выигрыш не меньше цены игры v, причем это вне зависимости от стратегий столбцевого игрока. Пусть, например, столбцевой игрок в серии партий все время применяет j-ю чистую стратегию (выбирает j-й столбик матрицы A), а строчный игрок применяет оптимальную смешанную стратегию p0 = (p1, p2, …, pm). Тогда средний выигрыш строчного игрока будет vj = a1jp1 + a2jp2 + …+ aijpi + …+ amjpm при любом j1, n. Так как в рассматриваемой ситуации имеются в виду оптимальность поведения строчного игрока и неоптимальность повтора чистой jв сериях партий, то vj v (j1, n ), где v - цена игры, й стратегии соответствующая оптимальному поведению игроков. Сказанное позволяет нам зафиксировать следующие неравенства:

Разделив левые и правые части этих неравенств на v > 0 и введя обозначения = x i (i = 1, m), из (11.2) получим

Учитывая, что p1 + p2 + …+ pm=1 и имея в виду введенные обозначения x i = i, можно считать, что переменные xi подчиняются условию А так как строчный игрок максимизирует цену игры, то минимизируется и получается естественная целевая функция в линейной форме Записи (11.3), (11.4), (11.5) составляют некоторую задачу линейного программирования: найти такие значения x1, …, xm, которые отвечают условиям

и приносят минимум целевой функции Теперь полагаем, что в сериях партий столбцевой игрок поступает оптимальным образом, т.е. ориентируется на применение оптимальной смешанной стратегии q0 = (q1, q2, …, qn), а строчный игрок неоптимальным образом использует чистые стратегии. Тогда по аналогии с (11.2) получаем

Разделив обе части этих неравенств на v > 0 и введя обозначения

где все yi 0 (j=1, n ), так как qj 0 и v > 0. Как и в рассуждениях для строчного игрока, имеем q1 + q2 + …+ qn =1. Тогда, учитывая обозначения получим Но столбцевой игрок заинтересован в минимизации цены игры v, поэтому в интересах столбцевого игрока мы получаем целевую линейную форму Здесь получается задача линейного программирования: определить такие значения yj (j=1, n ), которые бы удовлетворяли условиям

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

Пусть задана следующая матричная игра:

Для исследования на наличие седловой точки в рассматриваемой игре определяем максимин и минимакс:

Так как max min aij < min max aij, игра не имеет седловых точек и представляет интерес для определения смешанных стратегий. Нижняя цена игры = -2, верхняя цена = 1.

Так как матрица A заданной игры имеет отрицательные элементы, то переходим к эквивалентной игре где число k определяется по правилу Итак, получаем С помощью вычисления максимина и минимакса определяем цену эквивалентной игры vэ [2, 5].

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

Введением неотрицательных балансирующих переменных y4, y5, y приводим задачу к каноническому виду:

Решение задачи (11.6) – (11.8) представлено в таблицах 11.1-11.3.

Таблица 11. А 3 - ведущий столбик, min (1/9, 1/7) = 1/9, 1-я строка разрешающая.

А 2 - ведущий столбик, min (1/9 : 3/9, 1/5) = min (1/3, 1/5) = 1/5, 3-я строка разрешающая.

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

При этих оптимальных значениях переменных max = 11/45.

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

Итоговая таблица 11.3 несет информацию и о значении двойственных переменных, т.е. переменных, оценивающих оптимальное поведение строчного игрока. Значения переменных x1, x2, x3 вычитываются из указанных стрелками 2/15. И на основании уже этих данных определяем оптимальные стратегии строчного игрока:

Итак, определены оптимальные смешанные стратегии для игроков:

И еще рассмотрим маленький пример. Пусть игра задана матрицей Делаем необходимые расчеты для определения максимина и минимакса Так как в рассматриваемой игре максимин и минимакс совпадают, то задача решается в чистых стратегиях. Именно, так как элемент a33 седловой, то строчному игроку следует придерживаться стратегии i* = 3, a столбцевому j* = 3.

Иными словами, оптимальные стратегии для строчного и столбцевого игроков соответственно будут

§ 12. МЕТОД ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

Пусть сам процесс (ситуация) настолько сложен, что нет возможности его оптимизировать известными методами. Тогда по методу динамического программирования СЛОЖНЫЙ процесс (операция, ситуация) разбивается (членится) на ряд этапов (шагов). Эта разбивка во многих случаях является естественной, но в общем случае привносится искусственно. Например, при рассмотрении какойлибо партии игры в шахматы любой ход каждого из игроков как раз и служит разбивке всей партии на отдельные шаги (этапы). А в военной операции по преследованию одной ракеты другой весь непрерывный процесс приходится искусственно разбивать на этапы, например, через каждую секунду наблюдения.

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

Для решения задачи об оптимальном распределении капиталовложений мы будем пользоваться функциональным уравнением Беллмана (американский ученый Ричард Беллман - автор метода динамического программирования).

Сначала с помощью простейшей ситуации проиллюстрируем вывод функционального уравнения Беллмана, а потом на примере докажем, как использовать это уравнение для решения интересующей нас задачи.

Начнем с оптимального распределения выделенных капиталовложений в сумме К между двумя предприятиями. Плановые отделы предприятий на основе своих расчетов сформировали функции дохода q(x) для предприятия П1 и h(x) для предприятия П2. Функции эти означают, что если первое или второе предприятие получит капиталовложение и размере х, то первым предприятием будет получен доход q(x), а вторым h(x), причем величина x может принимать непрерывные или известные дискретные значения от 0 до К.

Итак, пусть предприятию П1 выделены капиталовложения в сумме х, тогда предприятию П2 выделяется сумма К - х. В этом случае от первого предприятия будет получен доход q(x), а от второго - h(К - x). Если капиталовложения К были выделены на один плановый период, то общий доход от двух предприятий составит R(K, x) = q(x) + h(K - x). Очевидно, что x и соответственно К - x надо выбирать такими, чтобы R(K, x) приняло свое максимальное значение, которое мы обозначим через F(K):

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

УСЛОЖНИМ нашу задачу, распределив капиталовложения на два плановых периода (два этапа). Пусть изначально решено первому предприятию П1 выделить сумму х, а второму К – х. В целом доход получался бы равным R(K, x) = q(x) + h(K - x). Если мы будем иметь в виду, что капиталовложения распределяются на 2 периода (2 этапа), то на первом предприятии остаток капиталовложений составит x, где 0 < 1, а на втором - (К - х), где 0 < 1. Соответственно доходы за второй период составят q(x) -по первому предприятию и h[(K - x)] по второму. Оптимизацию по методу динамического программирования, как правило, начинают с концевого этапа. Поэтому начнем со второго этапа, обозначив F1 максимально возможный доход от двух предприятий на втором этапе. Получим Затем к рассмотренному последнему (в нашем случае второму) этапу как бы пристраиваем предшествующий (у нас первый) этап и находим максимальный доход от двух этапов вместе:

Аналогичным образом для n этапов получаем где Fn-1 - целевая функция, дающая наилучший результат за последние (n - 1) этапы. Полученное функциональное уравнение Беллмана носит рекуррентный характер, т.е. связывает значение Fn со значением Fn-1.

В более общем начертании уравнение Беллмана имеет вид где 0 1, Fn-1 - максимальный доход за (n - 1) последних этапов, Fn максимальный доход за все n этапов.

Проиллюстрируем на примере, как, пользуясь функциональным уравнением Беллмана, оптимально распределить капиталовложения К = 200 тыс.грн четырем предприятиям на единый плановый период, если известны функции дохода каждого предприятия q1(x), q2(x), q3(x), q4(x), выраженные в относительных единицах прироста продукции. Здесь под х понимается величина капиталовложения, выделяемого отдельному предприятию.

Пусть исходные данные представлены в табл. I.

Капиталовложе Прирост выпуска продукции (в относительных В конечном счете все наши расчеты сведутся а перебору всевозможных вариантов распределения капиталовложений К = 200 тыс.грн. между четырьмя предприятиями. Так как мы имеем данные лишь по отдельным дискретным значениям выделения капиталовложений (х = 50, 100, 150, 200 тыс.грн.), то количество вариантов конечное и легко просчитываемое. Например, если тыс.грн. распределить поровну по 50 тыс.грн. каждому из предприятий, то получим (как видно из таблицы) общий прирост продукции q1(50) + q2(50) + q3(50) + q4(50) = 25 + 30 + 36 + 28 = 119.

Очевидно, что возможны и другие варианты распределения, обеспечивающие соответствующий прирост продукции. Поиск оптимального варианта распределения капиталовложений организуем с помощью функциональных уравнений Беллмана. Предварительно еще заметим, что если предприятию капиталовложения не выделяются, т.е. х = 0, то прироста продукции нет, т.е. qi(0) = 0 (i = 1, 2, 3, 4).

Методика нашего расчета будет состоять в том, что мы сначала (как бы на первом этапе) рассмотрим наилучший эффект от одного предприятия, затем от двух предприятий вместе, потом - от трех, и наконец - на последнем этапе - от всех четырех предприятий. Начнем рассмотрение с первого предприятия, с его функцией прироста продукции q1(х). Обозначим через F1(с) максимальный прирост продукции на отдельно взятом первом предприятии, если ему выделить капиталовложения с. Будем считать т.к. предполагается монотонный рост прироста продукции в зависимости от выделяемых капиталовложений, т.е. из неравенства с2 > c1 вытекает q1(с2) q1(с1).

Следовательно, для отдельно взятого первого предприятия мы вправе записать Переходим ко второму этапу расчетов. Теперь необходимо определить наилучшее распределение капиталовложений, если они выделяются 1-му и 2-му предприятиям. При этом учитываем наилучший эффект от выделения капиталовложений 1-му предприятию. Обозначим F2(с) наибольший прирост продукции от распределения капиталовложений с между 1-м и 2-м предприятиями. Согласно методике Беллмана запишем Произведем расчеты по этой формуле для возможных выделяемых капиталовложений, т.е. для 50, 100, 150, 200 тыс.грн.:

Поскольку согласно данным таблицы аргумент х может принимать лишь некоторые дискретные значения, то на отрезке изменения переменной х от 0 до 50 возможны лишь 2 значения: 0 и 50, поэтому Под знаком максимума подчеркнут тот член, который приносит максимум F2(50). Это q2(50) + F1(0) в качественном изображении. Он означает, что второму предприятию следует выделить капиталовложения 50 тыс.грн., первому предприятию не выделять капиталовложения. Этот факт мы проиллюстрируем следующей условной диаграммой:

В том случае, если первым двум предприятиям выделяется 50 тыс.грн., то их следует полностью отдать 2-му предприятию. В такой ситуации предполагается, что К - 50 = 200 –50 = 150 тыс.грн. каким-то образом распределены между 3-м и 4-м предприятиями. При подсчете F2(50) мы как бы оцениваем возможную гипотезу о выделении 50 тыс.грн. 1-му и 2-му предприятиям. Аналогичным образом определяем F2 от других значений выделяемых капиталовложений.

Именно Наилучшему эффекту соответствует диаграмма распределения:

При распределении 100 тыс. грн. между 1-м и 2-м предприятиями следует все 100 тыс. грн. выделить второму предприятию. При этом прирост продукции составит 70 относительных единиц.

Видно, что при выделении 150 тыс.грн. 1-му и 2-му предприятиям следует все 150 тыс.грн. отдать 1-му предприятию:

Диаграмма распределения:

Переходим к третьему этапу, когда надо будет определить наилучшие варианты распределения капиталовложений, если они будут выделяться 1-му, 2му и 3-му предприятиям вместе. Рассчитывая наилучший эффект для этого этапа F3(с), мы будем опираться на полученные значения для F2. Именно Конкретные расчеты дадут следующее:

при диаграмме распределения Максимальный эффект приносит член q3(0) + F2(100), который означает, что третьему предприятию капиталовложения выделять не следует, а первым двум надо выделить 100 тыс.грн. Как их распределить между 1-м и 2-м предприятиями, это уже решено ранее, когда мы подсчитывали F2(100) и показывали соответствующую диаграмму распределения. Именно там было решено все тыс.грн. отдать 2-му предприятию. Следовательно, итоговая диаграмма для F3(100) будет такой:

Согласно члену q3(50) + F2(100), принесшему максимальный эффект, следует при распределении 150 тыс.грн. между первыми тремя предприятиями отдать тыс.грн. 3-му предприятию, а 100 тыс.грн. распределить так, как это решено при подсчете F2(100). Там было решено 100 тыс.грн. отдать 2-му предприятию.

Итоговая диаграмма для рассматриваемого случая будет иметь вид:

Максимальный член q3(0) + F2(200) предписывает в случае выделения тыс.грн. первым трем предприятиям третьему предприятию капиталовложений не выделять, а выделять их 1-му и 2-му предприятиям. Но по расчету F2(200) мы можем увидеть, что все 200 тыс.грн. предписывается отдать 1-му предприятию.

Диаграмма распределения согласно расчету F3(200) имеет вид Переходим к последнему, четвертому этапу, когда надо оптимально распределить капиталовложения уже между всеми четырьмя предприятиями.

Необходим расчет F4(с):

На этом этапе нам уже нет смысла рассчитывать F4(50), F4(100), F4(150), а достаточно сразу определить F4(K) = F4(200), т.к. под знаком максимума в формуле для F4(с) уже нет F4, рассчитываемого от долей капиталовложений К.

Итак, Максимальный член q4(150) + F3(50) информирует нас о том, что четвертому предприятию следует выделить 150 тыс.грн., а первым трем вместе - 50 тыс.грн.

Надо взять управленческую информацию после расчета F3(50). Там констатировано, что 50 тыс.грн. следует отдать 3-му предприятию. В итоге получается, что 1-му и 2-му предприятиям капиталовложения выделять невыгодно.

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

§ 13. ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

Пусть задача нелинейного программирования ставится в следующем общем виде: найти такие значения переменных х1, х2,…, хn, которые отвечают условиям:

и приносят требуемый экстремум (максимум или минимум) целевой функции где f(х1, …, хn) и qi(х1, …, хn) ( i = 1, m ) - действительные нелинейные, регулярные функции n действительных переменных.

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

Прежде всего также справедлив графический подход при решении простейших задач нелинейного программирования. Так, если аргументами задачи являются переменные х1 и х2, то сначала на плоскости этих переменных строится область допустимых решений, а затем с помощью уровней целевой функции f(х1, х2) определяется оптимальная точка в области. Например, пусть надо определить такие значения х1 и х2, которые бы отвечали условиям и обеспечивали бы максимум целевой функции На рис. 13.1 представлено полное графическое решение этой задачи.

Прокомментируем это решение. Область допустимых решений выделяется тремя неравенствами (13.3).

В левой части первого неравенства x 12 6x 1 + x 2 4x 2 + 4 0 нетрудно выполнить приведение к полным квадратам. Для этого достаточно учесть, что x 2 4x 2 + 4 = ( x 2 2) 2, а к выражению x 12 6x 1 прибавить и отнять число 9. В результате получаем или или и окончательно Видно, что границей этого неравенства является окружность (x1 - 3)2 + + (x - 2) = 9 с центром в точке (3, 2) и радиусом r = 3. Центр этой окружности обозначим через Q. Путем простейшего контроля, например, с помощью подстановки координат точки Q(3, 2) в первое неравенство (13.3), можно установить, что круг будет допустимой зоной для первого ограничения. Границей второго неравенства x1 2 является вертикальная прямая x1 = 2. Согласно второму неравенству допускается вся полуплоскость от границы (2). Границей третьего неравенства x2 0 является ось х1, причем третье неравенство допускает все точки полуплоскости, лежащей выше оси х1. В итоге все три неравенства в качестве области допустимых решений выделяют часть круга ABCDE.

Для определения оптимальной точки надо на чертеже построить уровни целевой функции, т.е. кривые вида f = const или -х12 + х2 = const = c. Пусть c = 0, тогда линией уровня будет парабола -х12 + х2 = 0 или х2 = х12. На рис. 13. эта парабола помечена отметкой f = 0. При увеличивающейся константе c параболы уровни перемещаются вверх. Поэтому из чертежа видно, что максимум наступает в точке B. Для определения точных координат точки B достаточно решить систему уравнений, составленную из границ (1) и (2), т.е.

Решая эту систему, получаем x1 = 2, x 2 = 8 + 2. Итак, B = (2; 8 + 2).

Подставляя координаты оптимальной точки B в целевую функцию, получаем В нелинейном программировании для решения многих задач используется градиентный подход. Имеется целый ряд градиентных методов, сущность которых состоит в поиске оптимального результата с помощью градиента целевой функции - вектора, указывающего направление максимального возрастания цели для рассматриваемой точки. В общем случае процедура поиска совершается в итеративном режиме от первоначально выбранной точки к точкам с лучшим показателем. Пусть, например, - о6ласть допустимых решений рассматриваемой задачи, а итеративный процесс расчетов начинается с точки А(х1A, х2A,…, хnA), A. Пусть градиент целевой функции f = f(х1, х2,…, хn) И пусть из точки A мы перемещаемся в некоторую точку B c координатами Здесь h - постоянный или переменный параметр, определяющий величину шага перехода.

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

13.3), то критерием оптимальности будет с достаточной степенью достигнутая коллинеарность вектора - градиента целевой функции и вектора - градиента границы, на которой наступает искомый экстремум. Поиск экстремума начат в точке A1.

Далее, сначала делается переход по градиенту целевой функции, а затем возврат в область по градиенту к нарушенной границе О2 О3 области. На рис. 13. показано так, что Ai с нечетными индексами принадлежат области, а точки Аi с четными индексами не принадлежат. По мере приближения к оптимальной точке Q направления рабочих градиентов сближаются. Поэтому идеальным критерием остановки процесса будет коллинеарность градиента цели и градиента нарушенной границы.