Исследование математических операций 2 (стр. 9 из 28)
xr+1, xr+2 , ... , xn - свободные переменные.
; (2.40)
. (2.41)По последней системе ограничений и целевой функции Z построим табл. 2.3.
Таблица 2.3
Симплекс-таблица
Данная таблица называется симплекс-таблицей. Все дальнейшие преобразования связаны с изменением содержания этой таблицы.
Алгоритм симплекс-метода сводится к следующему.
1. В последней строке симплекс-таблицы находят наименьший положительный элемент, не считая свободного члена. Столбец, соответствующий этому элементу, считается разрешающим.
2. Вычисляют отношение свободных членов к положительным элементам разрешающего столбца (симплекс-отношение). Находят наименьшее из этих симплекс-отношений, оно соответствует разрешающей строке.
3. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.
4. Если имеется несколько одинаковых по величине симплекс-отношений, то выбирают любое из них. То же самое относится к положительным элементам последней строки симплекс-таблицы.
5. После нахождения разрешающего элемента переходят к следующей таблице. Неизвестные переменные, соответствующие разрешающей строке и столбцу, меняют местами. При этом базисная переменная становится свободной переменной и наоборот. Симплекс-таблица преобразована следующим образом (табл. 2.4):
6. Элемент табл. 2.4, соответствующий разрешающему элементу табл. 2.3, равен обратной величине разрешающего элемента.
7. Элементы строки табл. 2.4, соответствующие элементам разрешающей строки табл. 2.3, получаются путем деления соответствующих элементов табл. 2.3 на разрешающий элемент,
8. Элементы столбца табл. 2.4, соответствующие элементам разрешающего столбца табл. 2.3, получаются путем деления соответствующих элементов табл. 2.3 на разрешающий элемент и берутся с противоположным знаком.
9. Остальные элементы вычисляются по правилу прямоугольника: мысленно вычерчиваем прямоугольник в табл. 2.3, одна вершина которого совпадает с разрешающим элементом, а другая - с элементом, образ которого мы ищем; остальные две вершины определяются однозначно. Тогда искомый элемент из табл. 2.4 будет равен соответствующему элементу табл. 2.3 минус дробь, в знаменателе которой стоит разрешающий элемент, а в числителе - произведение элементов из двух неиспользованных вершин прямоугольника.
10. Как только получится таблица, в которой в последней строке все элементы отрицательны, считается, что минимум найден. Минимальное значение функции равно свободному члену в строке целевой функции, а оптимальное решение определяется свободными членами при базисных переменных. Все свободные переменные в этом случае равны нулю.
11. Если в разрешающем столбце все элементы отрицательны, то задача не имеет решений (минимум не достигается).
Таблица 2.4
Преобразование симплекс-таблицы
Пример 2.10. Решение задачи симплекс-методом:
;
.Приведем задачу к виду, допускающему применение симплекс-алгоритма:
Подставим в выражение Zmax величины x3, x4, x5:
.
По алгоритму целевая функция должна стремиться к минимуму:
.Составим симплекс-таблицу:
Разыскиваем в последней строке наименьший положительный элемент, в нашем примере он равен +6, первый столбец коэффициентов будет разрешающим. Определим отношение свободных членов к положительным элементам разрешающего столбца. Минимальное симплекс-отношение равно 1. Разрешающий элемент находится на пересечении строки переменной x4 и столбца - x1.
Переходим к следующей таблице, используя правило прямоугольника:
В последней строке нет положительных элементов, следовательно, оптимальное решение найдено: Zmin = -9; X = (1; 0; 2, 0, 1); Zmin = - Zmax = 9
Назад | Содержание | Далее
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
Построить математическую модель задачи линейного программирования (2.1 – 2.20).
Задача 2.1
Для сохранения нормальной жизнедеятельности человек должен в сутки потреблять белков не менее 120 условных единиц (усл. ед.), жиров – не менее 70 и витаминов – не менее 10 усл. ед. Содержание их в каждой единице продуктов П1 и П2 равно соответственно (0,2; 0,075; 0) и (0,1; 0,1; 0,1) усл. ед.
Стоимость 1 ед. продукта П1 – 2 руб., П2 –3 руб.
Постройте математическую модель задачи, позволяющую так организовать питание, чтобы его стоимость была минимальной, а организм получил необходимое количество питательных веществ.
Задача 2.2
Из пункта А в пункт В ежедневно отправляются пассажирские и скорые поезда. Данные об организации перевозок следующие:
| Поезда | Количество вагонов в поезде | ||||
| багажный | почтовый | плацкарт | купе | СВ | |
| скорый | 1 | 1 | 5 | 6 | 3 |
| пассажирский | 1 | - | 8 | 4 | 1 |
| число пассажиров | - | - | 58 | 40 | 32 |
| парк вагонов | 12 | 8 | 81 | 70 | 26 |
Сколько должно быть сформировано скорых и пассажирских поездов, чтобы перевезти наибольшее количество пассажиров?
Задача 2.3
Четыре овощехранилища каждый день обеспечивают картофелем три магазина. Магазины подали заявки соответственно на 17, 12 и 32 тонны. Овощехранилища имеют соответственно 20, 20 ,15 и 25 тонн. Тарифы (в д.е. за 1 тонну) указаны в следующей таблице:
| Овощехранилища | Магазины | ||
| 1 | 2 | 3 | |
| 1 | 2 | 7 | 4 |
| 2 | 3 | 2 | 1 |
| 3 | 5 | 6 | 2 |
| 4 | 3 | 4 | 7 |
Составьте план перевозок, минимизирующий суммарные транспортные расходы.
Задача 2.4
Имеются два склада готовой продукции: А1 и А2 с запасами однородного груза 200 и 300 тонн. Этот груз необходимо доставить трем потребителям В1, В2 и В3 в количестве 100, 150 и 250 тонн соответственно. Стоимость перевозки 1 тонны груза из склада А1 потребителям В1, В2 и В3 равна 5, 3 ,6 д.е., а из склада А2 тем же потребителям – 3, 4, 2 д.е. соответственно.
Составьте план перевозок, минимизирующий суммарные транспортные расход.
Задача 2.5
При откорме каждое животное должно получить не менее 9 ед. белков, 8 ед. углеводов и 11 ед. протеина. Для составления рациона используют два вида корма, представленных в следующей таблице.
| Питательные вещества | Количество единиц питательных веществ на 1 кг. | |
| корма 1 | корма 2 | |
| белки | 3 | 1 |
| углеводы | 1 | 2 |
| протеин | 1 | 6 |
Стоимость 1 кг корма первого вида – 4 д.е., второго – 6 д.е.
Составьте дневной рацион питательности, имеющий минимальную стоимость.
Задача 2.6
Хозяйство располагает следующими ресурсами: площадь – 100 ед., труд – 120 ед., тяга – 80 ед. Хозяйство производит четыре вида продукции: П1 , П2, П3 и П4. Организация производства характеризуется следующей таблицей:
| продукция | Затраты на 1 ед. продукции | Доход от единицы продукции | ||
| площадь | труд | тяга | ||
| П1 | 2 | 2 | 2 | 1 |
| П2 | 3 | 1 | 3 | 4 |
| П3 | 4 | 2 | 1 | 3 |
| П4 | 5 | 4 | 1 | 5 |
Составьте план выпуска продукции, обеспечивающий хозяйству максимальную прибыль.