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

Работа добавлена на сайт bukvasha.net: 2015-07-01

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Имя

Выберите тип работы:

Принимаю Политику конфиденциальности

Скидка 25% при заказе до 24.11.2024

Задача №1 (Симплекс метод решения задачи линейного программирования.)

Найти F_max = 9x₁+ 10x₂ + 16x_3, при ограничениях:

Запишем задачу в каноническом виде:

F=9x₁+ 10x₂ + 16x₃→ max

Заполним начальную таблицу:

Таблица 0.

			0	9	10	16	0	0	0	Отношение, θ
i		Базис
1	0		360	18	15	12	1	0	0	30
2	0		192	6	4	8	0	1	0	24
3	0		180	5	3	3	0	0	1	60
	∆j		0	-9	-10	-16	0	0	0
	Zj		0	0	0	0	0	0	0

Zj вычисляется по формуле

Оценки (∆j) вычисляются по формуле , где - коэффициент из первой строки таблицы.

Выбираем минимальную (отрицательную) оценку. Она определяет направляющий столбец.

Заполняем столбец «θ», по минимальному значению определяем направляющую строку.

На пересечение строки и столбца находится направляющий элемент.

Заполняем новую таблицу

Таблица 1.

			0	9	10	16	0	0	0	Отношение, θ
i		Базис
1	0		72	9	9	0	1		0	8
2	16		24			1	0		0

108

∆j

384

-2

384

Изменяется базис в позиции направляющей строки. Базисным становится вектор, соответствующий направляющему столбцу, т. е.

Столбец становится базисным, то есть единичным.

Новые значения в направляющей строке получаем делением элементов этой строки на направляющий элемент.

Остальные элементы в небазисных столбцах и в столбце вычисляем по правилу треугольника.

Выбираем минимальную отрицательную оценку. Она определяет направляющий столбец.

Заполняем столбец «θ»

По минимальному значению определяем направляющую строку.

На пересечении направляющей строки и столбца находится направляющий элемент.

Заполнение второй таблицы осуществляется по аналогии с предыдущей.

Таблица 2.

			0	9	10	16	0	0	0	Отношение, θ
i		Базис
1	10		8	1	1	0		-	0	______
2	16		20		0	1	-		0	______
3	0		96		0	0		-	1	______
	∆j		400	5	0	0			0
	Zj		400	14	10	16			0

Так как нет отрицательных оценок ∆j, значит выполняется признак оптимальности и не вводились искусственные переменные, то получено оптимальное решение.

Ответ:

Максимальное значение функции F_max =400 достигается в точке с координатами:

=20

=96

Задача №2 (Метод Литтла)

Найти кратчайший путь в графе, заданном графически в виде чертежа, методом Литтла.

Из чертежа запишем матрицу расстояний. (Расстояние от т.1 до т.2 равно:

, и т.д.)

∞

18,87

	49,48	51,86	80,51	97,42
2	18,87	∞	32,06	34,48	65,15	84,01
3	49,48	32,06	∞	31,76	61,19	83,20
4	51,86	34,48	31,76	∞	32,14	53,15
5	80,51	65,15	61,19	32,14	∞	22,14
6	97,42	84,01	83,20	53,15	22,14	∞

Предположим что кратчайший путь будет следующим:

т.1→ т.2→ т.3→ т.4→ т.5→ т.6→т.1 и составит

Решение: Первый этап.

Шаг 1. Приведем матрицу расстояний по строкам и столбцам

(в строке вычитаем из каждого элемента минимальный, затем в столбцах)

	1	2	3	4	5	6
1	∞	18,87	49,48	51,86	80,51	97,42	18,87
2	18,87	∞	32,06	34,48	65,15	84,01	18,87
3	49,48	32,06	∞	31,76	61,19	83,20	31,76
4	51,86	34,48	31,76	∞	32,14	53,15	31,76
5	80,51	65,15	61,19	32,14	∞	22,14	22,14
6	97,42	84,01	83,20	53,15	22,14	∞	22,14

↓

	1	2	3	4	5	6
1	∞	0	30,61	32,99	61,64	78,55
2	0	∞	13,19	15,61	46,28	65,14
3	17,72	0,30	∞	0	29,43	51,44
4	20,10	2,72	0	∞	0,38	21,39
5	58,37	43,01	39,05	10,00	∞	0
6	75,28	61,87	61,06	31,01	0	∞
	0	0	0	0	0	0

