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

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

.

При этом . Отсюда следует, что двойственная переменная y_i является коэффициентом при b_i и, следовательно, показывает, как изменится целевая функция при изменении i- го ресурса на единицу. В литературе двойственные переменные часто называют двойственными оценками. В отчетах EXCEL двойственная оценка называется теневой ценой.

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

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

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

Таким образом, в парах соотношений

из знака строгого неравенства во одном соотношении каждой пары следует знак строгого равенства в другом.

Условия теоремы равновесия часто записывают в виде

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

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

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

Необходимо заметить, что если в качестве канонической формы рассматривается задача максимизации, то сумма берется без знака “-“.

5. Задачи дробно-линейного программирования

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

при условиях

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

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

и ввести новые переменные

.

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

при условиях

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

Пример . Для производства двух видов изделий A и В используются два типа технологического оборудования. Первое изделие проходит обработку только на втором типе оборудования, второе - на первом и на втором. Время обработки каждого из изделий на оборудовании данного типа приведено в табл. 9. Там же указаны затраты, связанные с производством одного изделия каждого вида.

Таблица 9

Оборудование II типа предприятие может использовать не более 52 часов. При этом оборудование I типа целесообразно использовать не менее 16 часов. Требуется определить, сколько изделий каждого вида следует изготовить, чтобы себестоимость одного изделия была минимальной.

Составим математическую модель задачи. За x₁ обозначим количество выпускаемых изделий вида A, за x₂ – количество изделий вида B. Себестоимость определяется следующим образом: С=З/K, где К – количество выпускаемых изделий, З - общие затраты на их производство. Тогда получим следующую задачу дробно-линейного программирования:

;

Преобразуем ограничения-неравенства данной задачи в равенства:

;

Сведем данную задачу к задаче линейного программирования. Для этого обозначим через y₀ и введем новые переменные .

В результате приходим к следующей задаче: найти минимум функции

при условиях

Система ограничений задачи содержит всего одну базисную переменную y₄. Поэтому составим расширенную задачу путем введения двух искусственных переменных y₅ и у₆. :

при условиях

Решение задачи методом искусственного базиса приведено в табл. 10.

Таблица 10

Из таблицы видно, что оптимальным планом задачи является

.

Учитывая, что , находим оптимальный план исходной задачи:

. F(X^*)=220/30.

5. Решение транспортных задач линейного программирования

Пусть имеется m пунктов отправления , из которых сосредоточен однородный груз в количестве единиц, и n пунктов назначения , потребности которых в грузе составляют единиц. Стоимость перевозки единицы груза из пункта A_i в пункт B_j равна с_ij. Необходимо составить такой план перевозки грузов (т.е., определить сколько единиц груза необходимо перевезти из каждого пункта отправления в каждый пункт назначения), который бы обеспечивал вывоз всех грузов из пунктов отправления, удовлетворение всех потребностей в пунктах назначения и имел бы минимальную стоимость.

Обозначим через x_ij количество груза, перевозимого из пункта A_i в пункт B_j. Тогда математическая модель данной задачи может имеет следующий вид:

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

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

1. Транспортная задача – это задача линейного программирования, записанная в канонической форме.

2. Коэффициенты при переменных в системе ограничений транспортной задачи равны равны 0 или 1.

3. Всякая переменная входит только в два уравнения системы ограничений: в i-е уравнение системы (1) и в j-е уравнение системы (2).

4. Число переменных в задаче равно m*n.

5. Число ограничений в транспортной задаче равно m+n.

Пример Производственное объединение имеет в своем составе четыре филиала, которые производят однородную продукцию соответственно в количествах 28, 12 ,11 и 14 единиц. Эту продукцию получают три потребителя, расположенные в разных местах. Их потребности в продукции равны соответственно 20, 30, и 15 единиц. Тарифы перевозок единицы продукции от каждого из филиалов соответствующим потребителям задаются матрицей

Математическая модель для определения плана перевозок минимальной стоимости в данном случае имеет следующий вид:

x₁₁+7x₁₂+8x₁₃+12x₂₁+4x₂₂+6x₂₃+10x₃₁+15x₃₂+14x₃₃+5x₄₁+13x₄₂+16x₄₃ ®min;

x₁₁+x₁₂+x₁₃₌12;

x₂₁+x₂₂+x₂₃=28;

