Лекция 12. Уравнение колебаний струны.

Для нахождения необходимо знать точки на предыдущих 2-х слояхи

Для нахождения на 1 слое воспользуемся 2-м начальным условием.

Аппроксимация в этом случае 2-я по hи 1-я по

Если взять более точное представление формулы Тейлора

Аппроксимация 2-го порядка по hи по

Если граничные условия , то 2 порядок аппроксимации сохраняется. Если задаются в виде производной, оно записывается в разностном виде и тогда аппроксимация задачи будет 1-го порядка поhи 2-го по.

Рассмотренная схема условно устойчива, необходимое и достаточное условие устойчивости .

Задание. Программирование расчетного алгоритма решения задачи Дирихле и задачи Неймана.

Линейное программирование( и близкие к нему области математического программирования) –тут,после знакомства с методами конечных разностей.

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

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

Под принятием решений в исследовании операций понимают сложный процесс, в котором можно выделить следующие основные этапы:

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

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

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

3-й этап. Исследование влияния переменных на значение целевой функции. Этот этап предусматривает владение математическим аппаратом для решения математических, задач, возникающих на втором этапе процесса принятия, решения.

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

4-й этап. Сопоставление результатов вычислений, полученных на 3-м этапе, с моделируемым объектом, т. е. экспертная проверка результатов (критерий практики). Таким образом, на этом этапе устанавливается степень адекватности модели и моделируемого объекта в пределах точности исходной информации. Здесь возможны два случая:

* 1-й случай. Если результаты сопоставления неудовлетворительны (обычная ситуация на начальной стадии процесса моделирования), то переходят ко второму циклу процесса. При этом уточняется входная информация о моделируемом объекте и в случае необходимости уточняется постановка задачи (1-й этап), уточняется или строится заново математическая модель (2-й этап), решается соответствующая математическая задача (3-й этап) и, наконец, снова проводится сопоставление (4-й этап).

* 2-й случай. Если результаты сопоставления удовлетворительны, то модель принимается. Когда речь идет о неоднократном использовании на практике результатов вычислений, возникает задача подготовки модели к эксплуатации. Предположим, например, что целью моделирования является создание календарных планов производственной деятельности предприятия. Тогда эксплуатация модели включает в себя сбор и обработку информации, ввод обработанной информации в ЭВМ, расчеты на основе разработанных программ календарных планов и, наконец, выдачу результатов вычислений (в удобном для пользователей виде) для их использования в сфере производственной деятельности.

В математическом программировании можно выделить два направления.

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

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

Традиционно в математическом программировании выделяют следующие основные разделы.

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

2)Нелинейное программирование - целевая функция и ограничения нелинейны. Нелинейное программирование принято подразделять следующим образом:

3)Выпуклое программирование - целевая функция выпукла (если рассматривается задача ее минимизации) и выпукло множество, на котором решается экстремальная задача.,

4)Квадратичное программирование - целевая функция квадратична, а ограничениями являются линейные равенства и неравенства.

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

6)Важным разделом математического программирования является целочисленное программирование, когда на переменные накладываются условия целочисленности.

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

Наконец, заметим, что наименование предмета - "математическое программирование" - связано с тем, что целью решения задач является выбор программы действий.

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

Таблица 1

Тип оборудования	Затраты времени (станко-часы) на обработку одного изделия каждого вида			Общий фонд рабочего времени оборудования (часы)
	А	В	С
Фрезерное	2	4	5	120
Токарное	1	8	6	280
Сварочное	7	4	5	240
Шлифовальное	4	6	7	360
Прибыль (руб.)	10	14	12

Требуется определить, сколько изделий и какого вида следует изготовить предприятию, чтобы прибыль от их реализации была максимальной. Составить математическую модель задачи.

Решение.Предположим, что будет изготовлено x₁единиц изделий вида А, x_2 единиц видаВи x_3 единиц – видаС. Тогда для производства такого количества изделий потребуется затратить 2*x_1+4*x_2+5*x_3 станко-часов фрезерного оборудования.

Так как общий фонд рабочего времени станков данного типа не может превышать 120, то должно выполняться неравенство

2*x_1+4*x_2+5*x_3 <= 120

Аналогичные рассуждения относительно возможного использования токарного, сварочного и шлифовального оборудования приведут к следующим неравенствам:

x_1+8 *x_2+6*x_3<=280,

7*x_1+4*x_2+5*x_3<=240,

4*x_1+6*x_x+7*x_3<=360

При этом, так как количество изготовляемых изделий не может быть отрицательным, то x1>=0; x2>=0; x3>=0;(1)

Далее, если будет изготовлено x₁единиц изделий вида А, x2 единиц изделий видаВи x3 единиц изделий видаС, то прибыль от их реализации составит

F=10*x1+14*x2+12*x3;

Таким образом, приходим к следующей математической задаче: дана система

2*x_1+4*x_2+5*x_3 <= 120,

x_1+8 *x_2+6*x_3<=280,

7*x_1+4*x_2+5*x_3<=240,

4*x_1+6*x_x+7*x_3<=360

четырех линейных неравенств с тремя неизвестными и линейная функция относительно этих же переменных

F=10*x1+14*x2+12*x3 (3).

Требуется среди всех неотрицательных решений системы неравенств (2) найти такое, при котором функция (3) принимает максимальное значение. Как это сделать, будет показано в дальнейшем. Линейная функция (3), максимум которой требуется определить, вместе с системой неравенств (2) и условием неотрицательности переменных (1) образуют математическую модельисходной задачи.

Так как функция (3) линейная, а система (2) содержит только линейные неравенства, то задача (1) - (3) является задачей линейного программирования.

Пример 2.

Продукцией городского молочного завода являются молоко, кефир и сметана, расфасованные в бутылки. На производство 1 т молока, кефира и сметаны требуется соответственно 1010, 1010 и 9450 кг молока. При этом затраты рабочего времени при разливе 1 т молока и кефира составляют 0,18 и 0,19 машино-часов. На расфасовке 1 т сметаны заняты специальные автоматы в течение 3,25 часов. Всего для производства цельномолочной продукции завод может использовать 136000 кг молока. Основное оборудование может быть занято в течение 21,4 машино-часов, а автоматы по расфасовке сметаны – в течение 16,25 часов. Прибыль от реализации 1 т молока, кефира и сметаны соответственно равна 30, 22 и 136 руб. Завод должен ежедневно производить не менее 100 т молока, расфасованного в бутылки. На производство другой продукции не имеется никаких ограничений.

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

Решение.Предположим, что молочный завод будет ежедневно производить x₁тонн молока, x2 тонн кефира иx3 тонн сметаны. Тогда ему для изготовления этой продукции необходимо 1010*x1+1010*x2 +9450*x3 молока.

Так как завод может использовать ежедневно не более 136000 кг молока, то должно выполняться неравенство

1010*x1+1010*x2 +9450*x3<=136000

Аналогичные рассуждения, проведенные относительно возможного использования линий разлива цельномолочной продукции и автоматов по расфасовке сметаны, позволяют записать следующие неравенства:

0.18*x1+0.19 *x2<=21.4

3.25 x2<=16.25

Так как ежедневно должно вырабатываться не менее 100 т молока, то x1>=100. Далее, по своему экономическому смыслу переменныеx2 иx3 могут принимать только лишь неотрицательные значения:x2>=0,x3>=0. Общая прибыль от реализации x1 тонн молока,x2 тонн кефира иx3 тонн сметаны равна 30*x1+22*x2+136*x3 руб.

Таким образом, приходим к следующей математической задаче. Дана система

1010*x1+1010*x2 +9450*x3<=136000

