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

Задача №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	48
3	0		108			0	0	-	1	72
∆j		384	3	-2	0	0	2	0
Zj		384	12	8	0	0	2	0

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

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

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

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

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

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

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

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

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

Таблица 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 равно:

, и т.д.)

1	2	3	4	5	6
1	∞	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

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

Не сдавайте скачаную работу преподавателю!

Данную контрольную работу Вы можете использовать для выполнения своих заданий.

Доработать Узнать цену работы по вашей теме

Поделись с друзьями, за репост + 100 мильонов к студенческой карме :

Заказать работу:

!	Курсовая работа
!	Дипломная работа
!	Реферат
!	Решение задач
!	Отчет по практике
!	Контрольная работа

Другие популярные контрольные работы:

Контрольная работа	Концепция информатизации Российской Федерации
Контрольная работа	Причины агрессивного поведения. Методы работы с агрессивными детьми
Контрольная работа	Алгоритм выбора и реализации предпринимательской идеи
Контрольная работа	Современные методы арт-терапии
Контрольная работа	Системы управления взаимоотношения с клиентами
Контрольная работа	Учет материальных затрат в бухгалтерском учете
Контрольная работа	Геополитическое положение России
Контрольная работа	Особенности вознаграждения работников в организации
Контрольная работа	Виды запасов
Контрольная работа	Психоанализ

Сейчас смотрят :

Контрольная работа	Этикет делового телефонного разговора
Контрольная работа	Коммуникационные барьеры
Контрольная работа	Пути повышения эффективности логистических систем на промышленных предприятиях
Контрольная работа	Шифраторы, дешифраторы, триггеры
Контрольная работа	Полномочия органов местного самоуправления в области земельных отношений

Контрольная работа по предмету "Информатика, программирование"

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

Другие популярные контрольные работы:

Сейчас смотрят :