Классификация моделей и задач в математическом программировании

Примеры экономических задач

1) Задача оптимального распределения ресурсов при планировании выпуска продукции на предприятии (задача об ассортименте). Предположим, что предприятие выпускает n различных изделий. Для их производства требуются m различных видов ресурсов (сырья, вспомогательных материалов, рабочего и машинного времени). Эти ресурсы ограничены и составляют в планируемый период b 1, b 2, …, bm условных единиц. Известны также технологические коэффициенты aij, которые указывают, сколько единиц i -го ресур са требуется для производства изделия j -го вида (i = 1, m; j = 1, n). Пусть прибыль, получаемая предприятием при реализации едини цы изделия j -го вида, равна cj. В планируемый период все показа тели bi, aij и cj предполагаются постоянными. Требуется составить такой план выпуска продукции, при реа лизации которого прибыль предприятия была бы наибольшей. Другими словами, требуется составить о п т и м а л ь н ы й план работы предприятия X x x xn = (1, 2,...,), т.е. найти такие значения переменных x 1, x 2, …, xn (объем выпуска продукции каждого вида), чтобы обеспечить предприятию получение максимальной прибыли от реализации всей продукции и чтобы на ее производство хватило имеющихся в распоряжении ресурсов.

2) задача на максимум выпуска продукции При постановке задачи на максимум выпуска продукции при за­данных ограничениях по ресурсам вводимые переменные и коэффициенты обычно имеют следующий смысл: Х_j - выпуск продукции при использовании j-го технологического способа; C_j – цена единицы продукции при j-м способе производства; a_ij - расход i-го ресурса при j-м способе (коэффициенты материалоемкости, фондоемкости, трудоемкости); b_i - наличие i-го ресурса.

3) задача о смесях (рационе, диете); К задачам о диете относятся задачи, в которых требуется выбрать самый дешевый пищевой рацион, содержащий необходимое количество указанных заранее питательных веществ. Предполагается, что: 1. известен перечень биологически необходимых питательных веществ и их минимальная норма (например, суточная); 2. задан набор продуктов, из которых требуется составить пищевой рацион; 3. имеются нормы содержания различных питательных веществ в единице соответствующего продукта; 4. известна цена единицы каждого продукта, который может быть использован в пищевом рационе. Подобная проблема возникает при выборе рационального корма для скота.

4) транспортная задача Транспортная задача — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи). Для транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).

5) задача о рациональном использовании имеющихся мощностей;

Задача о назначениях

Классификация моделей и задач в математическом программировании

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

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

 

 

Этапы решения экономических задач математическими методами

1-й этап. Построение качественной модели рассматриваемой проблемы, т. е. выделение факторов, которые представляются наиболее важными, и установление закономерностей, которым они подчиняются. Обычно этот этап выходит за пределы математики. 2-й этап. Построение математической модели рассматриваемой проблемы, т. е. запись в математических терминах качественной модели. Таким образом, математическая модель – это записанная в математических символах абстракция реального явления, так конструируемая, чтобы анализ ее давал возможность проникнуть в сущность явления. Математическая модель устанавливает соотношения между совокупностью переменных – параметрами управления явлением. Этот этап включает также построение целевой функции переменных, т. е. такой числовой характеристики, большему (или меньшему) значению которой соответствует лучшая ситуация с точки зрения принимающего решения. Итак, в результате этих двух этапов формируется соответствующая математическая задача. Причем, второй этап уже требует привлечения математических знаний. 3-й этап. Исследование влияния переменных на значение целевой функции. Этот этап предусматривает владение математическим аппаратом для решения математических, задач, возникающих на втором этапе процесса принятия, решения.Широкий класс задач управления составляют такие экстремальные задачи, в математических моделях которых условия на переменные задаются равенствами и неравенствами. Теория и методы решения этих задач как раз и составляют содержание математического программирования. На третьем этапе, пользуясь математическим аппаратом, находят решение соответствующих экстремальных задач. Обратим внимание на то, что задачи математического программирования, связанные с решением практических вопросов, как правило, имеют большое число переменных и ограничений. Объем вычислительных работ для нахождения соответствующих решений столь велик, что весь процесс не мыслится без применения современных электронных вычислительных машин (ЭВМ), а значит, требует либо создания программ для ЭВМ, реализующих те или иные алгоритмы, либо использования уже имеющихся стандартных программ. 4-й этап. Сопоставление результатов вычислений, полученных на 3-м этапе, с моделируемым объектом, т. е. экспертная проверка результатов (критерий практики). Таким образом, на этом этапе устанавливается степень адекватности модели и моделируемого объекта в пределах точности исходной информации.