0.18*x1+0.19 *x2<=21.4

3.25 x2<=16.25

x1>=100

четырех линейных неравенств с тремя неизвестными x1,x2,x3 и линейная функция относительно этих же переменных

F=30*x1+22*x2+136*x3(5)

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

Каждая из этих задач является частным случаем общей задачи линейного программирования.

Определение 1.

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

F= (8)

при условиях

(9)

(10) (суммирование всюду проводится от 1 до n)

x_j=>0 (j=1..l,l<=n) (11)

где a_ij, b_i, c_j заданные постоянные величины и k<=m

Определение 2.

Функция (8) называется целевой функцией (или линейной формой) задачи (8) – (11), а условия (9) – (11) – ограничениями данной задачи.

Определение 3.

Стандартной (или симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (8) при выполнении условий (9) и (11), где k = m и l = n.

Определение 4.

Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (8) при выполнении условий (10) и (11), где k = 0 и l = п.

Определение 5.

Совокупность чисел X=(x1,x2,..x_n), удовлетворяющих ограничениям задачи (9) – (11), называется допустимым решением (или планом).

Определение 6.

План X*=(x_1*,x_2*...x_n*);, при котором целевая функция задачи (8) принимает свое максимальное (минимальное) значение, называется оптимальным.

Значение целевой функции (8) при плане Х будем обозначать через F(X). Следовательно, X* – оптимальный план задачи, если для любого Х выполняется неравенство F(X)<= F(X*)[соответственно F(x)>=F(X*) при минимизации].

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

Лекция 2 . Методы математического программирования.

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

Уже упоминалось о самых простых, одноцелевых задачах, исследованием которых занимается математическое  программирование. Слово программирование  в данном случае означает "планирование". К математическому  программированию  относят такие методы:

1.Линейное программирование : состоит в нахождении экстремального значения линейной функции многих переменных при наличии линейных ограничений, связывающих эти переменные; Более подробно этот подход будет изложен при описании симплекс-метода.

Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования. Это объясняется следующим:

* математические модели очень большого числа экономических задач линейны относительно искомых переменных;

* эти типы задач в настоящее время наиболее изучены;

* для них разработаны специальные конечные методы, с помощью которых эти задачи решаются, и соответствующие стандартные программы для их решения на ЭВМ;

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

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

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

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

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

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

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

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

2. Нелинейное программирование : целевая функция и ограничения могут быть нелинейными функциями; Иногда задачу пытаются приблизить линейной (линеаризация), иногда используется правило множителей Лагранжа и в более широком смысле вариационное исчисление.

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

В каждом конкретном случае способ выбирается в зависимости от вида функции F(x).

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

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

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

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

4.Динамическое программирование : для отыскания оптимального решения планируемая операция разбивается на ряд шагов (этапов) и планирование осуществляется последовательно от этапа к этапу. Однако выбор метода  решения на каждом этапе производится с учетом интересов операции в целом;

Это вычислительный метод для решения задач определенной структуры. Направление возникло и сформировалось в 1950-1953 гг. благодаря работам Р. Беллмана над динамическими задачами управления запасами. В упрощенной формулировке динамическое программирование представляет собой направленный последовательный перебор вариантов, который обязательно приводит к глобальному максимуму.

Основные необходимые свойства задач, к которым возможно применить этот принцип:

a. Задача должна допускать интерпретацию как n-шаговый процесс принятия решений.

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

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

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

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

5.Теория графов: с помощью теории графов решаются многие сетевые задачи, связанные с минимальным протяжением сети, построение кольцевого маршрута и др..

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

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

7. Геометрическое программирование. Под задачами геометрического программирования понимают задачи наиболее плотного расположения некоторых объектов в заданной двумерной или трехмерной области. Такие задачи встречаются в задачах раскроя материала для производства каких-то изделий и т.п. Это - еще недостаточно разработанная область математического  программирования и имеющиеся здесь алгоритмы в основном ориентированы на сокращение перебора вариантов с поиском локальных минимумов.

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

Теория массового обслуживания исследует на основе теории вероятностей

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

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

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

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

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

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

Для каждой формализованной игры вводятся правила, т.е. система условий, определяющая:

1. варианты действий игроков;

2. объем информации каждого игрока о поведении партнеров;

3. выигрыш, к которому приводит каждая совокупность действий.

Как правило, выигрыш (или проигрыш) может быть задан количественно; например, можно оценить проигрыш нулем, выигрыш - единицей, а ничью - 1/2.

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

Простейшими являются игры 2 лиц с нулевой суммой.

Пусть в такой игре игрок 1 имеет m выборов и игрок 2 - n выборов. Если игрок 1 делает свой i-й выбор, а игрок 2 - свой j-й выбор, то выигрыш игрока 1 (проигрыш игрока 2) равен Rij. Такая игра называется матричнойи матрица R = [ R_ij/ i=1..m , j=1..n ] называетсяматрицей выигрышей.

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

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

Методы МП можно также делить на аналитические, численно−аналитические и алгоритмические.

Лекция 3. Линейная операционная модель. Симплекс-метод решения задач линейного программирования.

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

F=p_1*x_1+p_2*x_2+..+p_n*x_n-> min(max) (1)

a_i1*x_1+a_i2*x_2+..+a_in*x_n>=a_i(2)

b_i1*x_1+b_i2*x_2+..b_in*x_n=b_i(3)

c_i1*x_1+c_i2*x_2+..c_in*x_n<=c_i(4)

x_j>=0 (5)

Переход от задачи минимизации к задаче максимизации проводится рассмотрением ц.ф.

F_1=-p_1*x_1+..-p_n*x_n;

Неравенства(2) можно переписать в виде

-a_i1*x_1-a_i2*x_2+..-a_in*x_n <= -a_i.

Также любое неравенство вида(4) можно рассматривать как равенство, введя новую неотрицательную переменную t_i

c_i1*x_1+c_i2*x_2+..c_in*x_n + t_i = c_i.

При необходимости можно обратить каждое равенство 2 мя равносильными неравенствами

b_i1*x_1+b_i2*x_2+..+b_in*x_n=b_i

на

b_i1*x_1+b_i2*x_2+..+b_in*x_n<=b_i

-b_i1*x_1-b_i2*x_2+..-b_in*x_n<=-b_i.

Общая задача линейного программирования может

1.Не иметь ни одного допустимого решения

2.иметь единственное допустимое оптимальное решение.

3.иметь несколько допустимых оптимальных решений

4.иметь такие допустимые решения, что целевая функция становится неограниченной

пример к 1)

F=12x_1+15x_2 --->max(1)

4x_1+3x_2<=12(2)

2x_1+5x_2<=10(3)

x_i>=0(4)

можно показать, что максимум достигается в точке пересечения прямых:

4x_1+3x_2=0;

2x_1+5x_2=0;

Заметим также, что 1) если множество решений является непустым, то оно выпукло и может быть как ограниченным, так и неограниченным ; 2) если множество решений непусто, то оптимальное значение целевой функции либо конечно, либо неограниченно велико (в абсолютном смысле)

Симплекс – метод.

В примере оптимальное значение достигается в точке пересечения сторон многогранника- границы области допустимых решений. Для задач линейного программирования это не случайно и неслучайность эта может быть строго доказана. Но нас в первую очередь интересует метод поиска таких решений. Нам надо выбрать оптимальное из значений целевой функции на многограннике границы допустимых решений. Простой перебор в реальных задачах не очень эффективен, так как число операций может оказаться экспоненциальным по размерности задачи. Однако оказывается имеет смысл вычислить значение ЦФ в одной из вершин многогранника, а затем переходить шаг за шагом в ту соседнюю, где ЦФ наиболее оптимальна. Это симплекс-метод, последовательность шагов по вершинам многогранника допустимых планов с целью поиска вершины, где ЦФ примет максимальное значение. Метод получил такое название после применения на многограннике x_1+..+x_n<=1; x_i>=0; который называется симплексом.

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

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

