p align="left">X0 + A0,m+1*Xm+1 + ... + A0,n*Xn = A0,0 X1 + A1,m+1*Xm+1 + ... + A1,n*Xn = A1,0 . . . . . . . . . . . . . . . . . . Xi + Ai,m+1*Xm+1 + ... + Ai,n*Xn = Ai,0 . . . . . . . . . . . . . . . . . . Xm + Am,m+1*Xm+1 + ... + Am,n*Xn = Am,0 Данная формальная модель задачи линейного программирования обычно задается в форме так называемой симплекс-таблицы, удобной для выполнения операций симплекс-метода: Симплекс-таблица |
| 1 | X1 | X2 | ... | Xm | Xm+1 | ... | Xn | | X0 | A0,0 | 0 | 0 | ... | 0 | A0,m+1 | ... | A0,n | | X1 | A1,0 | 1 | 0 | ... | 0 | A1,m+1 | ... | A1,n | | X2 | A2,0 | 0 | 1 | ... | 0 | A2,m+1 | ... | A2,n | | ... | ... | ... | ... | ... | ... | ... | ... | ... | | Xm | Am,0 | 0 | 0 | ... | 1 | Am,m+1 | ... | Am,n | | |
Верхняя строка симплекс-таблицы представляет целевую функцию задачи. Каждая строка симплекс-таблицы, кроме первой, соответствует определенному ограничению-равенству задачи. Свободные члены ограничений составляют крайний левый столбец таблицы. Слева от таблицы записаны текущие базисные переменные (X1, ..., Xm). Сверху от таблицы приведен набор всех переменных задачи, где Xm+1, ..., Xn - свободные переменные задачи. Преобразования таблицы надо производить до тех пор, пока не будет получена симплекс-таблица, которая одновременно является прямо и двойственно допустимой. Данный метод получил широкое распространение и большую популярность по сравнению с другими подходами, так как крайне редко на практике встречаются задачи трудные для симплекс-метода.
2.2.2. Геометрический метод Применяется дя задач с двумя переменными. Метод решения состоит в следующем: На плоскости Ох1х2 строятся прямые, которые задают соответствующие ограничения: a11 x1 + a11 x2 + …… + a11 xn = b1 , a21 x1 + a22 x2 + …… + a2n xn = b2 , ………………………………………… am1 x1 + am2 x2 + …… + amn xn = bm . Находим множество всех точек х1,х2, удовлетворяющим всем неравенствам. Такое множество называется областью допустимых решений. Строим вектор и перемещаем линию уровня, который задается уравнением: с1х1+с2х2 = const в направлении вектора до последней точки пересечения с ОДР. Эта точка и дает решение задачи Lmax = значению L в этой точки 2.3. Двойственная задача. Общая схема построения двойственной задачи. Если задана общая задача ЛП: где D определяется системой уравнений и неравенств: то двойственной по отношению к ней называется общая задача ЛП: где D* определяется системой уравнений и неравенств: Как следует из приведенной схемы при переходе от прямой задачи ЛП к двойственной: 1. Тип оптимума меняется на противоположный, т. е. максимум на минимум, и наоборот. 2. Вектор коэффициентов целевой функции c и столбец ограничений b меняются местами. 3. Матрица ограничений задачи А транспонируется. 4. Множество индексов переменных, на которые наложено условие неотрицательности в прямой задаче определяют номера ограничений, имеющих форму неравенств в двойственной задаче . 5. Множество номеров ограничений, имеющих форму неравенств в прямой задаче определяют множество индексов переменных, на которые накладывается условие неотрицательности, в двойственной задаче . Из приведенного определения вытекает важное свойство -- симметричность отношения двойственности, т. е. задача, двойственная по отношению к двойственной, совпадает с прямой (исходной) задачей. ((D*)*, (f*)*)?(D, f), Основные теоремы: Теорема 1. Если одна из двойственных задач имеет конечный оптимум, то другая также имеет конечный оптимум, причем экстремальные значения целевых функций совпадают Теорема 2 ( о дополняющей нежесткости). Для того чтобы план х* и у* являлись оптимальными решениями соответственно задач линейного программирования и двойственной к ним необходимо и достаточно, чтобы выполнялись следующие соотношения: Теорема 3 (об оценках). Значение переменных в оптимальном решении двойственной задачи представляет собой оценки влияния свободных членов bi в системе ограничения прямой задачи на величину целевой функции f(x*) 2.4. Транспортная задача. Одна из наиболее распространенных задач математического программирования -- транспортная задача. В общем виде ее можно представить так: требуется найти такой план доставки грузов от поставщиков к потребителям, чтобы стоимость перевозки (или суммарная дальность, или объем транспортной работы в тонно-километрах) была наименьшей. Следовательно, дело сводится к наиболее рациональному прикреплению производителей к потребителям продукции (и наоборот). В простейшем виде, когда распределяется один вид продукта и потребителям безразлично, от кого из поставщиков его получать, задача формулируется следующим образом. Имеется ряд пунктов производствас объемами производства в единицу времени (месяц, квартал), равными соответственнои пункты потребления потребляющие за тот же промежуток времени соответственно продукции. В случае, если решается закрытая (сбалансированная) задача, сумма объемов производства на всех пунктах-поставщиках равна сумме объемов потребления на всех пунктах-получателях: Кроме того, известны затраты по перевозке единицы продукта от каждого поставщика к каждому получателю -- эти величины обозначаются В качестве неизвестных величин выступают объемы продукта, перевозимого из каждого пункта производства в каждый пункт потребления, соответственно обозначаемые. Тогда наиболее рациональным прикреплением поставщиков к потребителям будет такое, при котором суммарные затраты на транспортировку будут наименьшими: При этом каждый потребитель получает нужное количество продукта: и каждый поставщик отгружает весь произведенный им продукт: Как и во всех подобных случаях, здесь также оговаривается неотрицательность переменных: поставка от какого-то пункта производства тому или иному пункту потребления может быть равна нулю, но отрицательной, т. е. следовать в обратном направлении, быть не может. Рассмотрим таблицу. Строки транспортной таблицы соответствуют пунктам производства (в последней клетке каждой строки указан объем запаса продукта ai), а столбцы -- пунктам потребления (последняя клетка каждого столбца содержит значение потребности bj). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в левом верхнем углу находится цена перевозки единицы продукта, а в правом нижнем -- значение объема перевозимого груза для данных пунктов. Клетки, которые содержат нулевые перевозки (xi,j=0), называют свободными, а ненулевые -- занятыми (xi,j>0). |
| В1 | В2 | …… | Вn | Всего | | | C1,1 | C1,2 | …… | C1,n | а1 | | A1 | C2,1 | C2,2 | …… | C2,n | а2 | | A2 | …. | …. | …. | …. | | | …. | … | … | … | …. | …. | | Am | Cm,1 | Cm,2 | …… | Cm,n | аm | | | b1 | b2 | | bn | | | |
Несбалансированную (открытую) транспортную задачу приводят к виду, показанному выше, искусственно: в модель вводятся так называемые фиктивный поставщик или фиктивный потребитель, которые балансируют спрос и потребление. В настоящее время разработано множество различных алгоритмов решения транспортной задачи: распределительный метод, метод потенциалов, дельта-метод, венгерский метод, метод дифференциальных рент, различные сетевые методы и т. д. Производственно-транспортная задача Это оптимизационная задача, при которой одновременно с установлением объема производства на отдельных предприятиях определяется и оптимальная схема размещения заказов (т. е. прикрепления поставщиков к потребителям). Она имеет особое значение для так называемых многотоннажных производств, где важен транспортный фактор (например, черные металлы, минеральные удобрения, нефтепереработка). Такие задачи математически могут быть представлены в двух видах: в сетевой и в матричной постановке. Будучи основанными на принципах транспортной задачи линейного программирования, они очень сложны и решаются специальными, обычно многостадийными приемами с использованием эвристических элементов. 3. Решение задач
3.1. Решение задачи линейного программирования
3.1.1.Постановка задачи Сформулируем задачу: Определить значения переменных, обеспечивающие минимизацию целевой функции. Составим целевую функцию и зададим ограничения. Пусть Х1, Х2, Х3, Х4, Х5 - неизвестные переменные Целевая функция: L(Х) = 14 х-9 х2 - х4+6,4 х5--> min; Ограничения: g1: 0,9 х + 10 х2-28х4 +5х5 245, g2: 0,8 х+ 1,7х2 -0,2х3 -0,5х4 =9, g3: 6 х + 4х3 - 7х4 + 6,3х5 54, g4: 8 х+6,2х2 -4,8х4 +2,9х5 17,
3.1.2.Ввод данных 1. Введем на рабочий лист Excel необходимые данные. В ячейке В5 запишем выражение целевой функции, а в ячейках В8:В11- левые части ограничений. 2.Командой Сервис, Поиск решения откройем диалоговое окно Поиск решения (рис. 2) и заполним его данными. В поле Установить целевую ячейку введем адрес целевой функции $В$5, в поле Изменяя ячейки - адреса $B$3:$E$3. Переведите переключатель Равной в положение минимальному значению. Чтобы ввести ограничения в окне Поиск решения нажмем кнопку Добавить и на экране появится диалоговое окно Добавление ограничения .
Страницы: 1, 2, 3
|