назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [ 82 ] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]


82

Этап 4. Проверяют полученные на этапе 3 точки на экстремум и определяют экстремальное значение функции/найденной точки.

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

Пример (расчет экономико-математической модели при нелинейных затратах на производство). Фирма реализует автомобили двумя способами: через магазин и через торговых агентов. При реализации автомобилей через магазин расходы на реализацию составляют Ах\ + усл. ед., а при продаже Х2 автомобилей через торговых агентов расходы составляют

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

Решение. Составим математическую модель задачи. Целью является

минимизация суммарных расходов Л = 4xi + xi + х.

Управляющие переменные- это число автомобилей, реализуемых первым и вторым способом: Х и Х2, соответственно (200 шт.).

Окончательно математическая модель имеет следующий вид:

7? = 4x1 + 1 + 2 Xl + Х2 = 200,

Х2 >0.

Для ее расчета применим метод множителей Лагранжа. Функция Лагранжа имеет вид

F(xi,X2,A) = 4xi +xf +Х2 +Я(200-Х1 -Х2).

Найдем частные производные функции F по х, Х2 и Я и приравняем их к нулю.

Получим следующую систему уравнений:

Г5F/axl=2xl + 4-Я=0, - 5/ас2=2х2-Я = 0, 5F/5Я = 200-XI-Х2 = 0.

Решая систему, найдем = 99, Х2 = 101, Я = 202, /(x,X2) = 20 398.



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

9.6. Условия Куна - Таккера

Условия Куна - Таккера

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

Важное место в теории выпуклого программирования занимают условия Куна-Таккера, названные так в честь открывших их американских математиков Куна и Таккера.

Пусть требуется решить задачу нелинейного программирования следующего вида:

/(xi,...,x„)max(min)

gl (xi,...,x„)<Z?i, g2 (xi,...,x„)<Z>2,

(9.6)

Tot факт, что ограничения задачи содержат только ограничения в виде неравенств «меньше или равно», никак не ограничивает общность задачи, поскольку каждое неравенство вида «больше или равно» приводится к требуемому виду умножением левой и правой частей на -1. Каждое равенство может быть представлено в виде двух неравенств противоположного знака, а далее неравенство вида «больше или равно» приведено к неравенству вида «меньше или равно» описанным способом.

Далее будем предполагать, что функции Дх), / = 1, w, удовлетворяют так называемым условиям регулярности. Не давая точных математических понятий этим условиям, приведем лишь два достаточных условия их выполнения: 1) все функции g/(x), / = 1, w, являются линейными; 2) существует точка х, такая, что выполняются соотношения gx) < fe-, / = 1,/W (условие Слейтера).

Теорема. Пусть задача (9.6) есть задача максимизации; функции f(x),g/(x) дифференцируемы на допустимом множестве. Функции g/(x),



/ = 1, w выпуклые и удовлетворяют условиям регулярности. Если точка X* =(х*,...,х*) является оптимальным решением задачи (9.6), то существуют значения Я*,...,Я такие, что выполняются соотношения

(9.7)

Xi>0, i = \,m.

Для задачи минимизации аналогичная теорема имеет следующий вид. Теорема. Пусть задача (9.6) есть задача минимизации, функции Дх), Дх) дифференцируемы на допустимом множестве. Функции g/(x),

/ = 1, w выпуклые и удовлетворяют условиям регулярности. Если

точка X* =(xi*,...,x*) является оптимальным решением задачи (9.6), то

существуют значения Я*,...,Я такие, что выполняются соотношения

(9.8)

X,/ >0, i-\,m.

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

Теорема. Пусть задача (9.6) есть задача максимизации, функции f(x), Дх) дифференцируемы на допустимом множестве. Функции g/(x), / = 1, w выпуклые и удовлетворяют условиям регулярности. Функция Дх) является вогнутой. Тогда точка х* = (х*,...,х*) является оптимальным решением задачи (9.6) тогда и только тогда, когда существуют значения Я*,...,Я такие, что выполняются соотношения (9.7).

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [ 82 ] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]