Принципы построения экономико-математичеких моделей

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

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

3. Принцип преемственности. Сводится к тому, что каждая последующая модель не должна нарушать свойств объекта, установленных или отраженных в предыдущих моделях.

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

 

...

a_m1x₁+a_m2x₂+…+a_mnx_n=b_m

x_j≥0; j=1…n

b_i≥0; i=1…m

Замечание. Если какая-либо правая часть отрицательная, то это уравнение нужно умножить на -1.

Любую задачу можно представить в векторной форме.

АХ=В, где называют решением или планом задачи.

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

Вектор столбец А₀= из свободных членов называется вектором правых частей.

 

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

Построение начального опорного решения. Необходимо в каждом уравнении системы найти базисную переменную (которая входит только в одно уравнение с коэффициентом +1). Обозначаю базисную переменную х_iб. х_1б – базисная переменная первого уравнения и т.д. Составляется первая симплекс-таблица следующим образом.

Сб	хб	А0	C1	C2	…	Cn	θ
х1	х2	…	xn
С1б	х1б	b1			…
С2б	х2б	b2			…
…	…	…	…	…	…	…
Сnб	хnб				…
	Z1-C1	Z2-C2	…	Zn-Cn

Где С_iб коэффициент из целевой функции при соответствующей базисной переменной.

x_jб – базисная переменная из соответствующего уравнения.

b_i – свободные члены системы.

В верхнюю строчку над х выписывают все коэффициенты из целевой функции.

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

 

 

Критерий оптимальности

Проверка на оптимальность опорного плана проходит с помощью критерия оптимальности, переход к другому опорному плану — с помощью преобразований Жордана-Гаусса и с использованием критерия оптимальности.

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

Признак оптимальности заключается в следующих двух теоремах.

Теорема 1. Если для некоторого вектора, не входящего в базис, выполняется условие:

, где ,

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

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

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

 

