Міністерство освіти і науки україни

Чернігівський Національний Технологічний Університет

Кафедра Інформаційних та комп’ютерних систем

З В І Т

про виконання лабораторної роботи №6

«Розв’язок задач лінійного програмування табличним сімплекс методом»

з дисципліни: «Алгоритми та методи обчислень»

Виконав:

студент групи КІ-133

Мочоний В.О

Керівник:

Старший викладач

Фірсова І. В.

Чернігів 2015

6.1 Цель работы:

отримати навички знаходження екстремумів функції за наявності обмежень засобами МК.

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

Вариант № 5

Фабрика выпускает пряники 3-х наименований. Каждый тип пряников содержит 3 компонента. Соответствующие данные приведены в следующей таблице. На складе имеется сахара – 500 кг., муки – 830 кг., меда – 550 кг. За 1 порцию пряников фабрика получает 30 грн., 45 грн., 35 грн. за 1-е, 2-е, и 3-е наименование соответственно. Найти оптимальный план выпуска продукции, при котором прибыль была бы максимальной с учетом м имеющихся в наличии ресурсов.

	Огонек кг/порц.	Бархатный кг/порц.	Медовик кг/порц.
Сахар	30	15	10
Мука	13	75	50
Мед	30	5	20

Вариант№5a(6, 10, 5); b(5, 5, 8); с_ij= (021, 213, 245).

6.3 Теоретические сведения

6.3.1 Алгоритм табличного симплекс-метода

1. Записываем начальную таблицу коэффициентов, соответствующей задачи ЛП с допустимым начальным базисом, т.е. . Свободные переменные в таблице учитываем со знаком минус. В этом случае анализируем коэффициенты первой строки, которые относятся к целевой функции. Если все, то получено оптимальное решение при решении задачина максимум. Более того, если в строке целевой функции нет нулевых элементов, то решение единственное. Если имеется хотя бы один нулевой элемент, то решений бесчисленное множество. Если есть отрицательный элемент, то решение может быть улучшено;

2. Определяем направляющий столбец, соответствующий той свободной переменной, которую нужно перевести в базис для увеличения значения целевой функции. Выбирается столбец с наибольшим по модулю отрицательным элементом. Если таких несколько, то выбираем любой. Если в выбранном столбце все , то задача не имеет решения (допустимая область не ограничена в направлении экстремума). Если найдется положительный элемент в направляющем столбце или их будет несколько, то выбирается направляющая строка, соответствующая переменной, выводимой из базиса;

3. Выберем направляющую строку, которая удовлетворяет следующему условию

. (6.4)

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

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

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

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

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

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

; (6.5)

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

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

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-й элемент, рассматриваемый в цикле.