![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Теоретические сведения. Индивидуальное заданиеСтр 1 из 2Следующая ⇒
Индивидуальное задание Вариант № 5 Фабрика выпускает пряники 3-х наименований. Каждый тип пряников содержит 3 компонента. Соответствующие данные приведены в следующей таблице. На складе имеется сахара – 500 кг., муки – 830 кг., меда – 550 кг. За 1 порцию пряников фабрика получает 30 грн., 45 грн., 35 грн. за 1-е, 2-е, и 3-е наименование соответственно. Найти оптимальный план выпуска продукции, при котором прибыль была бы максимальной с учетом м имеющихся в наличии ресурсов.
Вариант№5 a (6, 10, 5); b (5, 5, 8); сij = (021, 213, 245).
Теоретические сведения 6.3.1 Алгоритм табличного симплекс-метода 1. Записываем начальную таблицу коэффициентов, соответствующей задачи ЛП с допустимым начальным базисом, т.е. 2. Определяем направляющий столбец, соответствующий той свободной переменной, которую нужно перевести в базис для увеличения значения целевой функции. Выбирается столбец с наибольшим по модулю отрицательным элементом. Если таких несколько, то выбираем любой. Если в выбранном столбце все 3. Выберем направляющую строку, которая удовлетворяет следующему условию
В итоге выберем r -тую строку, на пересечении с которой находится разрешающий элемент 4. Произведем замену выбранной базисной переменной (соответствующую направляющей строке) на выбранную свободную переменную (соответствующую направляющему столбцу), при этом произведем пересчет коэффициентов матрицы по правилу Жордановых преобразований: разрешающий элемент заменяем на обратный ему; все коэффициенты направляющей строки делим на разрешающий элемент; все коэффициенты направляющего столбца дели на разрешающий элемент и изменяем их знак на противоположный; остальные коэффициенты пересчитываются по формуле:
переходим к первому пункту алгоритма для анализа новой матрицы коэффициентов. Таким образом, алгоритм табличного симплекс-метода предусматривает итерационное повторение шагов. 6.3.2 Алгоритм поиска оптимального плана задачи 1. Найти начальный опорный план методом северо-западного угла, при этом число занятых клеток должно быть 2. Для найденного плана вычисляется значение потенциалов ui и vj. Для этого строят систему уравнений для всех клеточек в которых xij > 0. Примечание: Поскольку число переменных в уравнениях n + m, а число уравнений 3. Для каждой клетки начального плана с xij = 0 находим величину sij = (ui - vj) - cij. Если окажутся все sij меньше нуля, то данный план оптимален, иначе переходим к следующему пункту. 4. Улучшение плана. Среди положительных значений sij находим максимальное. Допустим, оно соответствует элементу xsk и для данной свободной клетки матрицы строится цикл пересчета, который начинается с клетки xsk и содержит в качестве вершин непустые клетки. Вершинами цикла считаются клетки, в которых меняется направление перемещения, причем точки пересечения линий перемещения к вершинам не относятся. Нумеруем вершины цикла перемещения, начиная с клетки xsk которой присваивается номер 0. При построении цикла перемещаться можно только по вертикальным и горизонтальным линиям; 5. Среди занятых клеток цикла (пронумерованных) находим клетку, соответствующую минимальному значению xij. Производим перемещение груза по вершинам цикла: из всех нечетных вершин вычитается θ, а ко всем четным оно прибавляется. В результате количество груза не изменяется, но он перемещается; 6. Новый полученный план проверяем на оптимальность по условиям п.3 данного алгоритма. При определении начального плана или в процессе его оптимизации может быть получен вырожденный план. Чтобы избежать зацикливания следует свести задачу к невырожденной, добавив к одной из клеток плана E > 0, соответствующую фиктивной перевозке и решить задачу как невырожденную. В оптимальном плане считать Е = 0. В случае вырожденности начального плана на Е заменяют тот элемент, который требуется для определения значений потенциалов. Для исключения вырожденности при постройке оптимального плана на Е заменяют 0-й элемент, рассматриваемый в цикле. Рукописный вариант решения задачи линейного программирования симплекс-методом и шаблон решаемой задачи линейного программирования симплекс-методом, выполненный в МК.
|