13. алгоритм стандартного симплекс методоа
1. Если предложена задача на максимум, то сформулировать эквивалентную задачу на минимум (умножить коэффициенты целевой функции на –1).
2. Обеспечить условие bi >= 0, при необходимости умножив для этого соответствующие уравнения системы на –1.
3. Если имеется готовое начальное базисное решение задачи, то перейти к п. 7, иначе перейти к п. 4.
4. Сформулировать вспомогательную ЗЛП (для нахождения начального базисного решения исходной задачи) следующим образом:
целевая функция: xn+1 + … + xn+m
i-тое уравнение системы: ai1x1 + … + ainxn + xn+i = bi
5. Решить вспомогательную ЗЛП, используя данный алгоритм, при этом положив начальным базисом (xn+1,…,xn+m).
6. Если после окончания решения вспомогательной ЗЛП в ее базисе останутся вектора An+i, где i > 0, то:
6.1. Если среди xn+i есть ненулевые, то исходная ЗЛП не имеет решения.
6.2. Если в симплекс-таблице, тем не менее, для всех таких i xij = 0, где j=1..n, то все вспомогательные вектора, вошедшие в базис, из него исключаются. Перейти к п. 7.
6.3. Если существуют ненулевые xij, то принудительно ввести в базис вектор Aj и вывести из базиса вектор Ai. Повторять п. 6.3 до тех пор, пока перестанут выполняться условия п. 6 или будут выполняться условия п. 6.2. После достижения необходимого результата перейти соответственно к п. 7 или к п. 6.2.
7. Сформировать симплекс-таблицу (если был задан начальный базис) заново или путем корректирования симплекс-таблицы вспомогательной ЗЛП (отсечь ненужные ее части).
8. Сделать преобразования симплекс-таблицы таким образом, чтобы матрица, составленная последовательно из векторов текущего базиса, была единичной.
9. Найти оценки Dj = (CБ, Aj) – Cj. Если среди них нет положительных, то перейти к п. 12, иначе выбрать среди них максимальную положительную Dk = max Dj и вывести из базиса соответствующий ей вектор Ak.
10. Положить I-1 = B (множество индексов векторов, входящих в текущий базис). Cтроить In+1 = { i In| для xik > 0 q = min xi,n/xik – одинаково для всех i }, пока очередное In+1 не будет состоять из одного элемента. Вектор с данным индексом необходимо вывести из базиса. Другой вариант: I0 пусто. В этом случае решение ЗЛП: целевая функция не ограничена (бесконечно убывает).
11. Изменить базис (вывести и ввести вектора, которые были определены для этого ранее). Перейти к п. 8.
12. Окончательное оптимальное решение формируется следующим образом: неизвестные, соответствующие не вошедшим в окончательный базис векторам, полагаются равными 0, а неизвестные, соответствующие векторам, вошедшим в базис, берутся из столбца A0 симплекс-таблицы (в этом столбце они распогалаются в том же порядке, в котором в таблице следуют базисные вектора).

 

 

14. Рассматривая симплекс-метод, мы предполагали, что задача линейного программирования является невырожденной, т.е. каждый опорный план содержит ровно m положительных компонент, где m - число ограничений в задаче. В вырожденном опорном плане число положительных компонент оказывается меньше числа ограничений: некоторые базисные переменные, соответствующие данному опорному плану, принимают нулевые значения. Используя геометрическую интерпретацию для простейшего случая, когда n - m = 2 (число небазисных переменных равно 2), легко отличить вырожденную задачу от невырожденной. В вырожденной задаче в одной вершине многогранника условий пересекается более двух прямых, описываемых уравнениями вида xi = 0. Это значит, что одна или несколько сторон многоугольника условий стягиваются в точку.

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

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

 

 

Теоремы двойственности.

Любой задаче линейного программирования можно поставить в соответствие другую задачу, которую называют двойственной или сопряжённой.

Двойственные задачи бывают симметричными и несимметричными.

Теорема 1.

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

Теорема 2.

Для того чтобы допустимое решение исходной задачи являлось оптимальным решением необходимо и достаточно, чтобы при подстановке оптимального решения в систему ограничений исходной задачи выполнялось как строгое неравенство. И тогда при этом i-тая координата оптимального решения двойственной задачи равна 0. Если же i-тая координата оптимального решения двойственной задачи отлична от 0, то i-тое ограничение исходной задачи удовлетворяется как равенство.

 

Теорема двойственности

Для су­ществования оптимального плана любой из пары двойст­венных задач необходимо и достаточно существование допустимого плана для каждой из них.

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

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

 

 

19. Оценки как мера дефицитности ресурсов. Двойственные оценки отражают сравнительную дефицитность факторов производства. Чем выше величина оценки , тем выше дефицитность i-го ресурса. Факторы, получившие нулевые оценки, не являются дефицитными и не ограничивают производство.

Свойство 2. Оценки как мера влияния ограничений на значение целевой функции. Величина двойственной оценки какого-либо ресурса показывает, насколько возросло бы максимальное значение целевой функции, если бы объем данного ресурса увеличился на единицу. В связи с этим значение объективно обусловленной оценки иногда называют теневой ценой ресурса. Теневая цена - это стоимость единицы ресурса в оптимальном решении.

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

 

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

 

 

(2.9)