x₃₁+x₃₂+x₃₃=11;

x₄₁+x₄₂+x₄₃=14;

x₁₁+x₂₁+x₃₁+x₄₁₌20;

x₁₂+x₂₂+x₃₂+x₄₂=30;

X₁₃+x₂₃+x₃₃+x₄₃=15;

x_ij³0, .

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

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

Если запасы превышают потребности, вводится фиктивный n+1-й пункт назначения B_n+1. Его потребность равна , а тарифы .

Если потребности превышают запасы, вводится фиктивный m+1 пункт отправления A_m+1. Запас груза в нем равен , а тарифы .

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

A = (120, 280, 160), B = (130, 220, 60, 70), .

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

Решение транспортной задачи осуществляется в 2 этапа: построение начального опорного плана и его улучшение.

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

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

После того как проделаны т+п-2 описанных выше шагов, получают задачу с одним пунктом отправления и одним пунк­том назначения. При этом останется свободной только одна клетка, а запасы оставшегося пункта отправления будут равны потребностям оставшегося пункта назначения. Заполнив эту клетку, тем самым делают (n+m-1)-й шаг и получают искомый опорный план. Следует заметить, что на некотором шаге (но не на последнем) может оказаться, что потребности очередного пункта назначения равны запасам очередного пункта отправле­ния. В этом случае также временно исключают из рассмотрения либо столбец, либо строку (что-нибудь одно). Таким образом, либо запасы соответствующего пункта отправления, либо потреб­ности данного пункта назначения считают равными нулю. Этот нуль записывают в очередную заполняемую клетку. Указанные выше условия гарантируют получение п+т-1 занятых клеток, в которых стоят компоненты опорного плана, что является исход­ным условием для проверки последнего на оптимальность и на­хождения оптимального плана.

Метод северо-западного угла. При нахождении опорного плана транспортной задачи методом северо-западного угла на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначе­ния. Заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного х₁₁ («северо-западный угол») и заканчивается клеткой для неизвестного x_тп, т. е. идет как бы по диагонали таблицы.

Пример. На три базы A₁, A₂, A₃ поступил однородный груз в ко­личествах, соответственно равных 140, 180 и 160 ед. Этот груз требуется перевезти в пять пунктов назначения В₁. В₂, В₃, В₄, В₅ соответственно в количествах 60, 70, 120, 130 и 100 ед. Тарифы перевозок единицы груза с каждого из пунктов отправления в со­ответствующие пункты назначения указаны в таб­лице. При этом тарифы записаны в правом верхнем углу каждой клетки, а значения перевозимых грузов будут указаны в центре соответствующих клеток

Найти план перевозок данной транспортной задачи методом северо-западного угла.

Решение. Здесь число пунктов отправления m=3, а число пунктов назначения п =5. Следовательно, опорный план задачи определяется числами, стоящими в 5+3-1=7 заполненных клетках.

Заполнение таблицы начнем с клетки для неизвестного х₁₁, т. е. попытаемся удовлетворить потребности первого пункта назначе­ния за счет запасов первого пункта отправления. Так как запасы пункта А₁ больше, чем потребности пункта В₁, то полагаем х₁₁=60, записываем это значение в соответствующей клетке табл. 2.3 и временно исключаем из рассмотрения столбец В₁, считая при этом запасы пункта А₁ равными 80.

Рассмотрим первые из оставшихся пунктов отправления а₁ и назначения В₂. Запасы пункта А₁ больше потребностей пункта В₂. Положим Х₁₂=70, запишем это значение в соответствующей клетке табл. 2.3 и временно исключим из рассмотрения стол­бец B₂. В пункте А₁ запасы считаем равными 10 ед. Снова рассмо­трим первые из оставшихся пунктов отправления А₁ и назначе­ния Вз. Потребности пункта из больше оставшихся запасов пункта А₁. Положим X₁₃=10 и исключим из рассмотрения стро­ку А₁. Значение Х₁₃=10 запишем в соответствующую клетку таблицы и считаем потребности пункта из равными 110 ед.

Теперь перейдем к заполнению клетки для неизвестного Х₂₃ и т. д. Через шесть шагов остается один пункт отправления А₃ с запасом груза 100 ед. и один пункт назначения B₃ с потреб­ностью 100 ед. Соответственно имеется одна свободная клетка, которую и заполняем, полагая Х₃₅=100 . В резуль­тате получаем опорный план, представленный в таблице.

