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

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ РФ

 

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ  УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ

 

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕХНОЛОГИЙ И УПРАВЛЕНИЯ ИМЕНИ К. Г. РАЗУМОВСКОГО»

 

Филиал ФГБОУ  ВПО «МГУТУ имени К. Г. Разумовского»  в г. Омске

 

Кафедра экономических наук

 

 

 

 

КОНТРОЛЬНАЯ РАБОТА

 

по дисциплине: Принятие решений

тема:   Вариант №2

выполнил (а): Демидов Михаил Владимирович

факультет: ФЭУ

направление подготовки: дистанционно        группа:  ДО 541-09К

     шифр: К-409062С

консультировал (а):  ________________________________________________

подпись преподавателя, принявшего  работу:___________________________

 

 

 

 

 

 

Омск-2013г.

Содержание 

 

1. Симплексный метод решения задачи линейного 

программирования. Постановка задачи…………………………………………….3

2. Транспортная задача. Альтернативный оптимум в ТЗ………………..7

Список литературы

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Симплексный метод решения задачи линейного программирования. Постановка задачи.

 

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

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

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

Таблица 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.

Таблица 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 (свободного столбца), то значит, что оптимальное решение получено. В противном случае, переходим к новой симплекс таблице по выше описанному алгоритму.

 

 

 

 

 

2. Транспортная задача. Альтернативный оптимум в ТЗ.

 

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

В общем виде задачу можно представить  следующим образом: в т. пунктах производства A₁, A₂, ..., A_m имеется однородный груз в количестве соответственно a₁, a₂,…, a_m. Этот груз необходимо доставить в п пунктов назначения B₁, В₂, …., В_п в количестве соответственно b₁, b₂,..., b_п. Стоимость перевозки единицы груза (тариф) из пункта A_i в пункт B_j равна c_ij.

Требуется составить план перевозок, позволяющий вывезти все грузы и имеющий минимальную стоимость.

В зависимости от соотношения между  суммарными запасами груза и суммарными потребностями в нем транспортные задачи могут быть закрытыми и открытыми.

 

Определение 1. Если

то задача называется закрытой. Если

то открытой.

Обозначим через x_ij количество груза, перевозимого из пункта A_i в пункт B_j. Рассмотрим закрытую транспортную задачу.

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

при ограничениях:

Оптимальным решением задачи является матрица

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

— нахождение исходного опорного решения;

— проверка этого решения на оптимальность;

• переход от одного опорного решения к другому.

Признаком наличия альтернативного  оптимума в транспортной задаче является равенство нулю хотя бы одной из оценок свободных переменных в оптимальном решении (X_опт1).Сделав перераспределение грузов относительно клетки, имеющей Δ_ij = 0, получим новое оптимальное решение (Х_опт2), при этом значение целевой функции (транспортных расходов) не изменится. Если одна оценка свободных переменных равна нулю, то оптимальное решение находится в виде

где 0 ≤ t ≤ 1.

Рассмотрим конкретную задачу, имеющую  альтернативный оптимум.

Пример На трех складах имеется сахар в количестве 60, 130 и 90 т, который должен быть в течение месяца доставлен четырем заводам в количестве: 30, 80, 60, 110 т соответственно.

Составить оптимальный план перевозок, имеющий минимальные транспортные расходы, если стоимость доставки 1 т сахара на заводы задана матрицей

Решение. Составим распределительную таблицу в виде табл. 3

Таблица 3

bi ai		1	2	3	4	ui
		30	80	60	110
1	60	6 20	8	15	4 40	0
2	130	9	15	2 60	3 70	-1
3	90	6 10	12 80	7	10	0
vi		6	12	3	4

 

По методу минимального тарифа найдем исходное решение. Определим потенциалы строк и столбцов. Найдем оценки свободных клеток:

Так как Δ₁₂ = 4 > 0, то перераспределим грузы относительно клетки (1,2):

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

Таблица 4

bi ai		1	2	3	4	ui
		30	80	60	110
1	60	6	8 20	15	4 40	0
2	130	9	15	2 60	3 70	-1
3	90	6 30	12 60	7	10	0
vi		6	12	3	4