Задача о смесях

Введение
1. Стандартная и каноническая формы зада линейного программирования
1.1. Постановка задачи линейного программирования о выборе оптимальной программы выпуска продукции
1.2. Постановка задачи линейного программирования о смеси
1.3. Алгоритм симплекс-метода
1.4. Алгоритм графического решения задач линейного программирования
2. Пример решения задачи о смесях
Заключение
Список использованной литературы

Задача о смесях

Прародительницей этих задач была так называемая задача о диете: найти наиболее дешевую смесь пищевых продуктов 1, 2, …, m (хлеба, мяса, молока и пр.) которая удовлетворяла бы определенным биологическим ограничениям на содержание жиров, белков, углеводов, микроэлементов, витаминов и тому подобных биологически активных веществ. Если обозначить через xj процентное содержание (по весу) j-го продукта в смеси, через aij - весовое содержание i-го вещества в j-ом продукте, pi - допустимую верхнюю границу содержания i-го вещества в смеси, qi - нижнюю, а через cj - стоимость j-го продукта, то задача о наиболее дешевой диете приобретает вид: minj=1ncjxj (1.6)qi≤j=1naijxj≤pi (1.7)Для этой задачи характерно наличие двусторонних ограничений на значение определенных линейных комбинаций переменных. Эта особенность весьма часто встречается в практике линейного программирования и специальным образом учитывается как в алгоритмах, так и в формах представления данных. Приведенная интерпретация задачи имеет скорее учебно-педагогическое, чем реально-практическое значение. В действительности в качестве продуктов (хлеба, ...) могут выступать, например, различные виды нефти, полученные с разных месторождений. Эти виды отличаются по составу: они содержат различные концентрации примесей серы, парафинов, воды и прочих веществ, существенно влияющих на процесс термического разложения нефти на бензины, керосин и другие нефтепродукты. Для наилучшей эффективности и безопасности технологического процесса концентрации вышеупомянутых примесей должны находиться в определенных пределах, что достигается смешиванием различных видов сырой нефти. Учитывая то, что стоимости различных видов нефти существенно отличаются, задача подбора наиболее дешевой смеси, укладывающейся в технологические допуски, может дать существенный экономический эффект, преумноженный многомиллионными объемами переработки. Аналогичные проблемы возникают, например, и при производстве металлургического кокса из углей различных месторождений, разработке рациона питания скота и пр. В более реалистичных постановках возникают также и так называемые производственно-транспортные задачи, когда в расходах учитывают и транспортные затраты. Задача составления оптимального рациона для человека сложна, так как приходится учитывать много дополнительных, не всегда формализуемых факторов: вкусовые привязанности, разнообразие блюд и т. д. Однако в животноводстве определение рационов для скота с помощью задачи линейного программирования сегодня не просто реально, но и необходимо. Опыт показывает, что кормление скота рационами, рассчитанными по этому методу, дает существенную экономию (например, в США ими пользуются многие фермеры). Это не означает, разумеется, что каждый сам решает задачу линейного программирования: в разных районах страны издаются справочники рационов кормления, учитывающие местные особенности и возможности, породы скота и т. д.1.3. Алгоритм симплекс-методаРешение канонической задачи симплексным методом существенно облегчается применением так называемых симплексных таблиц. Всякую каноническую задачу можно записать в виде таблицы 1.Таблица 1 заполняется следующим образом: в столбце записываются свободные члены уравнений, в столбцах “x1”, “x2” , …, “xn”, коэффициенты при соответствующих неизвестных этой системы.Слева от столбца в столбце выписываются базисные неизвестные, содержащиеся в соответствующих уравнениях системы.Верхняя строчка и крайний левый столбец содержит коэффициенты при соответствующих неизвестных в неприведенном выражении для функции Если функция выражена только через свободные неизвестные, то соответствующие базисным неизвестным, равны нулю.Последняя строка таблицы называется индексной или оценочной и содержит в условной форме приведенное выражение целевой функции.Если целевая функция выражена как через свободные так и через базисные переменные, то для заполнения оценочной строки воспользуемся формулой: (1.8)Таблица 1 – Симплекс-таблицасjбазисс0с1с2ּּּсqּּּcmcm+1ּּּcpּּּcnθai0x1x2xqxmxm+1xpxnс1с2сqcmx1x2xqxma10a20aq0am01111a1,m+1a2,m+1aq,m+1am,m+1a1pa2paqpampa1na2naqnamnZа00a0,m+1a0pa0nАлгоритм сиплекс-метода содержит следующие этапы:Записываем данную задачу в исходную симплекс–таблицу.Если все элементы оценочной строки симплексной таблицы неотрицательны, то исходный план является оптимальным (теорема 1).Если в оценочной строке содержится отрицательный элемент, над которым в таблице нет положительных элементов, то целевая функция не ограничена сверху и задача не имеет решения (теорема 2).Если над каждым отрицательным элементом оценочной строки в соответствующем столбце есть хотя бы один положительный элемент, то можно перейти к лучшему плану (теорема 3).С этой целью:а) выбираем в исходной таблице разрешающий столбец. Это столбец, соответствующий наименьшей отрицательной оценке. Пусть это столбец, соответствующий переменному хp;б) выбираем разрешающую (q ю) строку из условия θ = (i = 1, 2, …, m).в) элемент разрешающий;г) элементы разрешающей строки делим на разрешающий элемент;д) элементы остальных строк вычисляем по формуле “прямоугольников”;е) элементы индексной строки вычисляются также по формуле (1.8). Эту формулу можно использовать в качестве контроля вычислений.Процесс продолжается до тех пор, пока не возникнут ситуации 2 или 3.При заполнении очередной таблицы удобно придерживаться следующего порядка:а) заполняется второй столбец, содержащий базисные переменные, и первый столбец с коэффициентами при этих переменных;б) заполняются единичные столбцы занесением единиц на пересечении строки и столбца, соответствующих одной и той же переменной;в) рассчитываются элементы разрешающей строки;г) рассчитываются остальные элементы таблицы;д) после того как все строки, включая оценочную, рассчитаны, производится перерасчет тех же оценок по формуле (1.8).Обнаруженная ошибка может быть сразу же исправлена.1.4. Алгоритм графического решения задач линейного программированияГрафический метод основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трёхмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трёх изобразить графически вообще невозможно.Пусть задача линейного программирования задана в двумерном пространстве, то есть ограничения содержат две переменные. Найти минимальное значение целевой функции. Z = c1x1 + c2x2 (1.9)при а11x1 + а12x2≤ b1, а21x1 + а22x2≤ b2, аn1x1 + аn2x2≤ bn (1.10)Каждое из неравенств определяющих границы задачи определяет полуплоскость с граничными прямыми: аi1x1 + аi2x2 + аi3x3 = bi, i = 1, 2, …, n, x1 = 0, x2 = 0.Линейная функция (1.9) при фиксированных значениях является уравнением прямой линии: c1x1 + c2x2 = const. Построим многоугольник решений системы ограничений (1.10) и график линейной функции (1.9) при Z = 0. Тогда поставленной задаче линейного программирования можно дать следующую интерпретацию. Найти точку многоугольника решений, в которой прямая c1x1 + c2x2 = const опорная и функция Z при этом достигает минимума.