Согласно данному плану перевозок, общая стоимость перево­зок всего груза составляет S =2*60 +3*70+4*10+1*110+4*70+7*60+2*100= 1380.

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

Пример. Найти опорный план транспортной задачи из предыдущего примера методом минимального элемента.

Решение. Минимальный тариф, равный 1, находится в клетках для переменной Х₂₃.и Х₂₅ . В клетки с индексами 2,3 и 2,5 заносим величины 120 и 60 соответственно. Тарифы, равные 2, соответствуют клеткам с индексами 11 , 14, 35. В клетку 11 заносим 60 единиц груза, в клетку 14 80 единиц, в клетку 35 40 единиц. Решение продолжаем аналогично. Окончательное решение приведено в таблице.

Общая стоимость перевозок в данном случае

S =2*60 +2*80+120+60+3*70+7*50+2*40=1100

При решении задач метод минимального элемента предпочтительнее.

Для улучшения первоначального опорного плана используется метод потенциалов.

Алгоритм метода потенциалов:

1). Построение первоначального опорного плана.

2). Определение потенциалов пунктов отправления (u_i) и пунктов назначения ( ).

Потенциалы находят из системы уравнений где C_ij - тарифы, стоящие в заполняемых клетках таблицы. Число переменных в этой системе равно m+n, число уравнений m+n-1. Для нахождения решения системы один из потенциалов приравнивается произвольному числу (например, u₁=0) и последовательно находятся значения всех остальных потенциалов.

3). Проверка оптимальности плана.

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

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

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

5). Построение цикла пересчета для выбранной свободной клетки i₀j₀.

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

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

6). Определение величины перераспределения груза.

, где x_ij - перевозки, стоящие в вершинах цикла, отмеченных знаком «-». Клетку, которой соответствует d, обозначим через i₁j₁.

7). Сдвиг по циклу пересчета (перераспределение грузов).

В выбранную для заполнения свободную клетку (i₀,j₀) заносится значение d. Одновременно это число прибавляется к значениям перевозок, стоящих в клетках со знаком «+», и вычитается из значений перевозок, стоящих в клетках со знаком «-». Т.о. клетка (i₀,j₀) становится занятой, а i₁j₁ - свободной.

Замечание: при сдвиге по циклу пересчета число занятых клеток остается const=n+m-1. Если d соответствует нескольким клеткам таблицы, то освобождают одну из них, а в остальные записываются нулевые перевозки и считают их занятыми. Нулевые перевозки записываются и в клетки, которые имеют меньшие тарифы.

8). Переход к шагу 2.

Пример. На 3-х складах сосредоточен однородный груз в количествах 80, 100, и 70 единиц. Данный груз необходимо доставить 4-м потребителям, потребности которых равны соответственно 80, 50, 50, 70 единиц. Матрица тарифов имеет вид:

. Необходимо определить: оптимальный план перевозок.

Составим таблицу транспортной задачи. Начальный план перевозок определим методом минимального элемента. При этом сначала помещаем 70 единиц груза в клетку с индексом 14, имеющую минимальный тариф, затем 10 единиц в клетку 12, 40 единиц в клетку 32, 30 единиц в клетку 38, 50 единиц в клетку 23, 50 единиц в клетку с индексом 21.

Затем определяем потенциалы пунктов отправления и потенциалы пунктов назначения. Для этого составляем уравнения для занятых клеток таблицы:

U₁ +V₂ = 2

U₁ +V₄ = 1

U₂ +V₁ = 6

U₂ +V₃ = 5

U₃ +V₁ = 3

U₃ +V₂ = 2

положим U₁ = 0 и последовательно найдем значения остальных потенциалов.

Получим: U₁ = 0, U₂ = 3, U₃ = 0, V₁ = 3, V₂ = 2, V₃ = 2, V₄ = 1.

Вычислим оценки D_ij для всех свободных клеток таблицы:

D₁₁ = 0 + 3 – 4 = -1

D₁₃ = 0 + 2 – 3 = -1

D₂₂ = 3 + 2 – 3 = 2

D₂₄ = 3 + 1 – 6 = -2

D₃₃ = 0 + 2 – 6 = -4

D₃₄ = 0 + 1 – 3 = -2