F=2 x_1+3 x_2 +7 x_3+ 9 x_4 ->max (1)

x_1+ x_2+ x_3+ x_4+x_5=9 (2)

x_1+2x_2+4x_3+8x_4+x_6=24 (3)

x_j>=0(j=1..6) (4)

Интуитивно понятно, что сильнее всего на Fдействуетx_4, её коэффициент 9 максимален. ПОТОМУ представляется целесообразным начать решение с нее, назвать ее ПЕРВОЙ БАЗИСНОЙ переменной. Максимальное значение, которое может принять x_4 равно 24/8=3( из ограничения (3)). Если же пробовать использовать x_4=9 по (2) то не выполнятся другие ограничения. В качестве второй базисной переменной примем x_5 так как иной выбор ведет к невыполнению (3) и (4). Значения других(небазисных) переменных принимаем равными 0.Выразим базисные функции и ЦФ через небазисные.

F-2x_1-3x_4-7x_3-9x_4=0;

ЦФ и ограничения записываем в таблицу

	X_1	X_2	X_3	X_4	X_5	X_6
ЦФ	-2	-3	-7	-9	0	0
(2)	1	1	1	1	1	0	9
(3)	1	2	4	8	0	1	24
ЦФ	-7/8	-3/4	-5/2	0	0	9/8	27
(6)	7/8	3/4	½	0	1	-1/8	6
(7)	1/8	1/4	½	1	0	1/8	3

По таблице можно посчитать, что при исключении x_4x_5 также уходит из (3) и (1)

Тогда ЦФ и базис запишутся в виде

F=27+7/8 x_1 +3/4 x_2 +5/2x_3 -9/8 x_6 (5)

X_5=6-7/8 x_1-3/4 x_2 -1/2 x_3+1/8 x_6 (6)

X_3=3-1/8x_1 –1.4x_2-1/2x_3-1/8x_6 (7)

В выражение ЦФ одна из переменных входит с положительным знаком(выберем максимальный коэффициент—он при x_3), ее можно ввести в базис для увеличения ЦФ, заменяем x_4 из базиса наx_3( требуется чтобы переменные оставались неотрицательными)/

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

F_max=43.

После формализации этот процесс можно будет назвать симплекс-методом.

Аналитический метод решения задачи линейного программирования.

Симплекс-метод

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

Мы будем исходить из предположения о том, что любая задача линейного программирования может быть представлена в стандартной форме

(1):

c_1 x_1+..+c_n x_n->max

\Sigma^{j} a_ij x_j<=b_i

x_j>=0

Преобразовать можно систему неравенств в уравнения, как уже указывалось ранее.

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

В системе уравнений W(2), схема приведения к которой системы неравенствиз (1) была ранее описана, содержитсяmбазисных переменныхx_n+1, …,x_n+mиnсвободных –x₁, …,x_n.

Приходим к представлению задачи как системы линейных уравнений:

A_1 X'+ A_2 X''=B

Условия неотрицательности естественно дополнены условиями неотрицательности, наложенными на новые переменные. (4)

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

Вновь введённые переменные, как уже говорилось, обозначающие разность между левыми и правыми частями соответствующих неравенств, будем называть базисными переменными, а множество индексов, которыми помечены базисные переменные будем называть базисом (В)

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

Пример 3. Определение решения по внешнему виду задачи.

Пусть задана некоторая основная задача линейного программирования, вид которой позволяет сразу найти ее решения. Данную задачу можно рассматривать в качестве некоторой уже преобразованной с помощью оператора Lосновной задачи линейного программирования.

[max] F’-20=- x_4- x_3;

-x_4+x_3+x_2 =4

2x_4-x_3 +x_1 =4

-2x_4+1/4x_3 +x_5=2

   Очевидно, что в данной задачи базисом является: B={x_1,x_2,x_5}, тем самым оптимальным решением являетсяx_1=4;x_2=4;x_5=2;x_3=x_4=0; иF’=20;

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

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

Указанные эквивалентные преобразования удобно проводить в специальной таблице, в j-ом столбце которой записаны коэффициенты при x_j.

Рассмотрим теперь некоторую k-тую итерацию алгоритма, реализуемого операторомL. Пусть на данной итерации внешний вид задачи соответствует таблице. Тогда действия алгоритма на данной итерации можно описать следующим образом.

Предположим, что в целевой функции существует хотя бы один положительный коэффициент при свободной переменной. Тогда выберем переменную с наибольшим положительным коэффициентом в целевой функции, в «0»-ой строке таблицы. Столбец, в котором находится выбранная по данному правилу переменная , будем называть e-столбцом.

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

Требуется дополнительно исследовать следующее отношение:

\gamma_i=\frac{a_i0}{a_ie}; i\in B

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

)

Выберем строку, которой соответствует наименьшее положительное значение \gamma_s. Выбранную по этому правилу строку будем называтьs-строкой.

Элемент a_se, стоящий на пересечении e-столбца иs-строки, будем называть  ведущим элементом. Чтобы поменять местамиe-столбец иs-строку, почленно разделим все элементыs-строки на ведущий элемент.

Таким образом, после данных преобразований на месте ведущего элемента всегда будет стоять 1. Исключим переменную x_e из целевой функции и остальных ограничений (т.е. переведем ее из разряда свободных в разряд базисных). Для того, чтобы выполнить эту операцию, необходимо вычесть из оставшихся строк вновь полученную строку, умноженную предварительно на a_ie, получив в е-столбце нули. Для нестолбцовых элементов удобно используется правило треугольника. Если схема выглядит неясной, стоит подробно выписать решение системы с 5 переменными, из них 2 базисных в ЦФ и 2мя ограничениями)

Обычно при решении задач в симплекс-таблицах не записывают столбцы при базисных переменных, содержащие всегда нули и единицы. Очевидно, что эти недостающие столбцы всегда могут быть получены без математических выкладок. Таким образом L-оператор или алгоритм симплекс-метода можно формально описать следующим образом:

1)Вычислить допустимое решение Rв соответствии со следующим правилом:

x_j= 0; для любогоjне вB(j-я переменная НЕ базисная)

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

Соответствие элементов таблицы шага параметрам задачи

x_j=a^{k}_{j0} ( после компиляции в техе )

F=a^k_{00}

2)    Проанализировать значения коэффициентов при свободных переменных:

Если окажется, что все a_{0j}<0 то полученоединственное оптимальное решениеR.

Если окажется, что все a_{0j}<=0, то найдено одно изэквивалентныхрешенийR:

Если окажется, что существует такой коэффициент хотя бы при одной из свободных переменных, что a_{0j}>0 , то необходимо выбирать е-столбец и s-строку

3) Произвести замену е-столбца и s-строки, т.е. включитьeв базис, одновременно исключив из него s. Как это сделать, уточним еще раз для задачи на минимум, с того момента когда ведущий элемент выбран

Общий вид правила треугольника:

a_{ij}^{новое}=a_{ij}- (a_{ie}*a_{sj})/a_{se}

4).       Перейти к пункту 1 алгоритма.

Лекция 4. Двойственный симплекс-метод. Двойственная задача ЛП. Математическая постановка транспортной задачи. Пример решения транспортной задачи.

Двойственная задача ЛП.

1. Нахождение допустимых базисных решений

