Теоретические сведения. Индивидуальное задание

Индивидуальное задание

Вариант № 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. Выберем направляющую строку, которая удовлетворяет следующему условию

. (6.4)

В итоге выберем r -тую строку, на пересечении с которой находится разрешающий элемент ;

4. Произведем замену выбранной базисной переменной (соответствующую направляющей строке) на выбранную свободную переменную (соответствующую направляющему столбцу), при этом произведем пересчет коэффициентов матрицы по правилу Жордановых преобразований:

Ÿ разрешающий элемент заменяем на обратный ему;

Ÿ все коэффициенты направляющей строки делим на разрешающий элемент;

Ÿ все коэффициенты направляющего столбца дели на разрешающий элемент и изменяем их знак на противоположный;

Ÿ остальные коэффициенты пересчитываются по формуле:

; (6.5)

Ÿ переходим к первому пункту алгоритма для анализа новой матрицы коэффициентов.

Таким образом, алгоритм табличного симплекс-метода предусматривает итерационное повторение шагов.

6.3.2 Алгоритм поиска оптимального плана задачи

1. Найти начальный опорный план методом северо-западного угла, при этом число занятых клеток должно быть .

2. Для найденного плана вычисляется значение потенциалов u_i и v_j. Для этого строят систему уравнений для всех клеточек в которых x_ij > 0. Примечание: Поскольку число переменных в уравнениях n + m, а число уравнений , то для решения системы необходимо положить одну из переменных равной нулю.

3. Для каждой клетки начального плана с x_ij = 0 находим величину s_ij = (u_i - v_j) - c_ij. Если окажутся все s_ij меньше нуля, то данный план оптимален, иначе переходим к следующему пункту.

4. Улучшение плана. Среди положительных значений s_ij находим максимальное. Допустим, оно соответствует элементу x_sk и для данной свободной клетки матрицы строится цикл пересчета, который начинается с клетки x_sk и содержит в качестве вершин непустые клетки. Вершинами цикла считаются клетки, в которых меняется направление перемещения, причем точки пересечения линий перемещения к вершинам не относятся. Нумеруем вершины цикла перемещения, начиная с клетки x_sk которой присваивается номер 0. При построении цикла перемещаться можно только по вертикальным и горизонтальным линиям;

5. Среди занятых клеток цикла (пронумерованных) находим клетку, соответствующую минимальному значению x_ij. Производим перемещение груза по вершинам цикла: из всех нечетных вершин вычитается θ, а ко всем четным оно прибавляется. В результате количество груза не изменяется, но он перемещается;

6. Новый полученный план проверяем на оптимальность по условиям п.3 данного алгоритма.

При определении начального плана или в процессе его оптимизации может быть получен вырожденный план. Чтобы избежать зацикливания следует свести задачу к невырожденной, добавив к одной из клеток плана E > 0, соответствующую фиктивной перевозке и решить задачу как невырожденную. В оптимальном плане считать Е = 0. В случае вырожденности начального плана на Е заменяют тот элемент, который требуется для определения значений потенциалов. Для исключения вырожденности при постройке оптимального плана на Е заменяют 0-й элемент, рассматриваемый в цикле.

Рукописный вариант решения задачи линейного программирования симплекс-методом и шаблон решаемой задачи линейного программирования симплекс-методом, выполненный в МК.