Данциг Дж. Линейное программирование, его обобщение и применение. -М. Прогресс, 1966. - 600 с. [c.217]
Данциг Дж. Линейное программирование, его при- [c.266]
Эффективный метод перебора угловых точек области допустимых решений с целью нахождения оптимального решения ЛП-задачи. Предложен Дж. Данцигом в 1947 г. Метод (или его последующие модификации) лежит в основе всех компьютерных алгоритмов для решения ЛП-задач. [c.296]
См. также Данцига — Вульфа метод декомпозиции, Декомпозиционные методы. [c.10]
Иначе говоря, схема Данцига— Вульфа построена по принципу "централизованное определение цен—децентрализованное определение наилучших возможностей", а схема Корнай—Лип-така — по принципу "централизованное лимитирование возможностей — децентрализованное выявление эффекта от их использования"7. В обоих случаях важную роль играют двойственные оценки, причем их оптимальный уровень выявляется вместе с оптимальный распределением ресурсов, т. е. собственно планом (именно в этом состоит принцип оптимального планирования). [c.34]
Данцига—Вульфа метод декомпозиции [c.70]
См., разработанный Дж. Данцигом, послужил исходным пунктом для разработки целого семейства алгоритмов решения как линейных, так и нелинейных выпуклых задач оптимизации. [c.322]
Данцига - Вульфа метод декомпозиции 70 [c.463]
Симплекс-метод. Это один из первых специализированных методов оптимизации, нацеленный на решение задач линейного программирования, в то время как методы простого и направленного перебора могут быть применены для решения практически любой задачи оптимизации. Он был предложен американцем Г.Данцигом в 1951 г. Симплекс-метод состоит в продвижении по выпуклому многограннику ограничений от вершины к вершине, при котором на каждом шаге значение целевой функции улучшается до тех пор, пока не будет достигнут оптимум. [c.170]
Третий метод решения задачи основывается на принципе декомпозиции /см. гл.22 книги Данцига/. Пока что отсутствует опыт планирования программы с переменными коэффициентами этим методом. [c.47]
Метод Данцига—Вольфа ограничен задачей управления портфелем Марковица. Поскольку существует много различных обстоятельств, при которых возникают задачи квадратического программирования, то, нужны более общие подходы. Действительно, портфельные задачи Марковица сейчас чаще решаются именно подобными пакетами. [c.456]
При такой постановке задачи оптимизации плана производства НПЗ модель (2)— (9) является нелинейной. Аналогичные постановки имели место в работах [2, 3, 4,. Б]. Пути решения указанных задач в основном связываются с различными методами линеаризации, предложенными в работе Дж, Данцига 16]. Подробное обоснование этих методов в отношении моделей оптимизации плана производства НПЗ рассматривается в работах [3, 4]. Недостатками методов линеаризации является, во-первых, значительное увеличение размерности моделей, а во-вторых, усложнение подготов-.ки исходной информации для решения. [c.98]
Становление современного математического аппарата оптимальных экономических решений началось в 40-е годы, благодаря первым работам Н. Винера, Р. Беллмана, С. Джонсона, Л. Канторовича. Задача линейного программирования впервые математически сформулирована Л. В. Канторовичем в 1939 г. на примере задачи раскроя материалов для Ленинградского фанерного треста. В 1947 г. Дж. Данциг предложил универсальный алгоритм решения задач линейного программирования, названный им симплекс-методом. В 1941 г. Хичкок и независимо от него в 1947 г. Купсман формулируют транспортную задачу, в 1945 г. Стиглер — задачу о диете. В 1952 г. было проведено первое успешное решение задачи линейного программирования на ЭВМ Sea в Национальном бюро стандартов США. [c.102]
Процедура построения выпуклого многогранника, аппроксимирующего области производственных возможностей, имеет определенное структурное xofl TBO j MeiofloM разложения Данцига - Вульфа [16]. Пусть имеется k (k = l,L) предприятий, производственные возможности которых описываются линейной моделью блочной структуры следующего вида k k k [c.24]
В отличие от метода Данцига — Вульфа, в котором производственные возможности отдельных предприятий представляются в виде линейной комбинации всех базисных решений х (s= , М ), в аппроксимаци-онных моделях выпуклые многогранники ооычно задаются на базе ограниченного множества опорных плановых решений. Ограниченность числа рассматриваемых в аппроксимационных моделях вариантов позволяет сократить размерность задач и объем обрабатываемой информации. [c.25]
Антверпен, Кёльн, Франкфурт, Майнц, Нюрнберг, Хохенкирхен, Лейпциг, Аугсбург, Хал, Инсбрук, Данциг, Бреслау, Краков, Вена, Будапешт, Больца-но, Милан, Венеция, Рим, Неаполь, Мадрид, Севилья, Лиссабон. [c.25]
Для решения подобных задач имеется ряд алгоритмов, которые строятся на основе принципа декомпозиции. Наиболее широко известны декомпозиционные алгоритмы, предложенные Данцигом и Вольфом [26], Корнай и Липтаком [61]. В терминах задачи распределения производственной программы отрасли с использованием моделей, решаемых методами линейного программирования, идея алгоритма Данцига-Вольфа следующая. Центральный орган управления отраслью устанавливает цены (двойственные оценки) на продукцию. Исходя из максимизации прибыли при этих ценах, каждое предприятие разрабатывает свою производственную программу. Центральный орган обобщает планы предприятий и сравнивает их с потребностями народного хозяйства в разных видах продукции отрасли. Затем производится корректировка цен если предложенный выпуск продукции данного вида меньше потребности, то цена на нее повышается если выпуск превышает потребность, то цена понижается. Новые цены сообщаются предприятиям для проведения следующей итерации и т. д. [c.189]
Данциг Дж., Вулф П. Алгоритм разложения для задач линейного програм- [c.263]
Первый такой алгоритм, называемый симплекс-методом, был предложен американским математиком Джорджем Данцигом в 1947 г. С тех пор появились различные модификации этого алгоритма, ускоряющие сходимость алгоритма к оптимальному решению. Кстати, симплекс (лат. simplex) означает замкнутую область в многомерном пространстве (область допустимых планов). [c.61]
Среди теоретических схем Б.п. наиболее известны две метод декомпозиции Данцига—Вульфа и метод планирования на двух уровнях Корнай—Липта-ка (Дж. Данциг и П. Вульф — американ- [c.33]
Данциг (Dantzig) Джордж Бернар (р. 1914), американский математик. Учился в Мэ-рилендском, Мичиганском и Калифорнийском университетах. Работал в бюро статистики труда, в военно-воздушных силах, РЭНД корпорейшн. Возглавлял кафедру исследования операций в Калифорнийском университете (г. Беркли) и в [c.436]
Глава 5 посвящена методам многоуровневой оптимизации, рассматриваются методы Данцига—Вулфа, Корнай—Липтака и Пугачева на примере оптимизации производственной программы группы предприятий (объединения). [c.4]
Метод разложения Данцига—Вулфа [c.179]
Метод разложения (декомпозиции) был разработан для решения задач линейного программирования большой размерности, имеющих блочную структуру. Его вычислительная процедура главным образом основана на идеях модифицированного симплекс-метода. Однако значение метода Данцига—Вулфа состоит не только и (не столько) в его вычислительных преимуществах, сколько в возможности дать содержательную экономическую интерпретацию. Метод предусматривает разложение исходной задачи (5.6)—(5.9) на локальные задачи, соответствующие обособленным частям объединения (в данном случае предприятиям), и главную задачу (соответствует объединению в целом и связывает эти локальные задачи). [c.179]
Как известно, на каждом шаге процесса решения в любом из методов линейного программирования выполняют следующие операции а) получают решение б) проверяют полученный план на оптимальность в) в случае неоптимальности выявляют тот вектор, который нужно ввести в базис (опорный план) улучшенного плана. В методе Данцига—Вулфа этот процесс распределяется между главной задачей, с одной стороны, и локальными задачами — с другой. [c.179]
Рассматривая метод Данцига— Вулфа, видим, что план системы в целом последовательно улучшается путем взаимного уточнения планов отдельных предприятий. [c.188]
Прибыль объединения равна 64 руб. Нетрудно убедиться, что при решении задачи и методом Данцига—Вулфа, и методом Корнай—Липтака оптимальные планы совпадают. [c.194]
Оптимальный план задачи объединения х,=3 шт. л 2=0 шт. х3=6 шт. х4=0 шт. f=66 руб. Напомним, что это решение приближенное, так как производственные возможности предприятий аппроксимировались гиперплоскостями AG и HQ с некоторым завышением (см. рис. 5.1 и 5.2). На самом деле области EDGvi NMQ соответствуют недопустимым планам. Поскольку истинный оптимальный план объединения с,=3,25 шт. х2=0 шт. х3=5 шт. х4=0 шт. F=66 руб. (см. точное решение методом Данцига—Вулфа) дает прибыль, равную 64, то полученный план, видимо, не уложится в ресурсы. Действительно, на втором предприятии первый собственный ресурс имеется в количестве 10 т, а по полученному плану его потребуется 12т. [c.201]
Сформулируйте метод разложения Данцига—Вулфа. Каким образом связаны главная и локальные задачи [c.205]
Коротко об истории вопроса. В I9GO-6I гг. в ИАТ /ныне Институт проблем управления/ была сформулирована постановка задачи оптимизации химико-технологического комплекса при варьируемых нормативных показателях /относительных выходах/. В 1963 г. Дж.Данциг указал метод линеаризации модели с переменными коэффициентами путем разложения коэффициентов по вершинам их области опр- Д. ./.ения. В 1963-65 гг. для оптимизации химико-технологического комплекса в ИАТ использовался метод линеаризации, тесно связанный с методом Данцига. В середине 60-х гг. некоторые авторы применя- [c.4]
Дж.Данциг. Линейное программврованяе, его применение и обобщения. Изд-во "Прогресс", 1966. [c.48]
Первые работы по стохастическому программированию появились в 1955 г. В них содержатся постановки линейных двухэтапных задач и подходы к вычислению распределения оптимального значения целевой функции задачи линейного программирования со случайными параметрами условий (так называемый пассивный подход к задачам стохастического программирования). Модели двухэтапных задач предложены одновременно и, по-видимому, независимо друг от друга Е. Билом i[30], и Дж. Данцигом [89]. Анализ двухэтапных постановок был затем развит А. Маданским [191—193], Р. Ветсом [60—62], П. Каллем [140, 142] и др. В настоящее время двухэтапным задачам посвящена достаточно обширная литература (см., например, [14—16, 71, 58, 94, 160, 176, 199, 253, 176, 284, 320, 49, 361]). [c.17]
Первой попыткой перехода от статических моделей стохастического программирования к динамическим была, по-видимому, двухэтапная задача Данцига — Маданского. Двухэтапная задача может быть обобщена в различных направлениях. Естественно, например, перейти к многоэтапной задаче с жесткими ограничениями (с ограничениями, которые должны выполняться при всех возможных реализациях случая, подобно тому, как это предполагается в классической двухэтапной задаче). Такого рода подходы рассматривались Беллманом [10], Дж. Данцигом [88], Н. 3. Шором и др. [332, 334—336]. Здесь мы, однако, рассмотрим более широкие обобщения двухэтапной задачи — различные постановки многоэтапных стохастических задач с безусловными и условными статистическими, вероятностными и жесткими ограничениями. Частные модели подобного типа обсуждались в [70, 308—310] и других работах. Многоэтапные модели стохастического программирования имеют многочисленные приложения к задачам планирования в экономике и технике. Ряд практических проблем, возникающих при перспективном планировании, при многостадийном проектировании, при управлении боевыми операциями, при планировании экспериментов и оперативном управлении космическими объектами, при регулировании технологических процессов, подверженных случайным возмущениям, может быть рассмотрен как многоэтапные стохастические задачи со статистическими вероятностными и жесткими ограничениями. [c.192]
Данциг Дж. Б. Линейное программирование. Его применения и обобщения,. М., Прогресс , Т966, гл. 25, 3. [c.384]
Условия Кюиа—Такера Метод Данцига—Вольфа Краткий обзор методов восхождения на холмы [c.425]
Задачи линейного программирования для двух переменных могут быть решены с помощью построения графиков. В 1940-х годах Данциг разработал алгоритм, называемый симплексным алгоритмом, эффективно преобразующий графический подход в алгебраический метод, который может быть использован для компьютерного приложения и позволяет обрабатывать любое число переменных. Симплексный алгоритм — это итерационный процесс нахождения оптимального значения (экстремума) целевой функции. [c.428]