Определение начального допустимого базисного решения (НДБР) в общем случае представляет значительные трудности. Поэтому для поиска НДБР разработаны специальные методы.

Метод искусственных переменных. Пусть ограничения задачи ЛП имеют вид

Ax <= A_0.

Если все b_i <= 0, \; i = 1, 2,..., m, то свободные векторы, образующие единичную подматрицу, составляют базис, а соответствующие им переменные - начальное базисное решение.

В общем случае, когда некоторые ограничения имеют знак >=, например

a_{i1} x_1 + a_{i2} x_2 + . + a_{in} x_n >= b_i, i=1,2,…, m,

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

a_{11}x_1 +a_{12}x_2 + .. +a_{1n}x_n- 1x_{n+1} + 0x_{n+2} + … + 0x_{n+m} =b_1 ;

a_{21} x_1 + a_{22} x_2 + … + a_{2n} x_n + 0x_{n+1} - 1x_{n+2} +… + 0x_{n+m} = b_2 ;

….

a_{m1} x_1 + a_{m2} x_2 + … + a_{mn} x_n + 0x_{n+1} + 0x_{n+2} + … - 1x_{n+m} = b_m

(1.1)

Свободные переменные {x_n+1,.,x_n+m} в этом случае уже невозможно использовать в качестве начального базиса, так как x_n+1<0,.,x_n+m<0. Поэтому в уравнения (1.1) дополнительно вводят искусственные переменные x_n+m+1,.,x_n+m+k. Эти переменные не имеют ничего общего с реальной задачей, и потому их надо вывести из базиса как можно быстрее. Для этого перед началом итераций искусственным переменным в целевой функции приписывают для задач максимизации очень большие по модулю отрицательные коэффициенты (-М), где M << c_i, \; (i = 1, 2, ..,m).

В случае решения задач минимизации искусственные переменные вводят в целевую функцию с большими положительными коэффициентами (+М).

Знаки искусственных переменных x_n+m+1,.,x_n+m+k должны совпадать со знаками соответствующих свободных членов. Искусственные переменные образуют начальное базисное решение. Применив симплекс-метод, необходимо вывести из базиса все искусственные переменные. Если удается доказать (или показать), что искусственные переменные полностью вывести из базиса невозможно, то это означает, что задача не имеет решения(при таком методе НДБР), то есть ее ограничения противоречивы.

2. Двойственная задача линейного программирования

2.1. Структура и свойства двойственной задачи

Задачу максимизации ЛП с экономической точки зрения можно рассматривать как задачу о распределении ограниченных ресурсов b1,.,bm между различными потребителями, например между определенными технологическими процессами, которые представляются столбцами A1,.,An матрицы ограничений задачи.

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

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

Эта задача имеет такой вид:

Максимизировать f= c_1 x_1 + c_2 x_2 + c_3 x_3 (2.1.1)

при ограничениях

a_{11}x_1 +a_{12}x_2 + …+ a_{13} x_3 <= b_1 ;

a_{21} x_1 + a_{22} x_2 + … + a_{23} x_3 <= b_2 ;

a_{31}x_1 +a_{32}x_2 + … +a_{33}x_3 <=b_3 .

(2.1.2)

где a_1j,a_2j,a_3j- время, необходимое для обработки единицы j-го вида продукции на токарном, фрезеровальном и сверлильном станках соответственно (j=1, 2 ,3), b1, b2, b3 - недельный ресурс машинного времени для группы токарных, фрезеровальных и сверлильных станков.

Обозначим через y1, y2, y3- цену единицы времени работы токарного, сверлильного и фрезеровального оборудования.

Тогда a_11*y1 + a_21*y2 + a_31*y3 можно трактовать как затраты на изготовление единицы продукции первого вида;

Предположим, что цены ресурсов y1, y2, y3 выбраны так, что выполняются соотношения

a_{11}y_1 + a_{12}y_2 + ... + a_{13}y_3 <= c_1 ;

a_{21}y_1 + a_{22}y_2 + . ..+ a_{23}y_3 <= c_2 ;

a_{31}y_1 +a_{32}y_2 + ... +a_{33}y_3 <=c_3 .

(2.1.3.)

Поскольку b1, b2, b3 - общий использованный ресурс машинного времени для каждого из станков, то b1*y1+b2*y2+b3*y3 - общие затраты на производство (общая стоимость использованных ресурсов).

Тогда можно сформулировать следующую задачу:

Требуется определить цены y1, y2, y3, удовлетворяющие условиям (2.1.3), при которых минимизируются суммарные затраты на производство, а именно:

Минимизировать g(y_1,y_2,y_3)=b_1y_1+b_2y_2+b_3y_3 (2.1.4.)

при ограничениях (2.1.3) и

y_1 >= 0, y_2 >= 0, y_3 >= 0.

Задачу (2.1.3), (2.1.4) называют двойственной относительно задачи (2.1.1), называемой прямой.

Запишем прямую и двойственную задачи в общем виде.

Прямая задача:

Максимизировать \sum_{j=1}^n c_j x_j (2.1.5.)

(т.е.) при ограничениях

\sum_{j=1}^n a_{ij} x_j , i=1,2,.,m, (2.1.6.)

x_j >= 0, j=1,2,.,n. (2.1.7.)

Двойственная задача:

Минимизировать \sum_{i=1}^mb_i*y_i(2.1.8.)

при ограничениях

\sum_{i=1}^ma_{ij}y_i>=c_j, \;j=1,2,.,n, (2.1.9.)

y_i >= 0, \; i=1,2,.,m. (2.1.10.)

В матричном виде пара двойственных задач записывается следующим образом:

Прямая задача:

Максимизировать c^T x (2.1.11.)

при ограничениях

Ax <= b; (2.1.12.)

x >= 0 (2.1.13.)

Двойственная задача:

Минимизировать b^T *y (2.1.14.)

при условиях

A^T y >= c; (2.1.15.)

y >= 0 (2.1.16.)

Сопоставляя формы записи прямой и двойственной задач, можно установить между ними следующие взаимосвязи.

1. Если прямая задача является задачей максимизации, то двойственная будет задачей минимизации, и наоборот.

2. Коэффициенты целевой функции прямой задачи c1,...,cn становятся свободными членами ограничений двойственной задачи.

3. Свободные члены ограничений прямой задачи b1,...,bm становятся коэффициентами целевой функции двойственной задачи.

4. Матрица ограничений двойственной задачи получается путем транспонирования матрицы ограничений прямой задачи.

5. Знаки неравенств в ограничениях изменяются на противоположные.

6. Число ограничений прямой задачи равно числу переменных двойственной задачи, и наоборот.

Двойственную задачу лучше решать, чем прямую, если в прямой задаче при малом количестве переменных имеется большое количество ограничений (m > n).

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

Теорема 2.1.1. Если x0 и y0 допустимые решения прямой и двойственной задач, то есть Ax_0 <= b и A^T y_0 >= c, то

c^T x_0 <= b^T y_0, (2.1.17)

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

Доказательство. Умножим выражение (2.1.12) на y_0^T, получим

y_0^TAx_0 <=y_0^Tb. (2.1.18)

Аналогично умножим (2.1.15) на x_0^T:

x_0^TA^Ty_0 >=x_0^Tc. (2.1.19)

Но y_0^TAx_0 = (y_0^TAx_0)^T=x_0^TA^Ty_0, а кроме тогоx_0^Tc=c^Tx_0.

Поэтому, сравнивая (2.1.19) и (2.1.18), получим

y_0^Tb>=y_0^TAx_0 >=x_0^Tc\; или;c^Tx_ 0 <=b^Ty_0.

