Характеристика типовых задач математического моделирования и подходов к их решению

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

В общей постановке задача линейного программирования выглядит следующим образом:

Имеются какие-то переменные х = (х1, х2, … хn) и функция этих переменных f(x) = f (х1, х2, … хn), которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции f(x) при условии, что переменные x принадлежат некоторой области G:

 

 

В зависимости от вида функции f(x) и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Линейное программирование характеризуется тем, что а) функция f(x) является линейной функцией переменных х1, х2, … хnб) область G определяется системой линейных равенств или неравенств.

Математическая модель любой задачи линейного программирования включает в себя:

• максимум или минимум целевой функции (критерий оптимальности);
• систему ограничений в форме линейных уравнений и неравенств;
• требование неотрицательности переменных.

Возникновение и развитие Линейного программирования связано с экономикой. Предположение о линейности экономических зависимостей несколько ограничивает возможности Линейного программирования, однако простота и наглядность линейных моделей, с достаточной степенью точности описывающих экономические процессы, позволяет применять эти модели в различных видах экономической деятельности.

 

1.4 Характеристика симплекс-метода как основного аппарата решения задач линейного программирования

 

Симплекс-метод является основным в линейном программировании. Решение задачи начинается с рассмотрений одной из вершин многогранника условий. Если исследуемая вершина не соответствует максимуму (минимуму), то переходят к соседней, увеличивая значение функции цели при решении задачи на максимум и уменьшая при решении задачи на минимум. Таким образом, переход от одной вершины к другой улучшает значение функции цели. Так как число вершин многогранника ограничено, то за конечное число шагов гарантируется нахождение оптимального значения или установление того факта, что задача неразрешима.

Допустим, предприятие предполагает выпускать два вида продукции и , для производства которых используется сырьё трех видов.

Производство обеспечено сырьем каждого вида в количествах: , , кг. На изготовление единицы изделия требуется затратить сырья каждого вида , , кг., соответственно, а для единицы изделия – , , кг. Прибыль от реализации единицы изделия составляет ден.ед., для единицы изделия – ден.ед. (табл.1.4.1).

 

Таблица 1.4.1

Вид сырья	Продукция		Ограничения по сырью
	А1	А2
1-й	a11	a12	b1
2-й	a21	a22	b2
3-й	a31	a32	b3
Прибыль	c1	c2

 

Составляем математическую модель:

математический моделирование производство транспортный

 

 (1.4.1)

 

Введем базисные переменные и преобразуем исходную задачу к виду:

 

 (1.4.2)

 

Решим систему уравнений относительно базисных переменных x3, x4, x5.

Таблица 1.4.2

Итерация № 0

Базис		Х1	Х2	Х3	Х4	Х5	Свободные члены	Отношение
Х3	C1							596/5
Х4	C2							264/3
Х5	C3							640/2
Z				0	0	0	0	-

 

При составлении исходной симплекс таблицы, коэффициенты при переменных функции Z записываются с противоположными знаками, а свободный член со своим знаком.

 – вектор, составленный из координат соответствующих базисных переменных.

Текущий план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

Будем считать что Z2 наименьший элемент, а строку с наименьшим отношением свободного члена к соответствующему элементу выбранного столбца - строку Х4.