↓

	1	2	3	4	5	6
1	∞	0	30,61	32,99	61,64	78,55
2	0	∞	13,19	15,61	46,28	65,14
3	17,72	0,30	∞	0	29,43	51,44
4	20,10	2,72	0	∞	0,38	21,39
5	58,37	43,01	39,05	10,00	∞	0
6	75,28	61,87	61,06	31,01	0	∞

Шаг 2. Определим оценки нулевых клеток:

Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (5 – 6)

Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 6-5 ставим ∞).

	1	2	3	4	5
1	∞	0	30,61	32,99	61,64
2	0	∞	13,19	15,61	46,28
3	17,72	0,30	∞	0	29,43
4	20,10	2,72	0	∞	0,38
6	75,28	61,87	61,06	31,01	∞

Далее повторяем шаги 1 – 4, пока не дойдем до одной клетки.

Второй этап.

Шаг 1. Приведем матрицу расстояний по строкам и столбцам.

	1	2	3	4	5
1	∞	0	30,61	32,99	61,64
2	0	∞	13,19	15,61	46,28
3	17,72	0,30	∞	0	29,43
4	20,10	2,72	0	∞	0,38
6	75,28	61,87	61,06	31,01	∞
	0	0	0	0	0,38

↓

	1	2	3	4	5
1	∞	0	30,61	32,99	61,26
2	0	∞	13,19	15,61	45,90
3	17,72	0,30	∞	0	29,05
4	20,10	2,72	0	∞	0
6	75,28	61,87	61,06	31,01	∞

Шаг 2. Определим оценки нулевых клеток:

Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (1 – 2)

Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 2 – 1 ставим ∞).

	1	3	4	5
2	∞	13,19	15,61	45,90
3	17,72	∞	0	29,05
4	20,10	0	∞	0
6	75,28	61,06	31,01	∞

Третий этап.

Шаг 1. Приведем матрицу расстояний по строкам и столбцам.

	1	3	4	5
2	∞	13,19	15,61	45,90
3	17,72	∞	0	29,05
4	20,10	0	∞	0
6	75,28	61,06	31,01	∞
	17,72	0	0	0

↓

	1	3	4	5
2	∞	13,19	15,61	45,90	13,19
3	0	∞	0	29,05	0
4	2,38	0

	∞	0	0
6	57,56	61,06	31,01	∞	31,01

↓

	1	3	4	5
2	∞	0	2,42	32,71
3	0	∞	0	29,05
4	2,38	0	∞	0
6	26,55	30,05	0	∞

Шаг 2. Определим оценки нулевых клеток:

Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (4 – 5)

Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 6 – 4 ставим ∞).

	1	3	4
2	∞	0	2,42
3	0	∞	0
6	26,55	30,05	∞

Четвертый этап.

Шаг 1. Приведем матрицу расстояний по строкам и столбцам.

	1	3	4
2	∞	0	2,42	0
3	0	∞	0	0
6	26,55	30,05	∞	26,55

↓

	1	3	4
2	∞	0	2,42
3	0	∞	0
6	0	3,50	∞

Шаг 2. Определим оценки нулевых клеток:

Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (3 – 4)

Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 6 – 3 ставим ∞).

	1	3
2	∞	0
6	0	∞

Пятый этап.

Остались не задействованными связи 2 – 3 и 6 – 1.

В результате получаем следующую цепочку:

1→ 2→ 3 → 4→ 5→ 6 →1

Длина пути составляет:

L=18,87+32,06+31,76+32,14+22,14+97,42=234,39

это и есть кратчайший путь.

1. Реферат на тему Фондовые биржи
2. Реферат Ответственность за нарушение законодательства Российской Федерации о труде и об охране труда
3. Реферат Кесарево сечение мелких домашних животных
4. Диплом Финансовое состояние предприятия и разработка стратегии по его улучшению на примере ООО Росагросервис
5. Реферат на тему Gender And Sexuality Essay Research Paper SBS
6. Доклад на тему Вестибулярный аппарат Укачивание
7. Курсовая Автоматизированная система управления менеджментом и маркетингом коммерческого банка
8. Методичка на тему Створення бізнесмоделі підприємства за допомогою компютерного комплексу Project Expert
9. Курсовая на тему Разработка системы измерения давления
10. Курсовая Основные средства предприятия и эффективность их использования 2