Чтд

Теорема 2.1.2. (основная теорема двойственности). Если x0 и y0 допустимые решения прямой и двойственной задач и кроме того, если c x0=b y0, то x0 и y0 - оптимальные решения пары двойственных задач.

Доказательство. Согласно теореме 2.1.1 для всех допустимых решений х и у справедливо неравенство (2.1.17). В частности, для всех допустимых решений х справедливо c^T x <= b^T y_0. Однако из условия теоремы cx=b y0 следует c^T x <= c^T x_0. Следовательно, x0 - оптимальное решение.

Вторая часть теоремы доказывается аналогично.

В силу теоремы 2.1.1 для всех допустимых у справедливо c^T x_0 <= b^T y. Но из условия c^T x_0=b^T y_0 следует, что b^T y >= b^T y_0 для всех y >= 0. Таким образом, y0 - оптимальное решение.

Теорема 2.1.3. Если в оптимальном решении прямой задачи (2.1.5) - (2.1.7) i-тое ограничение выполняется как строгое неравенство, то оптимальное значение соответствующей двойственной переменной равно нулю, то есть

Если \sum_{j=1}^na_{ij}x_{j,опт} =A^Ix_{опт} <b_i, тоy_{i, _опт} = 0, (2.1.20)

где Ai - i-я строка матрицы А.

Смысл теоремы 2.1.3 состоит в слeдующем. Если некоторый ресурс b_i имеется в избытке, и i-тое ограничение при оптимальном решении выполняется как строгое неравенство, то это ограничение становится несущественным.

Теорему 2.1.3. дополняет теорема 2.1.4, устанавливающая взаимосвязь между оптимальным решением прямой задачи и ограничениями двойственной.

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

Если; A-j^Ty_{опт} -c_j> 0, тоx_{j,опт} =0. (2.1.21)

Интерпретация теоремы 2.1.4.:

Поскольку величины y_i (i=1,2,.,m) представляют собой цены соответствующих ресурсов, то A^T_j y = \sum_{i=1}^n a_{ij} y_i- это затраты на j-й технологический процесс, величина c_j - прибыль от реализации единицы соответствующего продукта. Поэтому с хозяйственной точки зрения теорема 2.1.4 означает следующее: если j-й технологический процесс оказывается строго невыгодным относительно оптимальных цен ресурсов y_опт, то в оптимальном решении прямой задачи интенсивность использования данного технологического процесса должна быть равна нулю, и соответствующий вид продукции не выпускается как нерентабельный.

Таким образом, теорема 2.1.4 выражает принцип рентабельности для оптимально организованного производства.

Из этой теоремы вытекает также, что если x_{j ,опт} > 0, то

A_j^Ty_{опт} -c_j= 0 (2.1.22)

Предположим, что среди переменных x1, x2, ., x_n прямой задачи есть множество из m переменных, которые в оптимальном решении прямой задачи имеют ненулевые значения. Пусть, например, такими переменными оказались первые по порядку m переменных.

Тогда на основании уравнения (2.1.22) получаем m условий рентабельности:

A^T_1 y_{опт} - c_1 =0;

A^T_2 y_{опт} - c_2 =0;

………

A^T_m y_{опт} - c_m =0;

(2.1.23)

где

A^T_1 = (a_{11}, a_{21}, . , a_{m1});

.....

A^T_m = (a_{1m}, a_{2m}, . , a_{mm}).

Доказательства теорем 2.1.3 и 2.1.4 проведем последовательно.

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

Ax_{опт} -b<= 0; (2.1.24)

A^Ty_{опт} -c>= 0. (2.1.25)

Умножив неравенство (2.1.24) на y^T_{опт}, а неравенство (2.1.25) - на х^T_{опт}, получим

y^T_{опт} Ax_{опт} - y_{опт} b >= 0; (2.1.26)

x^T_{опт}A^T y_{опт} - x^T_{опт} c >= 0. (2.1.27)

Так как в силу теоремы 2.2 y^T_{опт} b = x_{опт} c и y^T_{опт} Ax_{опт} = x^T_{ опт} A^T y{опт}, то выражения (2.1.26), (2.1.27) строго равны нулю.

Расписав левую часть неравенства (2.1.26), получим

y^T_{опт} (Ax_{опт} -b) =y_{1 ,опт} ;

(A^{1}x_{опт} -b_1) +y_{2 , опт} (A^{2}x_{опт} -b_2) + …. +y_{m, опт} (A^{m}x_{опт} -b_m) = 0 . (2.1.28)

Поскольку y_{i ,опт} >= 0 и A^{i} x_{опт} - b_i <=0 для всех i = 1, 2, ..., m, то левая часть уравнения (2.1.28) может быть равна 0 только в том случае, если каждое слагаемое в отдельности равно нулю.

Таким образом, для каждого i, при котором A^{i} x_{опт} - b_i < 0, имеем y_{i, опт} = 0, что и требовалось доказать в теореме 2.1.3.

Рассмотрим теперь левую часть неравенства (2.1.27), предварительно расписав ее

x^T_{опт}A^Ty_{опт} -x^T_{опт}c=x^T_{опт} (A^Ty_{опт} -c) =

x_{1, опт} (A^T_1 y_{опт} - c_1) + …+ x_{2 , опт} (A^T_2 y_{опт} - c_2) + .. + x_{n , опт} (A^T_n y_{ опт} - c_n) = 0,

(2.1.29)

где A=[A1,A2,...,An].

Так как все x_{j, опт} >=0 иA_j^Ty_{опт} -c_j>= 0 для всехj=1,.,n, то уравнение (2.1.29) строго равно нулю, если для каждогоj, при котором (A_j^Ty_{опт} -c_j) > 0, соответствующая переменнаяx_{j,опт} равна нулю.

Приведем еще две важные теоремы теории двойственности.

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

Теорема 2.1.6. (теорема двойственности). Допустимый вектор x0 оптимальный тогда и только тогда, когда в двойственной задаче имеется такое допустимое решение y0, что

c^T x_0 = b^T y_0. (2.1.30)

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

\Delta_{n+1}^{пр} =y_{i, опт} ,

…

\Delta_{m+j}^{дв} =x_{j, опт}}

…

i= 1, 2, ..,m;j= 1, 2, ..,n, (2.1.31)

где n - количество переменных прямой задачи; m - количество ее ограничений;

\Delta_{n+1}^{пр}, \Delta_{m+j}^{дв} - соответствующие элементы индексной строки симплекс-таблицы прямой и двойственной задач соответственно.

При этом, если n+i, где 1 <= i <= m, больше числа векторов-столбцов матрицы ограничений расширенной формы соответствующей задачи, то элементы \Delta_{n+i} , \; \Delta_{m+j} находятся путем циклической перестановки, начиная с элемента \Delta_1.

...

2.2. Общий случай двойственности

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

Пусть прямая задача ЛП задана в виде

\text{максимизировать} \; \sum_{j=1}^n c_j x_j (2.2.1)

при условиях

\sum_{j=1}^n a_{ij} x_j <= b_i , ; i=1,2,..,m_1 <= m ; (2.2.2)

\sum_{j=1}^n a_{ij} x_j = b_i , ; i = m_1 + 1, m_1 + 2, …, m ; (2.2.3)

x_j>=0, \;j= 1,2,…,n_1 <=n.

Тогда двойственная задача по отношению к задаче (2.2.1)-(2.2.3) записывается так:

\text{минимизировать} \; \sum_{i=1}^m b_i y_i (2.2.4)

при условиях

\sum_{i=1}^m a_{ij} y_i >= c_j, \; j = 1,2,…, n_1 <= n ; (2.2.5)