В том случае, если Δ_j ≤ 0, вариант производства является выгодным, если Δ_j > 0 – вариант невыгоден.

 

20. Третья теорема двойственности позволяет определить зависимость изменения целевой функции начальной задачи от изменения запасов "ресурсов": (В формулировке для несимметричной двойственной задачи)

Если i-ая компонента оптимального плана исходной задачи строго положительна, то i-ое ограничение двойственной задачи при подстановке в нее оптимального плана превращается в строгое равенство

.

Если i-ая компонента оптимального плана исходной задачи равна нулю, то i-ое ограничение двойственной задачи при подстановке в нее оптимального плана имеет вид

.

Доказательство.

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

Но. согласно предыдущей теореме,

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

,

так что i-ая строка матрицы

имеет вид

.

Поэтому, если ,

то должно быть

и

.

Если же ,

то должно быть

, то есть

.

Теорема доказана.

Отметим в заключение, что для симметричных двойственных задач эта теорема звучит так:

Теорема 3. (В формулировке для симметричной двойственной задачи).

Если i-ая компонента оптимального плана какой-то задачи положительна, то i-ое ограничение двойственной ей задачи, при подстановке в не оптимального плана, превращается в строгое равенство.

Наоборот, если i-ое ограничение какой-то задачи, при подстановке в него оптимального плана, превращается в строгое неравенство, то i-ая компонента оптимального плана двойственной ей задачи равна нулю.

Модели транспортной задачи

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

22.Методы построения начального опорного решения.
Метод северо-западного угла.
Существует ряд методов построения начального опорного решения, наиболее простым из которых является метод северо-западного угла. В данном методе запасы очередного поставщика используются для обеспечения запросов очередных потребителей до тех пор, пока не будут исчерпаны полностью, после чего используются запасы следующего по номеру поставщика. Заполнение таблицы транспортной задачи начинается с левого верхнего угла и состоит из ряда однотипных шагов. На каждом шаге, исходя из запасов очередного поставщика и запросов очередного потребителя, заполняется только одна клетка и соответственно исключается из рассмотрения один поставщик или потребитель. Осуществляется это таким образом: 1. если, то и исключается поставщик с номером i,, k=1, 2,..., n, kj,;2. если, то и исключается потребитель с номером j,, k=1, 2,..., m, ki,;3. если, то и исключается либо i-й поставщик,, k=1, 2,..., n, kj,, либо j-й потребитель,, k=1, 2,..., m, ki, Нулевые перевозки принято заносить в таблицу только тогда, когда они попадают в клетку (i,j), подлежащую заполнению. Если в очередную клетку таблицы (i,j) требуется поставить перевозку, а i-й поставщик или j-й потребитель имеет нулевые запасы или запросы, то в клетку ставится перевозка, равная нулю (базисный нуль), и после этого, как обычно, исключается из рассмотрения соответствующий поставщик или потребитель. Таким образом, в таблицу заносят только базисные нули, остальные клетки с нулевыми перевозками остаются пустыми. Во избежание ошибок после построения начального опорного решения необходимо проверить, что число занятых клеток равно m+n-1 и векторы-условия, соответствующие этим клеткам, линейно независимы. Теорема4. Решение транспортной задачи, построенное методом северо-западного угла, является опорным. Доказательство. Число занятых опорным решением клеток таблицы должно быть равно N=m+n-1. на каждом шаге построения решения по методу северо-западного угла заполняется одна клетка и исключается из рассмотрения одна строка (поставщик) или один столбец (потребитель) таблицы задачи. Через m+n-2 шага в таблице будет занято m+n-2 клетки. В то же время останутся невычеркнутыми одна строка и один столбец, при этом незанятая клетка одна. При заполнении этой последней клетки число занятых клеток составит m+n-2+1=m+n-1.Проверим, что векторы, соответствующие занятым опорным решением клеткам, линейно независимы. Применим метод вычеркивания. Все занятые клетки можно вычеркнуть, если проделать это в порядке их заполнения.
Метод минимальной стоимости.
Метод минимальной стоимости прост, он позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи С=(), i=1,2,,...,m, j=1,2,...,n. Как и метод северо-западного угла, он состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости min {}, и исключается из рассмотрения только одна строка (поставщик) или один столбец (потребитель). Очередную клетку, соответствующую, заполняют по тем же правилам, что и в методе северо-западного угла. Поставщик исключается из рассмотрения, если его запасы использованы полностью. Потребитель исключается из рассмотрения, если его запросы удовлетворены полностью. На каждом шаге исключается либо один поставщик, либо один потребитель. При этом если поставщик еще не исключен, но его запасы равны нулю, то на том шаге, когда от данного поставщика требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь, затем поставщик исключается из рассмотрения. Аналогично с потребителем. Теорема5. Решение транспортной задачи, построенное методом минимальной стоимости, является опорным.

