Симметричные двойственные задачи
Разновидностью двойственных задач линейного, программирования являются двойственные симметричные задачи, в которых система ограничений как исходной, так и двойственной задач задается неравенствами, причем на двойственные переменные налагается условие неотрицательности. Исходная задача. Найти матрицу-столбец Х=(x1, x2,…, xn), которая удовлетворяет системе ограничений
(1.12). АХ>А0, Х>0 и минимизирует линейную функцию Z=СХ
Систему неравенств с помощью дополнительных переменных можно преобразовать в систему уравнений, поэтому всякую пару симметричных двойственных задач можно преобразовать в пару несимметричных, для которых теорема двойственности уже доказана. Используя симметричность, можно выбрать задачу, более удобную для решения. Объем задачи, решаемой с помощью ЭВМ, ограничен числом включаемых строк, поэтому задача, довольно громоздкая в исходной постановке, может быть упрощена в двойственной формулировке. При вычислениях без помощи машин использование двойственности упрощает вычисления. Очевидно, для того чтобы записать двойственную задачу, сначала необходимо систему ограничений исходной задачи привести к виду. Для этого второе неравенство следует умножить на -1. Виды математических моделей двойственных задач
Основываясь на рассмотренных несимметричных и симметричных двойственных задач отметим, что пары двойственных задач математических моделей могут быть представлены следующим образом: · Симметричные задачи (1) Исходная задача Двойственная задача Zmin=CX; fmax =Y>A0; AX=A0; YA=С X>0 Y>0 (2) Исходная задача Двойственная задача Zmax =CX; fmin =YA0; AX=A0; YA=С X>0 Y>0 · Несимметричные задачи
(3) Исходная задача Двойственная задача Zmin=CX; fmax=YA0; AX=A0; YA=С X>0 (4) Исходная задача Двойственная задача Zmax=CX; fmin=YA0; AX=A0; YA=С X>0 Поэтому до того, как сформулировать двойственную задачу для данной исходной, необходимо систему ограничений исходной задачи преобразовать должным образом.
Двойственный симплексный метод
Для получения решения исходной задачи можно перейти к двойственной. А используя оценки ее оптимального плана, можно определить оптимальное решение исходной задачи. Если рассмотреть первую симплексную таблицу с единичным дополнительным базисом, тогда переход к двойственной задаче не обязателен. Это связано с тем, что в столбцах определена исходная задача, а в строках – двойственная. bi являются оценками плана двойственной задачи. Сj являются оценками плана исходной задачи. Найдем решение двойственной задачи по симплексной таблице. В симплексной таблице прописана исходная задача. Также определим оптимальный план двойственной задачи. Также найдем и оптимальный план исходной задачи. Такой метод принято называть двойственным симплексным методом. Допустим нужно определить исходную задачу линейного программирования, которая поставлена в общем виде: минимизировать функцию Z=СХ при АХ=A0, Х>0. Значит в двойственной задаче следует максимизировать функцию f=YA0 при YA>С. Пусть определен следующий базис D=(A1, А2,…, Аi,…, Аm), причем в нем хотя бы одна из компонент вектора Х=D-1A0=(x1, x2,…, xi,…, xm) отрицательная. Для всех векторов Aj используется следующее соотношение Zj–Cj >0 (i=1,2,…, n). Пользуясь теоремой двойственности, Y=СбазD-1 является планом двойственной задачи. Этот план не оптимальный. Потому что оценки оптимального плана двойственной задачи должны быть неотрицательными и выбранный базис X содержит отрицательную компоненту и не является планом исходной задачи, а с другой стороны. Поэтому, следует исключить из базиса исходной задачи вектор Аi, который соответствует компоненте xi<0. Данный вектор относится к отрицательной оценке, его необходимо включить в базис двойственной задачи.
Просматриваем i-ю строку для выбора вектора, включаемого в базис исходной задачи. Т.е. если строка не имеет xij<0, тогда линейная функция двойственной задачи не ограничена на многограннике решений. Поэтому нет решений исходной задачи. В противном случае для столбцов, имеющих отрицательные значения, определяем q0j=min(xi/xij)>0. Также находим вектор, который соответствует minq0j(Zj–Cj) при решении исходной задачи на максимум, а также maxq0j(Zj–Cj) при значении исходной задачи на минимум. Найденный вектор включаем в базис исходной задачи. Направляющей строкой определяется вектор, который надо убрать из базиса исходной задачи. Допустим, что q0j=min(xi/xij)=0, т.е. xi=0, тогда xij выбирается как разрешающий элемент, но лишь тогда, когда xij>0. Данный подход к решению задачи не приводит к росту количества отрицательных компонент вектора X. Пока не будет получено Х>0, процесс не прекращается. Определяя оптимальный план двойственной задачи, находим и оптимальный план исходной задачи. Используя при решении, алгоритм двойственного симплексного метода условие Zj–Cj>0 допускается не учитывать, пока не будут исключены все хi<0. Обычным симплексным методом определяется оптимальный план. Этот метод обычно используется при условии, что все хi<0. Чтобы перейти к плану исходной, задачи за одну итерацию надо определить q0j=max(xi/xij)>0. Задачи линейного программирования можно решать двойственным симплексным методом. Системы ограничений в задачах при положительном базисе имеют свободные члены любого знака. Двойственный симплексный метод позволяет значительно уменьшить размеры симплексной таблицы и количество преобразований системы ограничений.
Разработка программы
Постановка задачи
Необходимо спланировать работу швейной мастерской на некоторый период. Установлен перечень выпускаемой продукции, известна рыночная цена каждого продукта. Для производства продукции используются ресурсы: материал, нитки, пуговицы, труд закройщиков, швей-мотористок и т.д. Установлен полный перечень этих ресурсов и общее количество каждого ресурса, которое может быть израсходовано в плановом периоде. Известен расход каждого ресурса на единицу каждого продукта. Необходимо определить, сколько каждой продукции нужно производить, чтобы суммарная рыночная цена всей продукции (выпуск, выручка) была наибольшей.
Введем следующие обозначения: i =1,…, m - номера (индексы) используемых ресурсов; j =1,…, n - номера (индексы) продуктов;
Рис. 2
Каждая строка матрицы соответствует одному ресурсу, каждый столбец – одному продукту. Справа от каждой строки записана величина ограничения по ресурсу (b 1,…, bi,…, bm); внизу каждого столбца - цена продуктов (с1,…, с j,…, с m). В каждой клеточке матрицы записаны так называемые технологические коэффициенты a ij, показывающие расход i -го ресурса на производство единицы j -го продукта. Запишем конкретный числовой пример
Рис. 3
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|