Методические рекомендации к практическим занятиям по дисциплине «Математическое и имитационное моделирование» для студентов специальности «Прикладная информатика (в менеджменте)» (стр. 3 )

Задача 8. Цех выпускает трансформаторы двух видов. Для изготовления трансформаторов обоих видов используются железо и проволока. Общий запас железа - 3 т, проволоки - 18 т. На один трансформатор первого вида расходуются 5 кг железа и 3 кг проволоки, а на один трансформатор второго вида расходуются 3 кг железа и 2 кг проволоки. За каждый реализованный трансформатор первого вида завод получает прибыль 3 д. е., второго - 4 д. е.

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

Задача 9. Обработка деталей А и В может производиться на трех станках, причем каждая деталь должна последовательно обрабатываться на каждом из станков. Прибыль от реализации детали А - 100 руб., детали В - 160 руб. Исходные данные приведены в табл. 7.

Таблица 7

Станки	Норма времени на обработку одной детали, ч	Время работы станка, ч
А	В
1	0,2	0,1	100
2	0,2	0,5	180
3	0,1	0,2	100

Определить производственную программу, максимизирующую прибыль при условии: спрос на деталь А - не менее 300 шт., на деталь В - не более 200 шт.

Практическое занятие «Решение задач линейного программирования симплекс-методом»

Цели занятия: научиться использовать симплекс-метод для нахождения оптимального решения задач линейного программирования.

Линейное программирование (симплекс-метод)

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

Симплексный метод состоит из трех основных элементов:

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

Алгоритм симплекс-метода:

Для определенности считаем, что решается задача на отыскание максимума, если необходимо отыскать минимум F, то решается задача максимизации функции –F, и это решение принимается за решение исходной задачи.

1) После введения добавочных переменных систему уравнений и линейную функцию записываем в виде, который называется расширенной системой:

Предполагаем, что все добавочные переменные имеют тот же знак, что и свободные члены.

2) Для нахождения первоначального базисного решения разобьем переменные на две группы: основные (базисные) и неосновные (свободные). В качестве основных переменных на первом шаге следует выбрать (если это возможно) такие т переменных, каждая из которых входит только в одно из т уравнений системы ограничений. При этом нет таких уравнений системы, в которые не входит ни одна из этих переменных.

Базисные неизвестные - хп+1, хn+2,..., xn+m

Cвободные неизвестные - х1,х2, ...,хп

3) По расширенной системе строим симплекс-таблицу

Базисные неизвестные	Свободный член	Неизвестные	Оценочное отношение
x1	x2	…	xn	xn+1	…	xn+m
xn+1	b1	a11	a12	…	a1n	1	…	0
…	…	…	…	…	…	…	…	…
xn+m	bm	am1	am2	…	amn	0	…	1
F	0	c1	c2	…	cn	0	0	0

4) Проверяем критерий оптимальности при решении задач на максимум. Если в последней строке F симплекс-таблице нет отрицательных коэффициентов, то решение оптимально. Максимальное значение функции равно свободному члену в строке целевой функции (строке F), а оптимальное решение определяется свободными членами при базисных переменных. Все свободные переменные в этом случае равны нулю.

5) Если критерий оптимальности не выполнен, то в последней строке симплекс-таблицы находим наименьший отрицательный элемент, не считая свободного члена. Столбец, соответствующий этому элементу, считается разрешающим. Если имеется несколько одинаковых наименьших элементов, то выбираем любой из них.

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

Если в разрешающем столбце все коэффициенты меньше или равны 0, то решение задачи бесконечно.

7) На пересечении разрешающей строки и разрешающего столбца находим разрешающий элемент. Если имеется несколько одинаковых по величине оценочных отношений, то выбирают любое из них.

8) После нахождения разрешающего элемента переходим к следующей таблице. Неизвестные переменные, соответствующие разрешающей строке и столбцу, меняем местами. При этом базисная переменная становится свободной переменной, и наоборот. Симплекс-таблицу преобразуем следующим образом:

Все элементы разрешающей строки делим на разрешающий элемент. Полученную строку обозначаем *. Вычисление элементов остальных строк, включая F-строку.

Новая строка = текущая строка – её коэффициент в разрешающем столбце ×строку *

9) См. п4.

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

Решение. Расширенная система задачи имеет вид:

Базисные неизвестные – х3, х4, х5, х6. Свободные неизвестные – х1,х2. Заполняем первую симплекс-таблицу.

Базисные неизвестные	Свободный член	Неизвестные	Оценочное отношение
x1	x2	x3	x4	x5	x6
№1	x3	18	1	3	1	0	0	0	18/3
№2	x4	16	2	1	0	1	0	0	16
№3	x5	5	0	1	0	0	1	0	5
№4	x6	21	3	0	0	0	0	1	-
№5	F	0	-2	-3	0	0	0	0

Проверяем критерий оптимальности. В последней строке имеется отрицательные коэффициенты. Выбираем из наименьший (-3); второй столбец разрешающий, переменная х2 перейдет в базисные переменные.

Находим оценочные отношения. Третья строка является разрешающей. На пересечении разрешающих строки и столбца стоит разрешающий элемент (1).

Строим таблицу №2

Новые базисные неизвестные – х3, х4, х2, x6. Свободные неизвестные – х1, х5.

Коэффициенты таблицы №2 вычисляем следующим образом:

Новая строка №3 = строка №3/1 – обозначим результат *

Новая строка №1 = строка №1 - 3×строка *,

Новая строка №2 = строка №2 - 1×строка *,

Новая строка №4 = строка №4 - 0×строка *,

Новая строка №5 = строка №5 - (-3)×строка *,

Новая симплекс-таблица, соответствующая новому базису, имеет следующий вид.

Базисные неизвестные	Свободный член	Неизвестные	Оценочное отношение
x1	x2	x3	x4	x5	x6
x3	3	1	0	1	0	-3	0	3
x4	11	2	0	0	1	-1	0	11/20
x5	5	0	1	0	0	1	0	-
x6	21	3	0	0	0	0	1	7
F	15	-2	0	0	0	3	0

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

Базисные неизвестные	Свободный член	Неизвестные	Оценочное отношение
x1	x2	x3	x4	x5	x6
x3	3	1	0	1	0	-3	0	-
x4	5	0	0	-2	1	5	0	5/5
x5	5	0	1	0	0	1	0	5
x6	12	0	-3	0	9	1	12/9
F	21	0	0	2	0	-3	0

Базисные неизвестные	Свободный член	Неизвестные	Оценочное отношение
x1	x2	x3	x4	x5	x6
x3	6	1	0	-1/5	3/5	0	0
x4	1	0	0	-2/5	1/5	1	0
x5	4	0	1	2/5	-1/5	0	0
x6	3	0	0	3/5	-9/5	0	1
F	24	0	0	4/5	3/5	0	0

Критерий оптимальности последней таблицы выполнен, значит