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

Задача линейного программирования. решена. б) Двойственная задача и её решение.

Рассмотрим исходную задачу (1)- (3). При переходе к двойственной задаче нужно вы¬полнить ряд правил. Во-первых, каждому ограничению (1) исходной задачи соответствует переменная двойственной задачи. Таким образом, здесь будут три двойственные переменные. Во-вторых, ограничения двойственной задачи соответствуют столбцам системы (1); неравенства типа превращаются в неравенства типа, а свободными членами становятся коэффициенты при соответствующих переменных целевой функции (3). В-третьих, целевая функция двойственной задачи оптимизируются не на максимум, а на минимум; коэф¬фициентами становятся свободные члены системы (1). Наконец, двойственные переменные, как и переменные задачи (1)-(3), подчиняются тривиальным условиям неотрицательно¬сти. С учетом этих замечаний задача, двойственная задаче (1)-(3), имеет вид: , (7) (8) (9) Эта задача тоже является задачей линейного программирования и также может быть решена симплекс-методом. Однако обе задачи, прямая и двойственная, тесно связаны между собой, и поэтому мы можем гораздо проще получить решение одну из них, если известно решение другой.

Оптимальное решение задачи (7)-(9) находится в индексной строке последней симплекс-таблицы и столбцах, соответствующих первоначальному базису.

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

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

В данном случае: ; . Сначала определим интервалы устойчивости двойственных оценок по отношению к изменению сырья каждого вида. Запишем неравенство (10): . Матричное неравенство преобразуем в систему скалярных неравенств: или: Рассмотрим устойчивость двойственных оценок к изменению запасов только первого вида сырья, т.е. . Подставляя в систему, найдем: Объединяя эти неравенства, получаем: . Изменение запасов сырья только второго вида дает нам сле¬дующее: Отсюда получаем: . Аналогично исследуем устойчивость по третьему виду сырья ( : . Как и следовало ожидать, произвольное увеличение недефицитного первого вида сырья не изменит его нулевой двойственной оценки. г) Определение нового оптимального плана при измененных запасах сырья. Проверим выполнение неравенства (10) для условий нашей задачи: Так как все компоненты полученного вектора неотрицательны, то, при заданных изме¬нениях запаса сырья двойственные оценки не изменятся.

Это означает, что второй и третий виды сырья также будут использованы полностью, поэтому второе и третье неравенства системы (1) с измененными правыми частями можно записать как уравнения: Получили систему двух уравнений с двумя неизвестными.

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

Нетривиальные неравенства (1) представляют собой полуплоскости, пересечение которых в пределах первого квадранта образует так называемую область допустимых решений (ОДP) задачи линейного программирования. Оптимальный план представляет собой одну из угловых точек ОДР. Построим, например, полуплоскость, отвечающую первому неравенству системы (1): . Эта полуплоскость лежит с одной стороны от прямой, заданной уравнением: Линию, если она не проходит через начало координат, проще всего построить по двум точкам на осях координат.

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

Аналогично построив две другие полуплоскости, получим ОДР (рис.1). Теперь надо найти угловую точку ОДР, в которой целевая функция достигает макси¬мума. Для этого построим вектор роста целевой функции = (50; 70) , который состоит из коэффициентов целевой функции при соответствующих переменных и опорную прямую, перпендикулярную вектору. Передвигая опорную прямую вдоль вектора роста и перпендикулярно ему, получаем, что максимум целевой функции достигается в точке Х – это последняя точка пересечения опорной прямой и ОДР. Точка Х образована пересечением границ 2-го и 3-ro нера¬венств, поэтому эти неравенства запишутся как уравнения: Из (1): , подставим в (2): Решение этой системы дает оптимальный план первоначальной задачи: Как и следовало ожидать, полученные числа совпадают с решением симплекс-методом.

Рис.1. Графическое решение задачи линейного программирования. Задание 2. Транспортная задача. ¬ На трех базах находится однородный груз в количестве т соот¬ветственно.

Этот груз необходимо развезти пяти потребителям потребно¬сти которых в данном грузе равны т. Стоимость перевозок пропорцио¬нальна расстоянию и количеству перевозимого груза. Задана матрица тарифов - стои¬мости перевозки единиц груза от каждой базы каждому потребителю. Необходимо спла¬нировать перевозки так, чтобы их общая стоимость была минимальной. Матрица тарифов: Решение. Составим транспортную таблицу по условиям задачи: ПН ПО Запасы, 16 9 10 12 13 100 5 11 8 6 9 150 7 4 5 16 25 250 Потребности, 100 40 140 60 160 Строки таблицы соответствуют базам (пунктам отправления, ПО), а столбцы - заказчи¬кам (пунктам назначения, ПН). Каждая клетка на пересечении некоторого столбца и какой¬ либо строки соответствует одному маршруту перевозок.

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