Выбираем максимальную положительную оценку. Это оценка D₂₂ = 2. Следовательно, на следующем шаге будет заполнятся клетка с индексом 22. Составим цикл пересчета для данной клетки и пометим его вершины последовательно знаками «+» и «–»:

Пункты отправления	Пункты назначения	Запасы
B1	B2	B3	B4
A1
A2
A3
Потребности

Определим величину перераспределения груза как минимальную из величин, стоящих в минусовых клетках. Это 40 единиц. Прибавляем данную величину к величинам перевозок, стоящим в клетках со знаком + и вычитаем ее из величин перевозок, стоящих в клетках со знаком – :

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

U₁ +V₂ = 2

U₁ +V₄ = 1

U₂ +V₁ = 6

U₂ +V₂ = 3

U₂ +V₃ = 5

U₃ +V₁ = 3

Тогда,

U₁ = 0, U₂ = 1, U₃ = -2, V₁ = 5, V₂ = 2, V₃ = 4, V₄ = 1.

Пересчитываем оценки:

D₁₁ = 0 + 5 – 4 = 1

D₁₃ = 0 – 2 + 3 = 1

D₂₄ = 1 + 1 – 6 = - 4

D₃₂ = -2 + 2 – 2 = -2

D₃₃ = -2 + 4 – 6 = -4

D₃₄ = -2 + 1 – 3 = -4

Имеем две максимальные положительные оценки D₁₁ = D₁₃ = 1. Для заполнения на следующем шаге целесообразно выбрать клетку с индексом 13, т.к. ей соответствует меньший тариф. Строим цикл пересчета для клетки 13:

Пункты отправления	Пункты назначения	Запасы
B1	B2	B3	B4
A1
A2
A3

Величина перераспределения груза равна 10. Перераспределяем груз:

Находим потенциалы пунктов отправления и назначения:

U₁ +V₃ = 3

U₁ +V₄ = 1

U₂ +V₁ = 6

U₂ +V₂ = 3

U₂ +V₃ = 5

U₃ +V₁ = 3

U₁ = 0, U₂ = 2, U₃ = -1, V₁ = 4, V₂ = 1, V₃ = 3, V₄ = 1.

Пересчитываем оценки:

D₁₁ = 0 + 4 – 4 = 0

D₁₂ = 0 + 1 – 2 = -1

D₂₄ = 2 + 1 – 6 = -3

D₃₂ = -1 + 1 – 2 = -2

D₃₃ = -1 + 3 – 6 = -4

D₃₄ = -1 + 1 – 3 = -3

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

ЦЕЛОЧИСЛЕННОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Задачей целочисленного линейного программирования (ЗЦЛП)называется задача линейного программирования, в которой на переменные наложено требование целочисленности. При этом если все переменные задачи должны принимать целочисленные значения, задача называется полностью целочисленной, иначе – частично целочисленной. Если множество допустимых решений задачи является конечным, то задача называется комбинаторной. В-частности, к классу комбинаторных относятся задачи булевой оптимизации, в которых переменные могут принимать только два значения: 0 или 1.

Прикладные задачи целочисленного программирования

Задача о раскрое.

Для изготовления заготовок D₁,…,D_m имеется n способов раскроя материала A₁,…,A_n. -количество заготовок i-го типа, получаемых из единицы материала при способе A_j. Имеется D единиц материала. При раскрое единицы материала по способу A_j имеются отходы площадью . Надо произвести не менее заготовок i-го типа и выполнить план с минимизацией отходов.

Таблица 11



Поиск по сайту

Узнать еще

1. I. Понятие о принципах обучения, их взаимосвязь.
2. III. Взаимосвязь потребления, сбережений и инвестиций. Парадокс бережливости.
3. III. Единство и взаимосвязь процессов воспитания и обучения.
4. IV. Подведение итогов урока.
5. MATHCAD. Назначение. Основные возможности. Простейшие приемы работы.
6. V. Взаимосвязь инфляции и безработицы.
7. VII. Значение Соборного уложения
8. А плотность распределения вероятности промежутков времени между заявками

Публикации по технике и механике

Публикации по биологии

Публикации по информатике

Публикации по строительству

Публикации по физике

Публикации по химии

Публикации по электронике

Публикации по искусству

Публикации по истории

Публикации по медицине

Разделы публикаций