vved v lp lekciya


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте файл и откройте на своем компьютере.
1 Тема . Введение в линейное программирование ЛП Цель : научить распознавать основные проблем ные ситуации , кот о рые могут быть формализованы в виде задачи линейног о программир о вания, познакомить с геометрическим методом нахожд ения оптимальн о го решения и ана лизом оптимального решения на чу в ствительность. Задачи :  в вести поняти е задачи линейного программирования ( задачи ЛП;  н аучить формализ овывать проблемы, приводящие к задачам ЛП;  в вести понятия допу стимого и оптимального решений, значения з а дачи ЛП;  н аучит ь находить оптимальное решение задачи ЛП геометрич е ским методом;  д ать представление о б анализе оптимального решения ЛП на чу в ствительность . Оглавление 2.1. Правила построения математической модели. Примеры задач л и нейного программирования. .. Зад а ча лине й ного программирования . .. Геометрическая структура множества допустимых решений задачи линейного программирования. .4. Геометрический метод решения задачи линейного программиров а ния. .5. Анализ оптимального решения на чувствительность. 2.1. Правила п о строения математической модели. Примеры з адач линейного программирования Линейное программирование или сокращенно ЛП Linear Progra m- ming, LP) это раздел более общей теории математического программирования M a thematical Programming, MP). Математическое программирование занимается изучением пр о блем принятия решений, которые могут быть математически сформулированы как задачи нахо ж дения максимума минимума некоторой, вообще говоря, нелинейной функции целевой функции многих переменных , при заданной системе ограничений на о с новные переменные задачи . Формализация проблемы как задачи ЛП подразумевает следующие этапы :  п онять проблему, составить описательную модель задачи;  и дентифицировать основные переменные задачи;  в ыбрать некоторую колич ественную меру эффективности для целевой функции; 2  п редставить эту меру эффективности как линейную функцию относительно основных переменных;  и дентифицировать и представить все огр аничения как линейные уравнения или неравенства относительно основных перемен ных;  с обрать количественные данные или сделать соответствующие оценки для всех параметров модели. Основные математические предположения для задачи ЛП осно в ные огран и чения на применение :  о пределенность детерминирован ность предполагает ся , что все пара метр ы модели известны точно или могут быть оценены ;  л инейность эквивалентна пропорциональности и аддитивности предполагается, что все функциональные соотношения модели линейны относительно основных переме н ных ; o п ропорциональность предполагается, что эффект влияния основной переменной задачи пропорци онален значению этой переменной ; o а ддитивность предполагается, что эффект влияния нескольких основных переменных задачи равен сумме эффектов от каждой переменной ;  д елимость предполагается, что все основ ные переменные задачи могут принимать произвольные вещественные значения в опр е деленном диапазоне бесконечно делимы. Рассмотрим несколько задач, которые можно сформулировать как задачи линейного программирования. Пример . .1. ( Построение оптимального п лана прои з водства ) Кондитерская фабрика производит продукцию двух в и дов: конфеты и шоколад. Для производства продукции каждого вида требуются ресу р сы двух ти пов: сахар и какао - бобы. Для производст ва одной тонны пр о дукции каждого вида требует ся по о д ной т онне сахара . Для производства одной тонны шоколада требуется 5 тонн какао , а для производства о д ной тонны конфет  тонны какао . Суточные запасы ресурсов равны 4 и 0 тонн соответственно. П рибыль от реализации одной тонны шоколада и конфет составляет 5 и 3 тысячи рублей соответственно. Написать м а тематическую модель для нахождения оптимального т. е. максимиз и рующего прибыль суточного плана производства. Основные данные задачи можно представить в виде таблицы: Расход ресурсов на  тон ну готовой пр о дук ции Исходные ресурсы Шоколад Конф е ты Запас ресу р са Сахар 1 1 4 Какао 5 2 10 Прибыль 5 3 3 Определим основные составляющие задачи линейного программ и рования. Переменные: 1 x суточный объем производства шоколада , 2 x суточный объем производства конфет . Целевая функция: общая прибыль от реализации с у точного плана  12 (,) xxx определяется линейной функцией  12 53 zxx . Ограничения: содержательно ограничения на запас ресурсов мо ж но записать следующим образом     Расход Запас ресурсаресурса , используя данные таблицы, получаем линейные огранич е ния  на расход сахара  12 4 xx ;  на расход какао - бобов  12 5210 xx ;  на знак переменных  12 0,0 xx . Окончательно з адача принимает вид:  12 maxmax(53) zxx при выполнении ограничений    12 12 12 4; 5210; 0,0. xx xx xx Пример . .2. ( Формирование смеси минимальной стоимости ) Фармацевтическая фабрика ежедневно производит не менее 800 фунтов пищевой добавки смеси кук урузной и соевой муки, состав кот о рой представлен в таблице в фунтах на фунт муки: Мука Кукуруза Соевая Белок 0,09 0,6 Клетчатка 0,02 0,06 Стоимость в долл. за фунт 0,3 0,9 Диетологи требуют, чтобы в пищевой добавке было не менее 0 % белка и не более 5 % клетчатки. Фирма хочет определить рецептуру см е си м и нимальной стоимости с учетом требований диетологов. Переменные: 1 x количество кукурузной муки, используемой в дневном прои з водстве пищев ой добавки; 4 2 x ко личество соевой муки, используемой в дневном производстве пище вой добавки. Целевая функция: требуется минимизировать общую стоимость произведенной пищевой добавки , которая может быть вычислена с п о мощью линейной функции  12 0,30,9 zxx . Огран ичения:  на количество производимой смеси  12 800 xx ;  на количество белка в пищевой добавке    1212 0,090,60,3 xxxx ;  на количество клетчатки в пищевой добавке    1212 0,020,060,05 xxxx ;  на знак переменных  12 0,0. xx После п ереноса переменных в левую часть ограничений задача примет вид:    12 minmin0,30,9 zxx при ограничениях     12 12 12 12 800; 0,210,30; 0,030,010; 0,0. xx xx xx xx Пример ... Поиск оптимального плана производств а Автомобильная компания производит легковые автомобили и гр у зовики. Каждое транспортное средство должно обрабатываться в покр а сочном и сб о рочном цехах. Если бы в покрасочно м цехе обрабатывались только грузовые а в томобили, то можно было бы покрасить 40 машин в день. Если бы обрабатывались только легковые автомо би ли, то выпус к составил бы 60 единиц продукции . В сборочном цехе обрабатывается 50 транспортных средств в день. Прибыль от производства одного легков о го автомоби ля и грузо вика составляет 00$ и 00$ соответственно. О п ределить оптимальный ежедневный выпу ск продукции, обеспечива ю щий ма к симальную прибыль компании. Переменные: 1 x количество гру зовиков, производимых ежедневно; 2 x количество автомобилей , производимых ежедневно. Ограничения:  на время использования покрасочн ого цеха  12 11 1 4060 xx , где 5 1 40 время в днях, идущ ее на покраску одного грузовика; 1 60 время в днях , идуще е на покраску одного автомобиля;  на время использования сборочного цеха  12 50 xx ;  на знак переменных  12 0,0. xx Целевая функция: Суммарный доход компании определяется функцией  12 300200 zxx . Окончательно имеем задачу    12 maxmax300200 zxx при ограничениях    12 12 12 32120; 50; 0,0. xx xx xx Замечание 2.1.1 . Поскольку переменные задачи характеризуют план выпуска транспортных средств, они могут принимать только цел о численные значения, т.е. свойство делимости в данной задаче не выпо л няется. Однако отмеченная проблема легко преодолима. Например, е с ли в процессе решения задачи получим оптимальный план ежедневного выпуска       ** 12 11 ,2,3 24 xx , то это эквивалентно рекомендации произв о дить 0 грузовиков и  легковых автомобилей за 4 дня. Пример . .4 . ( Определение кредитной полит ики банка ) Банк, предоставляющий полный набор банковских у с луг, находится в процессе формирования портфеля креди тов объемом  млн . дол . В таблице представлены во з можные типы банковских кредитов . Тип кредита Ставка кр е дита Вероятность безнадежных долгов Нецелевые кредиты 0,14 0,1 На покупку автомоб и лей 0,13 0,07 На покупку жилья 0,12 0,03 Сельскохозяйственные 0,125 0,05 Коммерческие 0,1 0,02 Конкурентная борьба с другими финансовыми институтами выну ж дает банк не менее 40 % капитала помещать в сельскохозяй ственные и 6 коммерческие кредиты . Для содействия строительной индустрии банк планирует вложить в кредиты на покупку жилья не менее 50 % от о б щей суммы нецелевых кредитов , кредитов на покупку автомобилей и жилья. Максимально возможная доля без надеж ных долгов в кредитном пор т феле составляет 4 % . Переменные: 1 x сумма нецелевых кредитов ; 2 x сумма кредитов на покупку автомобилей; 3 x сумма кредитов на по купку жилья; 4 x сумма сельскохозяйственных кредитов ; 5 x сумма коммерческих кредитов . Целевая функция: банк максимизирует прибыль, т. е. разность м е жду доходом и ожидаемой суммой невозвращенных кредитов, кот о рую мож но вычислить так :   1234 512345 0,140,90,130,930,120,970,1250,95 0,10,980,10,070,030,050,02. zxxxx xxxxxx Ограничения:  н а общую сумму кредитов  12345 12 xxxxx ;  на сельскохозяйственные и коммерческие кредиты  4512345 0,4() xxxxxxx ;  на покупку жилья    3123 0,5 xxxx ;  на невозвращенные кредиты    12345 12345 0,10,070,030,050,02 0,04 xxxxx xxxxx ;  условия неотрицательности переменных  12345 ,,,,0 xxxxx . После приведения подобных членов в целевой функции и прео б разов а ния ограничений, получаем задачу:  12345 max0,0260,05090,08640,068750,078 zxxxxx при огран и чениях      12345 12345 123 12345 12345 12; 0,40,40,40,60,60; 0,50,50,50; 0,060,030,010,010,020; ,,,,0. xxxxx xxxxx xxx xxxxx xxxxx 7 2.2 . Зада ч а линейного программирования з адача ЛП Математически задача ЛП задача нахождения на и большего наименьшего значения линейной функции многих переменных при л и нейных ограничениях типа равенств н е равенств, когда на переменные задачи есть нет огранич е ний на знак. В общем случае задача линейного программирования может быть записана следующим образом :  задача максимиз а ции   11 maxmax() nn zcxcx (2.2.1) при ограничениях    11 ,1,, 0,1,. iinni j axaxbim xjn (2.2.2)  задача минимизации   11 minmin() nn zcxcx (2.2.3) при ограничениях    11 ,1,, 0,1,. iinni j axaxbim xjn (2.2.4) Здесь  ,1, j xjn переменные мод е ли,   11 nn zcxcx целевая функция,   11 iinni axaxb ограничение с номером i ,  1, im ,  0 j x условие неотрицательности переменной j ,  1, jn ,  ,, jiji сab заданные параметры ,  1, im ,  1, jn . Вектор   1 (,,) n Xxx , удовлетворяющий ог раничениям зад ачи , н а зывается допустимым решением задачи ЛП . Допустимым множеством решений задачи ЛП называется множ е ство векторов   1 (,,) n Xxx , удовлетворяющих всем ограничениям з а дачи. Вектор    1 (,,) n Xxx , доставляющий максимум минимум фун к ции z при заданных ограничениях, называется оптимальным решением з а дачи ЛП. Соответственно, наибольшее     * zzX наименьшее     * zzX  значение целевой функции называется значением з а дачи ЛП. Решить задачу ЛП означает найти оптим альное р е шение    1 (,,) n Xxx и соответствующее знач е ние целевой функции   * zx , т. е. значение задачи ЛП. 8 2.3 . Геометрическая структура множества допустимых решений в з а даче линейного программирования Приведем некоторые понятия из теории выпуклых множеств и сформулируем теорему о геометрической структуре множества допуст и мых реше ний в задаче ЛП . Напомним, что элементы пространства n R называются как точками, так и векторами. Множество  n MR называется выпуклым , если для двух любых т о чек  12 , XXM и любого     0,1 выполняется условие :     12 1 XXM . Другими словами, множество называется выпуклым , если с люб ы ми двумя точками из этого множ ества ему прина д лежит и весь отрезок, соед и няющий эти точки. Пусть  n MR выпуклое множество. Точка  0 XM называется крайней экстремальной точкой множества M , если из условия     012 1 XXX ,  12 , XXM ,     0,1 следует, что  012 XXX . Выпуклой линейной комбинацией точек   1 ,, rn XXR называется точка, которую можно представить в виде:     11 ;0;1,;1 rr i iii ii XXir . Выпуклым многогранником M , порожденным точками   1 ,, rn XXR , называется множество все возможных выпуклых лине й ных комбинаций точек  1 ,, r XX :        11 ;0;1,;1 rr ni iii ii MXRXXir . Конечным конусом K , порожденным векторами   1 ,, rn AAR , наз ы вается множество всех векторов  n XR , удовлетворяющих условию :     11 ;0;1,;1 rr i iii ii XAir . Рассмотрим систему нестрогих линейных неравенств (2.2.2) или ..4 . Каждое линейное ограничение типа неравенства задает в n R о т рицательное положительное полупространс т во       11 iiinni Xaxaxb (       11 iiinni Xaxaxb ) , ограниче н ное гиперплоскость ю      11 iiinni Xaxaxb . 9 Множество векторов , удовлетворяющих системе (2.2.2) или (2.2.4) , можно представить как пересечение  mn полупр о странств :       1 mn i i M (       1 mn i i M ) . Такое м ножество M назы вается многогранным множес т вом. Теорема .. ( о геометрической структуре множества допу с тимых решений в задаче ЛП ) . М ножество M допустимых решений задачи линейного программ и рования можно представить в виде:  0 MMK , где 0 M выпуклый мно гогранник , порожденный крайними точками мн о жества M ; K конечный конус. 2.4 . Геометрический метод решения задачи ЛП Геометрический г рафический ) метод применим тол ь ко для задач малой р азмерности количество переменных в задаче равно  или , п о скольку он основан на геометрическом построении множества допуст и мых решений в задаче ЛП. Рассмотрим геометрический метод решения задачи ЛП на нескол ь ких примерах. Пример .4. . Решим графически задачу из примера ..:     12 12 12 12 maxmax53, 4; 5210; 0,0. zxx xx xx xx       1 2 3 Геометрический метод реализуется в два этапа:  построение допустимого множества решений задачи ЛП;  нахождение оптимального решения среди всех допу с тимых. Первому ограничению задачи соответствует прямая  12 4 xx , об о зна ченная на рис. .4. значком   1 . Точки пересечения этой прямой с осями координат:     4,0,0,4 . П рямая  12 5210 xx , соответствующая второму ограничению, пересекается с осями координат в точках     2,0,0,5 . Аналогичным образом учитываем ограничения   3 на знак переменных. Множество допустимых решений данно й задачи изображ е но на рис. .4. в виде заштрихованного чет ы рехугольника. 10 Рис. .4. Нахождение оптимального решения требует определения напра в ления наискорейшего роста целевой функции z . Та кое направление з а дается градиентом целевой функции :         12 12 grad,, zz zxx xx . Так как  12 53 zxx , то направление наискорейшего роста функции z определяется вектором     5,3 c . Вектор     5,3 c также является ве к тором нормали к линии уровня целевой функции  12 53const zxx . Точка пересечения области допустимых решений и прямой, соо т ветствующей максимальному значению целевой функции, и будет реш е нием задачи ЛП. На р ис. .4. видно, что это точка является точкой пересечения прямых  и . Ее координаты можно найти как решение си с темы уравнений, з а дающих эти прямые:         *** 121 *** 122 423 5210103 xxx xxx . Таким образом ,   (2/3,10/3) X оптимальное решение;    * 523310/340/3 zX максимальное зна чение целевой функции. Пример .4.. Решим геометрически задачу из прим е ра .. :    12 minmin0,30,9 zxx при ограничениях 11     12 12 12 12 800; 0,210,30; 0,030,010; 0,0. xx xx xx xx       1 2 3 Постоим множество допустимых решений как пересечение пол у плоск о стей, соответствующих трем ограничениям задачи. Заметим, что получившееся множество неогранич е но рис..4. . Рис. .4. Поскольку в данной задаче требуется найти минимум целевой функции  12 0,30,9 zxx , нас будет интересовать точка пересечения множеств а допустимых решений с линией уровня целевой функции , с о ответствующей минимально возможному значению z . Такой точкой я в ляется точка пересечения прямых   1 и   2 . Чтобы найти координаты о п тимальной точки * X , решим систему уравн е ний:        ** 12 ** 12 800, 0,210,30 xx xx         * 1 * 2 470,6 329,4 x x . При данных значениях переменных минимальная сто имость пищ е вой добавки составляет    *** 12 0,30,9437,64 zXxx . Пример .4.. Решим геометрически задачу из примера ...    12 maxmax300200 zxx при ограничениях 12    12 12 12 32120; 50; 0,0. xx xx xx       1 2 3 Множество допуст имых решений задачи приведено на рис. .4. и представляет собой заштрихованный четырехугольник. Поскольку вектор коэффициентов целевой функции     300,200 c задает то же направл е ние, что и вектор коэффициентов первого ограничения   3,2 , любая то ч ка отрезка AB является оптимальной. В качестве оптимального р е шения можно взять либо точку   20,30 A , либо точку   40,0 B , либо л ю бую точку на отрезке AB . Максимальную прибыль компании можно найти так :      * 300*401200 zXzB . Рис. 2.4.3 Пример .4.4. Добавим в предыдущую задачу еще два огранич е ния  12 30,20 xx , тогда задача будет иметь вид    12 maxmax300200 zxx при огр аничениях      12 12 1 2 12 32120; 50; 30; 20; 0,0. xx xx x x xx           1 2 3 4 5 13 Как видно из рис. .4.4 множество допустимых решений пусто, п о этому задача не имеет и оптимального решения. Рис. .4.4 Пример .4.5 . Решить задачу    12 maxmax2 zxx при ограничениях    12 12 12 1; 26; 0,0. xx xx xx       1 2 3 Множество допустимых решений этой задачи неограничен о рис. 2.4.5 ) . Г радиент целевой функции :     2,1 c . При движении линии уровня в направлении гра дие нта целевая функция неограничен н о во з растает, как следствие, задача не имеет оптимального решения. Отм е тим, что ограничение  1 0 x в данной задаче ЛП является избыточным. Рис. .4.5 14 Далее сформулируем общий алгоритм геометрическог о  графич е ского ) метод а нахождения оптимального решения задачи ЛП. Экстремальной точкой в задаче ЛП будем называть крайнюю у г ловую точку множества допустимых решений. Теорема .4. . об оптимальных экстремальных точках . Е сли в задаче ЛП существует оптим альное решение, то сущ е ствует и оптимальная экстремаль ная точка. А л горитм графического мето да решения задач ЛП с двумя п е ременными :  з аписать каждое ограничение задачи ЛП как равенство уравнение и нарисовать соответствующую прямую в координатной плоско сти ;  д ля каждого ограничения неравенства определить нарисовать допустимую область, а затем допустимую область для всех ограниче ний о н а представляет собой пересечение таких областей для всех ограничений ) . Полученная область представляет собой множество допустимых решений задачи ЛП;  записать уравнение линии уровня целев ой функци и:    12 ,const zxx ;  найти градиент целевой функции         12 12 grad ,, zz zxx xx , который показывает напра в ление наискорейшего роста функции z . Сдвигать линию уровня целевой функции в на правлении градиента в случае н а хожд е ния максимума или в направлении , противоположном градиенту в сл у чае нахождения минимума ;  экстремальная угловая точка, которая лежит на пересечении п о следней» линии уро в ня целевой функции и множества допустимых решений , и будет оптимальным решением задачи ЛП ;  чтобы аналитически найти координаты оптимальной точки, соста в ляем систему уравнений из ограничений, соответствующих прямым, пр о ходящим через эту точку. Вычислить зн ачение целевой функции в оптимальной точке значение задачи ЛП. При решении задачи ЛП возможны следующие случаи: 1. Задача ЛП имеет единствен ное решение см. примеры .4. и 2.4.2). 2. Задача ЛП имеет бесконечное множество решений пример 2.4.3) , это возможно , если линия уровня целевой функции параллельна прямой, соответствующей одному из ограничений зад а чи. 3. Задача ЛП не имеет оптимального решения, это является либо следствием неогр а ниченности множест ва допустимых решений пример 2.4.5 , либо следствием его п устоты пример .4.4 . 15 2 . 5 . Ана лиз оптимального решения на чувствительность Модель линейного программирования является как бы моментальным снимком» реальной ситуации, когда параметры модели предполагаются неизменными. Естественно изучить влияние измене ния параметров модели на получ енное оптимальное решение задачи ЛП. Такое исследование оптимального решения называется анализом на чувствительность. Пример 2.5 .1. Проведем анализ на чувствительность оптимальн о го р ешения, найденного в примере .4 .1. Напомн им, что оптимальное решение рассматриваемой задачи вектор   (2/3,10/3) X и   40/3. z Первая задача анализа на чувствительность чувствительность к правой части ограни чений. В рамках этой задачи ограничения классифицируются как:  свя зывающие активные, если соответствующие им прямые пр оходят через оптимальную точку ;  несвязывающие неактивные, если соответствующие им прямые не п роходят через оптимальную точку . Связывающим активным ограничениям отвечают дефицитные ресурсы, т. е. рес урсы, используемые полностью. Несвязывающим неа к тивным ограничениям отвечают н е дефицитные ресурсы. Цели первой задачи на чувствительность:  о пределить предельно допустимое увеличение запаса дефицитн о го ресурса, позволяющее улучшить найденное значение це левой фун к ции;  о пределить предельно допустимое снижение запаса недефицитн о го ресурса, не изменяющее найденного оптимального р е шения. Ресурс 1 дефицитный, ограничение  связывающее акти в ное; Ресурс  дефицитный, ограничение  связывающее акт и в ное. Рис. .5. 16 Для ресурса  предельно допустимое увеличение запаса соста в ляет  единицу с 4 до 5 единиц , т. к. прямую  имеет смысл двига ть параллельно себе до точки 0 , 5 , ей будет отв е чать уравнение    1 :  12 5 xx . М аксимальная при быль будет в точке с координатами 5,0, z (0 , 5 ) =15 и увели чится на  1540353 рис. .5.. При увеличении запаса второго дефицитного ресурса, прямую  следует двигать до точки 4,0, такому полож е нию прямой соответствует уравнение  12 5220 xx , и изм е нение запаса второго ресурса равно 0. Максимальная прибыл ь z 4,00, изменение прибыли при изменении запаса второго ресурса равно  20403203 рис. .5. ) . Рис. .5. Результаты решения первой задачи анализа на чувствительность оформляются в виде та б лицы: Ресурс Тип статус ресурса Максимальное изменение з а паса Максимальное и з менение д о хода Ресурс дефицитный  541  1540353 Ресурс дефицитный  201010  20403203 Вторая задача анализа на чувствительность позволяет опред е лить меру зависимости оптимального решения от изменения огранич е ний, накладываемых на ресурсы. Эта мера называется теневой дво й ствен ной ценой ресурса и показывает , на сколько изменится оптимал ь ное значение целевой функции при изменении количества ресурса на един и цу. Т еневая двойственная цена ресурса i обозначается i y и вычи с ляется по формуле: 17  Максимальное увеличение дохода Максимальное увеличение запаса го ресур са i y i . Для рассматриваемой задачи  1 15-4035 13 y ,  2 20-4032 203 y . Заметим, что для недефиц итных ресурсов теневая цена всегда равна нулю. Можно сделать вывод, что наиболее выгод но уве личение первого ресу р са, т. к. прибыль на единицу этого ресурса больше. Третья задача анализа на чувствительность состоит в опред е лении пределов изменения коэффициентов целевой функции, позв о ляющих сохранить оптимальное решение з а дачи. Пусть  1122 zcxcx целевая функция,  1111221 axaxb и  2112222 axaxb два активных ограничения в оптимальной точке * X . рис. .5. . При изменении коэффициентов целевой функции решение остается опт имальным, если соотношение коэффициентов 1 2 c c удовл е творяет н е равенству  11121 12222 aca aca диапазон оптимальности. В рассматриваемом примере решение   (2/3,10/3), X остается оптимальным, если  1 2 15 12 c c . Рис. .5. В частности , если  1 const5 c ,  2 155 12 c ,  2 25 c ; 18 если  2 const3 c ,  1 15 132 c ,  1 15 3 2 c . Выводы  Многие проблемные ситуации мог ут быть сформулированы как з а дачи ЛП , если они удовлетворяют следующим математическим предп о лож е ниям : определенности, линейности, делимости .  Структурными с оставляющими задачи ЛП являются: переменные, целе вая функция, ограничения и ограничения на знак пер е м енных.  Оптимальное решение для задач малой размерности может быть получено с помощью геометрического м е тода .  Геометрически оптимальное решение задачи ЛП находится на гр а нице множества допустимых решений.  Задача ЛП может иметь одно оптимальное решение, беск онечно е множество оптимальных решений или не иметь оптимальных р е шений.  Анализ на чувствительность выявляет зависимость оптимального решения от возможных изменений параметров исходной м о дели. Вопросы для самопроверки 1. Назовите основные предположения, кот орым должна удовлетв о рять модель ЛП. 2. Назовите основные этапы формализации задачи ЛП. 3. Сформулируйте проблему, которую можно формализовать как з а дачу ЛП. 4. Дайте определение задачи ЛП. 5. Дайте определение допустимого решения задачи ЛП и допуст и мого множества реш ений задачи ЛП. 6. Что понимают под оптимальным решением задачи ЛП? 7. Дайте определение выпуклого множества. 8. Что такое крайняя экстремальная точка множества? 9. Какую структуру имеет множество допустимых решений задачи ЛП? 10. Сформулируйте алгоритм геометрического метода решения зад а чи ЛП. 11. В чем отличие решения задачи ЛП максимизации от задачи ЛП миним и зации при геометрическом методе? 12. Сколько решений может име т ь задача ЛП? 13. В чем сущность анализа оптимального решения на чувствител ь ность? 14. Дайте определение активного связывающего ограничения. 15. Что такое дефицитный ресурс? 16. Что понимают под теневой двойственной ценой ресурса? 17. Чему равна теневая цена недефицитного ресурса? 19 18. Можно ли улучшить значение целевой функции, изменяя запас недефицитного ресурса? 19. Всегда ли измен ение коэффициентов целевой функции приводит к изменению оптимального решения задачи ЛП? Библиография 1. Таха Х.А. Введение в исследование операций. 7 - е изд . М.: Изд . дом Вильям с», 005. 2. Ху Т. Целочисленное программирование и потоки в сетях.М.: Мир, 1972. 3. Зайченко Ю.П. Исследование операций.  - из д . К иев: Изд - во В и ща школа», 979. 4. Красс М.С. , Чупр ынов Б.П . Основы математи ки и ее приложения в экономическом образован ии. М.: Дело, 00. 5. Зенкевич Н.А. , Марченко И.В . Экономико - математические методы. Рабочая те традь №. СПб .: изд - во МБИ, 005. 6. Хазанова Л.Э. Математическое моделирование в экономике. М.: Изд - во БЕК, 1998. 7. Cook Т . & Russel R.A. Introduction to Management Science. Engl e- wood Cliffs (New Jersey), Prentice Hall, Inc. 1989. 8. Winston W.L. Introduction to Mathematical Programming: Applications and Algorithms. Boston (Mass.) : PWS - KENT Publ., 1991 . 9. Winston W.L. Operations Researc h: Applications and Algorithms . Bo s- ton (Mass.) : PWS - KENT Publ., 1990.

Приложенные файлы

  • pdf 18814076
    Размер файла: 244 kB Загрузок: 0

Добавить комментарий