\sum_{i=1}^m a_{ij} y_i = c_j, \; j = n_1+1,n_1+2,…., n ; (2.2.6)

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

1. Если переменная xj прямой задачи предполагается неотрицательной, то j-е условие системы (2.2.5) является неравенством.

2. Если на переменную xj не накладывается ограничение на знак, то j-е ограничение двойственной задачи (2.2.5) будет равенством.

Аналогично связаны знаки переменных двойственной задачи yi и соответствующие им ограничения прямой задачи.

Заметим, что если положить m1=m и n1=n, то получим частный случай пары двойственных задач с ограничениями в форме неравенств.

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

1. Двойственный симплекс - метод

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

Задача ЛП в канонической форме имеет вид:

Максимизировать L(x) = \sum_{j=1}^n c_j x_j (1.1)

при условиях

\sum_{j=1}^na_{ij}x_j=b_{\mu}, \; (\mu= 1,2,…,m) (1.2)

или \sum_{j=1}^n A_j x_j = b , \; x_j >=0, \; j = 1,2,…,n.

Предположим, что n >= m и ранг матрицы А равен m.

Двойственная задача к задаче (1.1), (1.2) записывается так:

Максимизировать} L’ {\deltae} (y) = \sum_{\mu=1}^mb_{\mu}y_{\mu} (1.3)

при условиях

A_j^T y >= c_j,; \sum_{\mu=1}^m a_{ij} y_{\mu} >= c_j , j=1,2,.,n. (1.4)

Назовем “сопряженным базисом”, или базисом двойственной задачи такую систему из m линейно-независимых векторов матрицы ограничений прямой задачи \{ A_i \}_{i \in I_\delta}, для которой базисное решение y соответствующей системы линейных уравнений вида

A_i^T y = c_i, \; i есть \; I_{\delta} (1.5)

удовлетворяет всем ограничением (1.4).

Разложим вектор b по “сопряженному базису”

\sum_{i \in I_{\delta}} A_i x_i = b = A_0 (1.6)

Решив систему (1.6), получим некоторое ее базисное решение \{ x_{i0} \}_{i \in I_{\delta}}, которое называется псевдопланом прямой задачи, для него может выполняться условие неотрицательности переменных x_i0.

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

Как известно, оценки для небазисных векторов \Delta_j определяется в соответствии с

\Delta_j = \sum_{i \in I_{\delta}} c_i x_{ij} - c_j ; j=1,2,…,n . (1.7)

Псевдоплан можно найти и независимо от двойственной задачи. Пусть \{ A_i \}_{i \in I_{\delta}} - произвольная система линейно-независимых векторов прямой задачи.

Выразим все небазисные векторы {Aj} через базисные:

A_j = \sum_{i \in I_{\delta}} A_i x_{ij} , (1.8)

A_0 = b = \sum_{i \in I_{\delta}} A_i x_i . (1.9)

Обозначим решение (1.9) через х0. Тогда можно дать дополнительное определение псевдоплана: n-мерный вектор X, для которого xi = xi0 при i \in I_{\delta}, и xj=0 при j \notin I_{\delta}, является псевдопланом тогда и только тогда, когда все \Delta_j >= 0, \; j=1,…,n.

Доказательство. Векторы \{ A_i \}_{i \in I_{\delta}}, линейно независимы.

Поэтому можно вычислить такой y={y1,y2,...,ym}, для которого

A_j^T y = \sum_{\mu =1}^m a_{\mu} y_{\mu} = c_i, \; i \in I_{\delta} (1.10)

Тогда

\Delta_j = \sum_{i \in I_{\delta}} c_i x_{ij} - c_j = \sum_{i \in I_{\delta}} (\sum_{\mu=1}^m a_{\mu i} y_{\mu}) x_{ij} - c_j = ..

…

\sum_{\mu=1}^m (\sum_{i \in I_{\delta}} a_{\mu i} x_{ij}) y_{\mu} - c_j = \sum_{\mu=1}^m a_{\mu i} y_{\mu} - c_j .

С учетом (1.4) получим

\Delta_j = \sum_{\mu = 1}^m a_{\mu i} y_{\mu} - c_j >= 0, для всех m= 1,..n , (1.11)

что и требовалось доказать.

Рассмотрим некоторый сопряженный базис и соответствующий ему псевдоплан.

Справедлив следующий признак оптимальности: если среди базисных компонентов псевдоплана Х нет отрицательных, то псевдоплан Х={xi0} оказывается оптимальным решением прямой задачи.

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

Пусть известен некоторый сопряженный базис \{ A_i \}, i \in I_{\delta}, которому соответствует псевдоплан х. Очевидно, А_j = \sum_{i \in I_{\delta}} A_i x_{ij}, А_0 = \sum_{i \in I_{\delta}} A_i x_i. При этом в зависимости от знаков {xi} и {xij} может иметь место один из трех случаев:

1. базисные компоненты х_i = х_{i0} > 0 для всех i \in I_{\delta};

2. среди хi имеются отрицательные, причем для некоторого i: хi0<0, а все х_{ij} > 0, j=1,.,n;

3. псевдоплан содержит отрицательные компоненты хi0<0, но для каждой из них среди элементов {хij}, j=1,...,n, имеются отрицательные. В первом случае, как следует из достаточного признака оптимальности, псевдоплан х - оптимальное решение. Во втором случае задача не разрешима. В третьем случае можно перейти к некоторому новому сопряженному базису и, следовательно, к новому псевдоплану с меньшим значением L.

...

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

Каждая итерация содержит два этапа. На первом этапе выясняют, не является ли псевдоплан оптимальным планом прямой задачи, и если нет, то разрешима ли задача. Для этого необходимо вычислить \{ x_i \}, \; i \in I_{\delta} и установить их знаки. Второй этап состоит в осуществлении элементарного преобразования - (одной итерации) метода полного исключения Жордана-Гауcса, приводящего к новому псевдоплану с меньшим значением целевой функции.

Описание алгоритма. Задача ЛП должна быть задана в канонической форме (1.1), (1.2) или сведена к ней. Отыскивают сопряженный базис двойственной задачи и обозначают его \{ A_i \}, i \in I_{\delta}. Разложим А0 по векторам базиса А1,.,Аm в соответствии с (1.9) и найдем псевдоплан \{ х_{i0} \}, i \in I_{\delta} прямой задачи.

Исследуем знаки {хi0}. Если имеет место случай х_{i0} > 0, \; для всех i из I_{\delta}, то начальный псевдоплан является оптимальным планом прямой задачи. При наличии отрицательных компонент {хi0} вычисляем коэффициенты разложения векторов Aj по векторами сопряженного базиса {хij} в соответствии с (1.8).

Если для некоторого r такого, что хr0<0, все х_{rj} > 0 то задача не разрешима (второй случай), и на этом процесс вычислений заканчивается.

Если имеет место третий случай (то есть для каждого r такого, что х_r0<0, по крайней мере одна из компонент х_rj<0), то переходим к второму этапу. С этой целью составляют таблицу k-й итерации (аналогичную симплекс-таблице), которая состоит (m+2) строк и (n+1)-го столбца (табл. 6.1).

Столбец В_x таблицы, как обычно, содержит векторы {Ai} базиса псевдоплана х_k, а столбец А_0 - базисные компоненти псевдоплана {х_i0(k)}. Строка (m+1)-индексная, ее заполняют параметрами \Delta_j^{(k)}, являющимися оценками векторов Аj:

\Delta_j = a_{0j} = \sum_{i \in I_{\delta}} c_i x_{ij} - c_j ,

величина - значение целевой функции при псевдоплане