Шаг 2. Полученный план проверяется на оптимальность (с помощью метода потенциалов). Если план оптимален, то он и будет решением. Иначе переходим к шагу ¬ 3. Шаг 3. Улучшаем план с помощью метода пересчета по циклу и возвращаемся к шагу 2. На Шаге 1 подготавливается первоначальный опорный план тремя разными методами: методом северо-западного угла, методом минимальной стоимости и методом двойного предпочтения.

Затем из этих трех планов выбирается самый выгодный. Его и под¬вергают процедуре дальнейшей оптимизации методом потенциалов. Рассмотрим метод северо-западного угла, или диагональный метод. В этом методе за¬полнение транспортной таблицы всегда начинается с клетки, т.е. "северо-западного угла" таблицы. Далее, заполнение идет вокруг диагонали таблицы и всегда заканчивается в правом нижнем углу (клетка (3; 5 ). В каждой клетке объем перевозки определяется как наименьшее значение из двух чисел: остатка запаса на базе и остатка заявки потребителя.

Отсюда: В результате получаем опорный план : ПН ПО 100 40 140 60 160 100 16 100 9 10 12 13 150 5 11 40 8 110 6 9 250 7 4 5 30 16 60 25 160 В этом опорном плане 6 занятых клеток. В невырожденном плане их должно быть, где т - число баз, п - число заказчиков. Полученный план является выро¬жденным. Подсчитаем общую стоимость перевозок. Она складывается из произведений объемов перевозок и тарифов по всем занятым клеткам: Как видим, при распределении грузов совсем не учитывается стоимость перевозок.

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

Запишем последовательность заполнения клеток: В результате получаем новый опорный план : ПН ПО 100 40 140 60 160 100 16 9 10 12 10 13 90 150 5 100 11 8 6 50 9 250 7 4 40 5 140 16 25 70 . Теперь построим опорный план методом двойного предпочтения. При этом сначала в каждом столбце отметим галочкой клетку с наименьшей стоимостью, затем то же самое де¬лаем с каждой строкой. Далее максимально возможные объемы перевозок помещаем в клет¬ки, отмеченные двойной галочкой.

Затем распределяем перевозки по клеткам, отмеченным одной галочкой начиная с наименьшей. В оставшейся части таблицы перевозки распределя¬ем по методу минимальной стоимости. Клетки с двумя галочками: Клетки с одной галочкой: Остальные клетки: Получаем новый опорный план: ПН ПО 100 40 140 60 160 100 16 9 10 12 10 13 90 150 5 100 11 8 6 50 9 250 7 4 40 5 140 16 25 70 . В этом опорном плане 7 занятых клеток. Полученный план является невыро-жденным. Шаг 2: проверка плана по методу потенциалов.

Определяем потенциалы поставщиков и потребителей. На этом этапе составляем систему уравнений для потенциалов, используя только заня¬тые клетки. Используем последний опорный план: Заметим, что в этой системе всего неизвестных, а уравнений всего, поскольку в невырожденном опорном плане всего 7 заполненных клеток. Для однозначного решения не хватает одного уравнения. В этом случае один из потенциалов, например, приравнивают нулю. Получаем: . Для свободных клеток вычисляем оценки: (11) Среди полученных оценок имеются отрицательные, значит, найденный план неоптимальный.

Произведем загрузку клетки (3, 1) с наименьшей оценкой. Строим замкнутый цикл: ПН ПО 100 40 140 60 160 100 16 9 10 «-» 12 10 «+» 13 90 150 «-» 5 100 11 8 «+» 6 50 9 250 «+» 7 4 40 5 140 16 «-» 25 70 Получим новый опорный план: ПН ПО 100 40 140 60 160 100 16 9 10 12 13 100 150 5 90 11 8 6 60 9 250 7 10 4 40 5 140 16 25 60 . Вычисляем оценки свободных клеток: Произведем загрузку клетки (2, 5) . Строим замкнутый цикл: ПН ПО 100 40 140 60 160 100 16 9 10 12 13 100 150 «-» 5 90 11 8 6 60 «+» 9 250 «+» 7 10 4 40 5 140 16 «-» 25 60 Получим новый опорный план: ПН ПО 100 40 140 60 160 100 16 9 10 12 13 100 150 5 30 11 8 6 60 9 60 250 7 70 4 40 5 140 16 25 . Вычисляем оценки свободных клеток: Так как все оценки неотрицательны, то получен оптимальный план. Запишем решение транспортной задачи: . Задание № 3.