Метод потенциалов

Циклом в транспортной таблице называется несколько клеток, соединенных замкнутой ломаной линией, которая в каждой клетке совершает поворот на 90, Знаком " + " отмечают те вершины, в которых перевозки увеличиваются, а знаком "- " - те вершины, в которых перевозки уменьшаются. Перемещение какого-то количества единиц груза по циклу означает увеличение перевозок на это количество единиц в положительных вершинах и уменьшение перевозок на это же количество единиц в отрицательных вершинах. При этом, если перевозки остаются неотрицательными, план остается допустимым. Стоимость плана при этом может меняться. Ценой цикла называется увеличение стоимости перевозок при перемещении единицы груза по этому циклу. Очевидно, цена цикла равна алгебраической сумме стоимостей, стоящих в вершинах цикла, при этом стоимости в положительных вершинах берутся со знаком " +", а стоимости в отрицательных вершинах берутся со знаком " - ". Идея метода потенциалов состоит в следующем. Для любой свободной клетки транспортной таблицы всегда существует единственный цикл, положительная вершина которого лежит в этой свободной клетке, а все остальные - в базисных. Если цена такого цикла отрицательна, то план можно улучшить перемещением перевозок по данному циклу. Количество единиц груза, которое можно переместить, определяется минимальным значением перевозок, стоящих в отрицательных вершинах цикла (если переместить большее число единиц груза, возникнут отрицательные перевозки). Если циклов с отрицательной ценой нет, то это означает, что дальнейшее улучшение плана невозможно, т.е. оптимальный план найден.

Вычислительная схема метода потенциалов

Шаг 1. Строим опорный план (методом северо-западного угла) с

n+m-1 базисными клетками. Шаг 2. Определяем платежи

для всех базисных клеток. Один из платежей (например a1) полагаем равньм нулю. Шаг 3. Считаем псевдостоимости для всех свободных клеток. Если

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

Шаг 4. Если есть свободная клетка, для которой то улучшаем план, перебрасывая перевозки по циклу этой свободной клетки. Шаг 5. Возвращаемся к шагу 2 для пересчета платежей нового опорного плана.

 

 

24Транспортная задача с ограничениями на пропускную способность.
Пусть требуется при решении транспортной задачи ограничить перевозки от поставщика с номером l к потребителю с номером k. Возможны ограничения двух типов: 1); 2), где и - постоянные величины.1. если, то необходимо прежде, чем решать задачу, сократить (уменьшить) запросы l-го поставщика и запросы k-го потребителя на оптимальном решении следует увеличить объем перевозки на величину.2. если, то необходимо вместо k-го потребителя с запросами ввести двух других потребителей. Один из них с номером k должен иметь запросы =, а другой с номером n+1 - запросы. Стоимости перевозок для этих потребителей остаются прежними, за исключением стоимости, которая принимается равной сколь угодно большему числу М(М>>1). После получения оптимального решения величины грузов, перевозимых к (n+1)-му потребителю, прибавляются к величинам перевозок k-го потребителя. Так как =М - самая большая стоимость перевозки, то в оптимальном решении клетка с номером (l, n+1) останется пустой, =0 и объем перевозки не превзойдет.В некоторых задачах требуется запретить перевозки от отдельных поставщиков отдельным потребителям. В таких случаях либо зачеркивают клетку таблицы транспортной задачи, либо назначают соответствующую этой клетке стоимость перевозки единицы груза сколь угодно большой, равной М>>1. В остальном задача решается обычным способом. Для разрешимости данной задачи необходимо существование начального опорного решения.

 