\Delta_0 = \sum_{i \in I_{\delta}} c_i x_{i0}^{(K)}.

Итерацию k завершают заполнением главной части таблицы (от первой до (m+1)-й строк).

Таблица 6.1. C C1 C2 . Cj . Cn

Bx A0 A1 A2 . Aj . An

C1 X1 X10 X11 X12 . X1j . X1n

C2 X2 X20 X21 X22 . X2j . X2n

. . . . . . . . .

Ci Xi Xi0 Xi1 Xi2 . Xij . Xin

. . . . . . . . .

Cm Xm Xm0 Xm1 Xm2 . Xmj . Xmn

\Delta \Delta_0 \Delta_1 \Delta_2 . \Delta_j . \Delta_n

\Theta \Theta_1 \Theta_2 . \Theta_j .

На первом этапе (k+1)-и итерации выясняют, имеет ли место первый, второй или третий случай.

В третьем случае переходим ко второму этапу. Сначала определяют вектор Аr, который необходимо вывести из базиса. Его индекс r определяют из условия

A_{r0} =min_i{x_i0 |x_i0 < 0 \} (1.14)

т.е. по максимальной по модулю отрицательной компоненте базисного решения.

Затем заполняют элементы (m+2)-й строки, которые вычисляют по формуле

\Theta_j^{(k)} = { - \Delta_j/x_{rj}| x_{rj} < 0 }. (1.15)

В строке \Theta заполняют лишь те позиции, для которых xrj<0. Вектор Аl, который должен быть введен в базис, находят из условия

\Theta_i = \min_j \{ \Theta_j \} = \min_j \left. \left\{ - \frac{\Delta_j}{x_{rj}} \right| x_{rj} < 0 \right\}.

Определив направляющую строку r и столбец l, вычисляют элементы главной части таблицы (k+1)-й итерации по рекуррентным соотношениям

x_{ij}^{(k+1)} =

x_{ij}^{(k)} - \frac{x_{rj}^{(k)}}{x_{ri}^{(k)}} *x_{il}^{(k)}, при} ;i!=r,

\\

\frac{x_{rj}^{(k)}}{x_{ri}^{(k)}}, приi=r,

(1.15)

где x_ri- направляющий элемент преобразования.

Вычислительная схема алгоритма двойственного симплекс-метода похожа на вычислительную схему симплекс-метода. Аналогичны и формы таблиц.

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

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

Отметим некоторые важные свойства двойственного симплекс-метода.

В отличие от прямого симплекс-метода, двойственный симплекс-метод не требует нахождения начального базисного решения (опорного плана), а поиск начального псевдоплана часто может оказаться легче, чем поиск ДБР.

Рассмотрим, например, типичную задачу минимизации

\sum_{j=1}^n c_j x_j (1.17)

при условиях

\sum_{j=1}^n a_{ij} x_j > b_i, \; i=1,2,..,m , (1.18)

x_j > 0 , (1.19)

c_j > 0. (1.20)

Для задачи такого вида найти сразу начальный опорный план нельзя, и поэтому необходимо применить метод искусственных переменных и выполнить значительный объем вычислений. В то же время псевдоплан находится почти автоматически. Действительно, перейдем от (1.17) - (1.19) к эквивалентной задаче в расширенной форме, введя свободные переменные xn+1, xn+2, ., xn+m...

-\sum_{j=1}^n c_j x_j (1.21)

при условиях

\sum_{j=1}^n a_{ij} x_j - 1x_{n+i} = b_i, \; i= 1,..,m (1.22)

Запишем ограничения двойственной задачи

\sum_{i=1}^ma_{ij}y_j>-c_j, \;j= 1,..,n(1.23)

-y_i> 0, \;i= 1,..,m(1.24)

Из неравенств (1.23) - (1.24) видим, что поскольку решение y_i при i=1,m удовлетворяет всем ограничениям (1.23), то сопряженный базис образуют векторы A_n+1,A_n+2,...,A_n+m при свободных переменных. При этом начальный псевдоплан такой:

x_{n+i} = -b_i, ; i= 1,..,m.

Итак, для задачи вида (1.17) - (1.18) пpи условии (1.20) применение двойственного симплекс-метода оказывается предпочтительнее в сравнении с прямым.

Двойственный симплекс-метод позволяет в процессе итерации добавлять новые дополнительные ограничения к уже найденному некоторому промежуточному решению. Это важное его свойство широко используется при решении задач целочисленного программирования.

...

2. Исследование моделей задач линейного программирования на чувствительность

Теория двойственности позволяет анализировать модели ЛП на чувствительность. Рассмотрим обычную задачу ЛП в виде

Максимизировать \sum_{j=1}^nc_jx_j= \maxL(x) (2.1)

при условиях

\sum_{j=1}^n a_{ij} x_j < b_i, \; i=1,2,..,m; \; x_j > 0. (2.2)

Напомним ее экономическую интерпретацию. Целевая функция L(x)- это доход от реализации плана производства x; a_ij- интенсивность расходования i-го ресурса при j-м способе производства; b_i- имеющийся уровень i-го ресурса.

1. Варьирование ограниченных ресурсов. Предположим, что величины ресурсов b=|| bi || варьируются. Тогда возникают вопросы: при каких вариациях правых частей ограничений найденный оптимальный план x_0 не изменяется; как эти вариации влияют на функцию максимального дохода L_max? Ответ на эти вопросы дает анализ соответствующей задачи ЛП на чувствительность.

Пусть ограничение bi получают некоторые вариации \Delta b_i, что приводит к вариациям плана x_0, x_0 = x_0(b+\Delta b) и функции L_{\max} (x_0(b_0 + \Delta b)). Предположим, эти вариации \Delta b таковы, что план x_0(b + \Delta b) остается допустимым (т.е. удовлетворяет условию неотрицательности). Найдем отношения приращения

\Delta L_{\max} (b) = L_{\max} (x_0(b_0+\Delta b)) - L_{\max} (x_0(b)) ;

{к} \Delta b.

Имеем

\lim_{\Delta b_i -> 0} \frac{\Delta L_{\max}(b)}{\Delta b_i} = \frac{\partial L_{\max (b)}}{\partial b_i} , (2.3)

где b рассматривается как варьируемый параметр.

(Выражение \frac{\partialL_{\max(b)}}{\partialb_i} Тех компилирует к виду)

Вспомним, что в соответствии с основной теоремой двойственности

L_{\max} (x_0) = \sum_j c_j x_j^0 = \sum_i b_i, y_i^0 , (2.4)

и, подставляя (2.7.4) в (2.7.3), получим

\frac{\partial L_{\max (b)}}{\partial b_i} = y_i^0, \; i=1,2,..,m . (2.4)

Таким образом, оптимальные значения двойственных переменных y_i^0 определяют вклад каждого ресурса в доход L_max при оптимальном решении x_0. Эта величина численно равна дополнительному доходу при увеличении i-го ресурса b_i на единицу при условии, что ресурсы используются оптимальным образом.

Итак, величины y_i^0 служат показателями важности соответствующих ресурсов для системы. Чем большее значение y_i^0 при некотором i, тем существеннее вклад i-го ресурса в функцию максимального дохода L_max и тем выгоднеее его увеличение. Если для некоторого y_i^0 =0, то i-й ресурс не является существенным ограничением для системы.

Обозначим через Ax матрицу оптимального базиса задачи ЛП при векторе ресурсов b. Очевидно соответствующее оптимальное решение

x_{опт} =A_x^{-1}b.

Предположим, что мы изменили вектор ресурсов b=|| bi || на b_{\text{н}}=b+\Delta b и хотим узнать, как это повлияет на оптимальное решение. Для этого найдем новое соответствующее базисное решение