Ведущий столбец Х2, так как ( – наименьшее отрицательное число.

За ведущую выберем строку 2, так как отношение свободного члена к соответствующему элементу выбранного столбца для 2 строки является наименьшим.

Разрешающий элемент .

Разделим элементы строки 2 на разрешающий элемент ( ).

От элементов строки 1 отнимаем соответствующие элементы строки 2, умноженные на .

От элементов строки 3 отнимаем соответствующие элементы строки 2, умноженные на .

От элементов строки Z отнимаем соответствующие элементы строки 3, умноженные на .

Заменяем базисную переменную Х5 на Х1.

Количество итераций будет продолжаться до тех пор, пока в строке Z остаются отрицательные элементы.

Порядок работы с симплекс таблицей

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

Алгоритм перехода к следующей таблице такой:

• просматривается последняя строка (индексная) таблицы и среди коэффициентов этой строки (исключая столбец свободных членов Y0) выбирается наименьшее отрицательное число при отыскании max, либо наибольшее положительное при задачи на min. Если такового нет, то исходное базисное решение является оптимальным и данная таблица является последней;
• просматривается столбец таблицы, отвечающий выбранному отрицательному (положительному) коэффициенту в последней строке- ключевой столбец, и в этом столбце выбираются положительные коэффициенты. Если таковых нет, то целевая функция неограниченна на области допустимых значений переменных и задача решений не имеет;
• среди выбранных коэффициентов столбца выбирается тот, для которого абсолютная величина отношения соответствующего свободного члена (находящегося в столбце свободных членов) к этому элементу минимальна. Этот коэффициент называется разрешающим, а строка в которой он находится ключевой;
• в дальнейшем базисная переменная, отвечающая строке разрешающего элемента, должна быть переведена в разряд свободных, а свободная переменная, отвечающая столбцу разрешающего элемента, вводится в число базисных. Строится новая таблица, содержащая новые названия базисных переменных:
• разделим каждый элемент ключевой строки (исключая столбец свободных членов) на разрешающий элемент и полученные значения запишем в строку с измененной базисной переменной новой симплекс таблицы.
• строка разрешающего элемента делится на этот элемент и полученная строка записывается в новую таблицу на то же место.
• в новой таблице все элементы ключевого столбца = 0, кроме разрезающего, он всегда равен 1.
• столбец, у которого в ключевой строке имеется 0,в новой таблице будет таким же.
• строка, у которой в ключевом столбце имеется 0,в новой таблице будет такой же.
• в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы

В результате получают новую симплекс-таблицу, отвечающую новому базисному решению.

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

 

1.5 Основные этапы, особенности и методы решения транспортной задачи

 

Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

Предположим что на три базы , , поступил однородный груз в количествах: соответственно. Груз требуется развезти в пять пунктов: в пункт в пункт в пункт в пункт в пункт

 

Таблица 1.5.1

Пункт направления	B1	B2	B3	B4	B5	Запасы, ai
A1	c11	c12	c13	c14	c15	A1
A2	c21	c22	c23	c24	c25	A2
A3	c31	c32	c33	c34	c35	A3
Потребности, bj	b1	b2	b3	b4	b5

 

Составим математическую модель данной задачи:

Целевая функция:

 (1.5.1)

 

Ограничения:

 

(1.5.2)

 

 – количество груза, отправляемого с базы в пункт

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

Методы решения транспортных задач

Так как транспортная задача является задачей линейного программирования, то её можно решать симплекс-методом, но в силу своей особенности её можно решить гораздо проще.

Условия задачи удобно располагать в таблице, вписывая в ячейки количество перевозимого груза из Аi в Bj груза Xij ≥ 0, а в маленькие клетки – соответствующие тарифы Cij.(рис. 1.5.1)

 

Рисунок 1.5.1

Затем решение задачи разбивается на два этапа:

• Определение опорного плана (Это решение можно найти, используя метод "северо-западного угла" или метод "минимального элемента".)
• Нахождение оптимального решения путем последовательных операций. Метод северо-западного угла

Сущность метода заключается в том, что на каждом шаге заполняется левая верхняя (северо-западная) клетка оставшейся части таблицы, причем максимально возможным числом: либо полностью выносится груз из Аi, либо полностью удовлетворяется потребность Вj. Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы аi и не удовлетворятся все потребности bj. В заключении проверяют, удовлетворяют ли найденные компоненты плана Хij горизонтальным и вертикальным уравнениям.

Метод наименьшего элемента

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

Метод потенциалов

Соотношения определяют систему из m+n-1 линейных уравнений с m+n известными, имеющую бесчисленное множество решений; для её определённости одному неизвестному присваивают произвольное значение (обычно альфа равное 0), тогда все остальные неизвестные определяются однозначно.

Критерий оптимальности

Если известны потенциалы решения Х0 транспортной задачи и для всех незаполненных ячеек выполняются условия αi+βj ≤ Cij, то Х0 является оптимальным планом транспортной задачи.

Если план не оптимален, то необходимо перейти к следующему плану (таблице) так, чтобы транспортные расходы не увеличивались.

Цикл перерасчёта таблицы – это последовательность ячеек, удовлетворяющая условиям:

• Одна ячейка пустая, все остальные занятые.
• Любые две соседние ячейки находятся в одной строке или в одном столбце.
• Никакие три соседние ячейки не могут быть в одной строке или в одном столбце.