25.Транспортная задача по критерию времени.
Задача по критерию времени возникает при перевозке срочных грузов. Как и в обычной транспортной задаче, имеется m поставщиков с запасами однородного груза в количестве и n потребителей, которым этот груз должен быть доставлен в объеме. Известно, i=1,2,,...,m, j=1,2,...,n - время, за которое груз доставляется от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок груза, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью и наибольшее время доставки всех грузов является минимальным.Составим математическую модель этой задачи. Обозначим - объем перевозимого груза от i-го поставщика j-му потребителю. Система ограничений задачи не отличается от системы ограничений обычной транспортной задачи. Пусть Х=() i=1,2,,...,m, j=1,2,...,n - некоторое опорное решение задачи. Запишем целевую функцию задачи. Обозначим через Т(Х) наибольшее значение элементов матрицы Т=(), i=1,2,,...,m, j=1,2,...,n, соответствующих клеткам таблицы, занятым опорным решением: Т(Х)=. Таким образом, за время Т(Х) план перевозок будет выполнен полностью. Математическая модель имеет вид Т(Х)= (26), i=1,2,...,m, (27), j=1, 2,..., n, (28), i=1,2,,...,m+1, j=1,2,...,n. (29)Задача решается в следующем порядке. Находится начальное опорное решение Х1. определяется значение целевой функции Т(Х1)==. Все свободные клетки, которым соответствует значения >T(X1), исключаются из рассмотрения (перечеркиваются). Занимать эти клетки нецелесообразно, так как повысится значение целевой функции. Чтобы понизить ее значение, необходимо освободить клетку (l1, k1), в которой достигает максимума. Для этого строят так называемые разгрузочные циклы, которые могут включать в свой состав несколько свободных клеток. В каждом разгрузочном цикле, начиная с разгружаемой клетки (l1, k1), расставляются поочередно знаки "-" и "+" и осуществляется сдвиг на величину =. Если удается эту клетку разгрузить, то она исключается из рассмотрения (зачеркивается). Получается новое опорное решение Х2, на котором значение целевой функции меньше, чем на Х1. далее снова пытаются разгрузить клетку, соответствующую Т(Х2)= =. Процесс продолжается до тех пор, пока возможность разгрузить соответствующую клетку не исчезнет.

 

Задача о назначениях.

ЗАДАЧА О НАЗНАЧЕНИЯХ [assignment problem] — вид задачи линейного программирования, с помощью которой решаются вопросы типа: как распределить рабочих по станкам, чтобы общая выработка была наибольшей или затраты на заработную плату наименьшими (поскольку для каждой комбинации “рабочий — станок” характерна своя производительность труда), как наилучшим образом распределить экипажи самолетов, как назначить людей на различные должности (отсюда и название задачи) и т. д.

Математически такие задачи — частный случай распределительных задач с той особенностью, что в них объемы наличных и требующихся для выполнения каждой работы ресурсов равны единице, т. е. aj = bj = 1, и все xij=1, если работник i назначен на работу j, или нулю в остальных случаях (обозначения см. в ст. “Распределительные задачи”). Иначе говоря, для выполнения каждой работы расходуется только один вид ресурса, а каждый ресурс может быть использован на одной работе: ресурсы неделимы между работами, а работы — между ресурсами. Исходные данные группируются в таблице, которая называется матрицей оценок, результаты — в матрице назначений.

Количество возможных вариантов назначений равно факториалу числа работ и ресурсов и огромно даже в небольшой зада