x_{н} =A^{-1}_xb_{н} =A^{-1}_x(b+ \Deltab).

Если все компоненты x_{i ,н} > 0, то это решение x_{н} = [x_{i,н}] оптимально (т.е. оптимальный базис не изменился). В противном случае нужно произвести поиск нового решения, для этого можно применить двойственный симплекс-метод, начиная с текущего базисного решения x_{н}.

2. Варьирование целевой функции. Теперь рассмотрим случай, когда варьируются коэффициенты {c_j}, j= 1,2,.,n.... Попытаемся выяснить условия, при которых найденный ранее оптимальный план останется оптимальным при таких вариациях.

Пусть вариациям \delta_{c_r} подвергнется коэффициент c_r : c_r^{н} = c_r + \delta_{c_r}. Обозначим через J_б, J_неб множество индексов базисных и небазисных векторов в оптимальном плане x0 соответственно.

Найдем значения оценок \Delta_j^{(\text{н})} после вариации c_r для двух случаев:

1) r \in J_{неб} тогда \Delta_j^{н}=\Delta_j для всех j != r;

\Delta_r^{н} = \sum_{i \in J_{\delta}} c_i a_{ir} - (c_r + \delta_{c_r}) ; для j=r ; (2.6)

2) r \in J_{б},

\Delta_r^{н} = \sum_{i \in J_{\delta}} c_i^{н} a_{ij} - c_j = \sum_{i \in J_{\delta}} c_i a_{ij} + \delta_{c_r} a_{rj} - c_j ; \; j \in J_{неб} (2.7)

Очевидно, что для сохранения оптимальности прежнего плана при вариациях коэффициента cr необходимо и достаточно сохранение знаков оценок \Delta_j^{н} для всех небазисных переменных. Поэтому из условий \Delta_j^{н} > 0 в соответствии с формулами (2.6) и (2.7) можно определить допустимые вариации коэффициента \delta_{c_r}, при которых сохраняется прежнее оптимальное решение.

До сих пор мы рассматривали вариации лишь одного коэффициента целевой функции. Этот же подход можно применить, когда варьируются одновременно несколько коэффициентов ci.

В таком случае получим соотношения, аналогичные (2.7), в которых оценки \Delta_j будут функциями уже нескольких параметров (\delta_1, \delta_2,.,\delta_r)...

Решая совместно систему неравенств вида \Delta_j(c_1, c_2,.,c_r)> 0,\; j \in J_{неб} находим условия для вариаций \delta_{c_r}, при которых прежний оптимальный базис сохраняется.

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

3. Варьирование элементов матрицы ограничений A. Рассмотрим лишь случай вариации компонентов небазисных векторов Aj=[a_ij], i=1,2,...,m, поскольку исследование вариаций компонент базисных векторов A_i довольно сложное, легче заново решить задачу с новыми условиями.

Итак, пусть небазисный вектор Aj=[a_mj] изменился. Нужно выяснить, останется ли оптимальным текущий базис. Для этого полезно применить теорию двойственности. Пусть оптимальный базис прямой задачи Ax, а соответствующие оптимальные значения двойственных переменных y_i^0. Как известно, условие оптимальности \Delta_j > 0, \forall j \in J_{неб}. Вместе с тем в соответствии с (1.11), \Delta_j = \sum_{i \in J_{\delta}} a_{ij} y_i^0 - c_j. Значит, если \Delta_j^{(\text{н})} = \sum_{i \in J_{\delta}} a_{ij} y_i^0 - c_j > 0, то прежний оптимальный базис сохраняется.

4. Добавление еще одного способа производства. Предположим, что первоначально задача имеет вид

Максимизировать \sum_{j=1}^n c_j x_j (2.8)

при условиях

\sum_{j=1}^nA_jx_j<b, \;x_j> 0. (2.9)

Предположим, что найден оптимальный базис \{ A_i \}, i \in J_{\delta} и соответствующие оптимальные решения прямой x_j^0 и двойственной y_j^0 задач.

Пусть прибавляется еще один (n+1)-й способ производства, которому отвечает вектор технологических затрат An+1=[ai n+1] и коэффициент целевой функции c_n+1. Тогда будем иметь следующую задачу:

\text{максимизировать} \; \sum_{j=1}^n c_j x_j + c_{n+1} x_{n+1} (2.10)

при условиях

\sum_{j=1}^nA_jx_j+A_{n+1}x_{n+1} <b, \;x_j> 0, \;j=1,2,.,n+1. (2.11)

Нужно определить, изменится ли при этом прежнее оптимальное решение и при каком значении коэффициента c_n+1 выпуск (n+1)-го продукта будет рентабельным (то есть x_{n+1}^0 > 0).

Чтобы оптимальное решение после ввода вектора An+1 не изменилось, необходимо, чтобы вектор An+1 и переменная xn+1 оставались небазисными, т.е., чтобы \Delta_{n+1} > 0. На основании теории двойственности получим

\Delta_{n+1} = \sum_{i \in J_{\delta}} a_{i n+1} y_i^0 -c_{n+1}.

Если \sum_{i \in J} a_{i n+1} y_i^0 -c_{n+1} \ge 0, то прежний оптимальный план не изменится после включения выпуска (n+1)-го вида продукции.

Если же \sum_{i \in J} a_{i n+1} y_i^0 -c_{n+1} < 0, то выпуск (n+1)-го вида продукции становится рентабельным, и прежний оптимальный план изменяется.

Лекция 4.Математическая постановка транспортной задачи. Пример решения транспортной задачи.

Частным случаем задачи линейного программирования является транспортная задача.ТЗ в общем виде состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления А₁ , А₂ , ..., А_mвnпунктов назначенияB₁ , B₂ , ..., B_n. В качестве критерия оптимальности можно взять минимальную стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим задачу с первым критерием, обозначив через сn тарифы перевозок единицы груза изi-го пункта отправления вj-й пункт назначения, черезa_i- запасы груза в пунктеА_iчерезb_j- потребности в грузе пунктаB_j ,x_ij- количество единиц груза, перевозимого изi-го пункта вj-й пункт. Составим математическую модель задачи. Так как отi-гo поставщика кj-му потребителю запланировано к перевозкеx_ijединиц груза.

Таблица 2.2

Поставщики	Потребители				Запасы
	B1	B2	...	Bn
А1	C11 X11	C12 X12	...	C1n X1n	a1
А2	C21 X21	C22 X22	...	C2n X2n	a2
...	...	...	...	...	...
Аm	Cm1 Xm1	Cm2 Xm2	...	Cmn Xmn	am
Потребности	b1	b2	...	bn	∑ai=∑bj

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

Z=\Sigma\Sigma c_ij *x_ij (2.17)

при условиях:

\Sigma_{j} x_ij =a_i	(i = l, ..., m),	(2.18)
\Sigma_{i}x_ij=b_j	(j = 1, ..., n),	(2.19)
xij ≥ 0	(i = l, ..., m; j = l, ..., n).	(2.20)

Всякое неотрицательное решение систем уравнений (2.18)-(2.20), определяемое матрицей X=(x_ij ), называют опорным планом ТЗ, а планX*=(x_ij ), при котором функцияZпринимает минимальное значение - называетсяоптимальным планомТЗ. Все данные, а затем и опорный план, удобно занести в распределительную таблицу Если общее количество груза в пунктах отправления и общая потребность в нем в пунктах назначения совпадают, т.е. \Sigmaa_i= \Sigmab_j(2.21)

то модель ТЗ называется закрытой.

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