Записать систему в канонической форме. Различные формы записи ЗЛП (общая, каноническая, симметрическая). Виды задач линейного программирования

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

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

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

Описание алгоритма венгерского метода  

После конечного числа построений очередной первый этап обязательно закончится переходом на второй этап и количество независимых нулей увеличится на единицу, т. е. (к + 1)-я итерация будет завершена. Обоснование отдельных этапов алгоритма венгерского метода для задачи выбора приведено в .  

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

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

Известны различные способы решения этой задачи - распределительный, венгерский, метод потенциалов и др. Как правило, для расчетов применяется ЭВМ.  

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

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

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

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

Корнай (Kornai) Янош (р. 1928), венгерский экономист-математик, академик АН Венгерской республики. Окончил Будапештский университет (1955), работал в АН, Институте текстильной промышленности , вычислительном центре Академии наук с 1967 г. - профессор и руководитель отдела АН Венгрии, с 1986 г. - профессор экономики в Гарвардском университете. В конце 50-х гг. вместе с Т. Липтаком разработал метод решения задач блочного программирования - метод планирования на двух уровнях (см. Корнай-Липтака метод). Исследовал проблемы функционирования экономики в условиях неравновесия, взаимоотношения между дефицитом и инфляцией. Был одним из идеологов венгерской экономической реформы конца 60-х гг. Иностранный член Британской, Шведской, Финляндской академий наук , почетный член Американской академии искусств и наук, Американской экономической ассоциации почетный доктор университетов многих стран мира . Государственная премия ВНР - 1983 г.  

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

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

Предварительный этап .

Шаг 1 . При максимизации целевой функции С найти максимальный элемент и каждый элемент этого столбца вычесть из максимального. При минимизации целевой функции (суммы показателей эффективности назначений) в каждом столбце матрицы С найти минимальный элемент и вычесть его из каждого элемента этого столбца.

С  с неотрицательными элементами. В каждом столбце матрицы С  имеется, по крайней мере, один нуль.

Шаг 2 . В каждой строке матрицы С  найти минимальный элемент и вычесть его из каждого элемента этой строки.

В результате образуется матрица С 0 с неотрицательными элементами. В каждом столбце и каждой строке матрицы С 0 имеется, по крайней мере, по одному нулю.

Шаг 3 . Отме­тить произвольный нуль в первом столбце звездочкой. Начиная со второго столбца просматривать каждый столбец матрицы С 0 и отмечать в нем звездочкой нуль, расположенный в строке, где нет нуля со звездочкой. В каждом столбце можно отметить звездочкой только один нуль. Очевидно, что нули матрицы С 0 , отмеченные звездочкой, являются по построению независимыми. На этом предварительный этап заканчи­вается.

( k + 1)-я итерация . Допустим, что k -я итерация уже проведена и в результате получена матрица С k . Если в матрице С k имеется ровно п нулей со звездочкой, то процесс решения заканчивается. Если же число нулей со звездочкой меньше п , то переходим к (k + 1)-й ите­рации.

Каждая итерация начинается первым и заканчивается вторым эта­пом. Между ними может несколько раз проводиться пара этапов: третий – первый . Перед началом итерации знаком «+» выделяют столбцы матрицы С k , которые содержат нули со звездочкой .

Первый этап . Просмотреть невыделенные столбцы матри­цы С k . Если среди них не окажется нулевых элементов, то перейти к третьему этапу .

Если же невыделенный нуль матрицы С k обнаружен, то возможен один из двух случаев:

эта строка не содержит нуля со звездочкой.

В первом случае невыделенный нуль отметить штрихом и выделить строку , в которой он содержится, постановкой справа от нее зна­ка «+». Затем уничтожить знак «+», обводя его кружком над тем столбцом , на пересечении которого с данной выделенной строкой со­держится нуль со звездочкой.

 Если такой нуль найден и он единственный в столбце, то отметить его штрихом и выделить строку (строки), содержащую такой нуль (нули), знаком «+». Затем просмотреть эту строку (строки), отыскивая в них нуль со звез­дочкой.

 Если такой нуль в столбце найден, но он не единственный в столбце, то из этих нулей следует выбрать:

в первую очередь такой нуль, в одной строке с которым, нет 0*;

во вторую очередь такой нуль, в одной строке с которым имеется 0*, но в одном столбце с этим 0* имеется невыделенный нуль;

в последнюю очередь такой нуль, в одной строке с которым имеется 0*, но в одном столбце с этим 0* отсутствует невыделенный нуль;

Этот процесс законечное число шагов заканчивается одним изследующих исходов:

Исход 1 . Все нули матрицы С k выделены, т. е. находятся в выделенных строках или столбцах. В этом случае перейти к третьему этапу ;

Исход 2 . Имеется невыделенный нуль в строке, где нет нуля со звездочкой. Тогда перейти ко второму этапу , отметив последний по порядку нуль штрихом .

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

Второй этап . Построить следующую цепочку из элементов матрицы С k : исходный нуль со штрихом, нуль со звездочкой, располо­женный в одном столбце с первым, нуль со штрихом, расположенный в одной строке с предшествующим нулем со звездочкой, и т. д. Итак, цепочка образуется передвижением от 0" к 0* по столбцу , от 0* к 0" по строке и т. д.

Можно доказать, что описанный алгоритм построения цепочки однозначен и конечен. При этом цепочка всегда начинается и закан­чивается нулем со штрихом . Далее над элементами цепочки, стоящими на нечетных местах (0"), поставить звездочки, уничтожая их над четными элементами (0*). Затем уничтожить все штрихи над элементами мат­рицы С k и знаки «+». При этом количество независимых нулей будет увеличено на единицу . (k + 1)-я итерация закончена .

Третий этап . К этому этапу следует переходить после первого этапа в случае, если все нули матрицы С k выделены , т. е. находятся в выделенных строках или столбцах. В таком случае среди невыделенных элементов матрицы С k выбрать минимальный элемент и обозначить его h > 0.

вычесть h из всех элементов матрицы С k , расположенных в невыделенных стро­ках , и

прибавить h ко всем элементам матрицы С k , расположенным в выделенных столбцах .

В результате получается новая матрица , эквивалентнаяС k .

Поскольку среди невыделенных элементов матрицы
появятся новые нули (согласно определению), следует перейти к первому этапу, а вместо матрицыС k рассматривать матрицу
.

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

В первом случае после проведения второго этапа итерация закан­чивается .

Во втором случае после проведения третьего этапа получается матрица
~
~С k . В матрице
появятся невыделенные нули, и всю последовательность операций, начиная с первого этапа, надо повторить.После конечного числа повторений очередной первый этап обязательно закончится переходом на второй этап , при выполнении которого количество независимых нулей увеличится на единицу, а после выполнения которого (k + 1)-я итерация за­канчивается .

Пример 9. Решим венгерским методом задачу:

На боевом надводном корабле имеется 5 зенитных огневых средств (ЗОС). На корабль совершается одновременный налет авиации противника в количестве 5 единиц. Поражающий потенциал каждого i –го ЗОС по j –му летательному аппарату противника равен (количество потенциально уничтожаемыхj –х летательных аппаратов за время атаки НК одним ЛА). Предполагается, что любое ЗОС может обстрелять любую цель.

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

на одну ВЦ может быть назначено только одно ЗОС;

все цели должны быть обстреляны ЗОС.

Решение :

Предварительный этап .





Первая итерация .

Первый этап .

+ +



В

+ +



Вторая итерация .

П

+ +



Поскольку все нули матрицы С 1 выделены следует перейти к третьему этапу.

Третий этап .

+ +