ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 04.12.2023
Просмотров: 45
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Итерация №1.
1. Проверка критерия оптимальности.
Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (2125 : 0.5 , 427.5 : 0.25 , - , 575 : 0.3 ) = 1710
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (0.25) и находится на пересечении ведущего столбца и ведущей строки.
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | min |
| x2 | 2125 | 0.5 | 1 | 1.5 | 2.5 | 0 | 0 | 0 | 4250 |
| x5 | 427.5 | 0.25 | 0 | -0.05 | -0.25 | 1 | 0 | 0 | 1710 |
| x6 | 92.5 | -0.05 | 0 | -0.35 | -0.75 | 0 | 1 | 0 | - |
| x7 | 575 | 0.3 | 0 | -0.1 | -0.5 | 0 | 0 | 1 | 1916.67 |
| F(X2) | 318750 | -45 | 0 | 115 | 375 | 0 | 0 | 0 | |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x5 в план 2 войдет переменная x1.
Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x5 плана 1 на разрешающий элемент РЭ=0.25. На месте разрешающего элемента получаем 1. В остальных клетках столбца x1 записываем нули.
Таким образом, в новом плане 2 заполнены строка x1 и столбец x1. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
| B | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| 2125 | 0.5 | 1 | 1.5 | 2.5 | 0 | 0 | 0 |
| 427.5 | 0.25 | 0 | -0.05 | -0.25 | 1 | 0 | 0 |
| 92.5 | -0.05 | 0 | -0.35 | -0.75 | 0 | 1 | 0 |
| 575 | 0.3 | 0 | -0.1 | -0.5 | 0 | 0 | 1 |
| 318750 | -45 | 0 | 115 | 375 | 0 | 0 | 0 |
Получаем новую симплекс-таблицу:
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| x2 | 1270 | 0 | 1 | 1.6 | 3 | -2 | 0 | 0 |
| x1 | 1710 | 1 | 0 | -0.2 | -1 | 4 | 0 | 0 |
| x6 | 178 | 0 | 0 | -0.36 | -0.8 | 0.2 | 1 | 0 |
| x7 | 62 | 0 | 0 | -0.04 | -0.2 | -1.2 | 0 | 1 |
| F(X2) | 395700 | 0 | 0 | 106 | 330 | 180 | 0 | 0 |
1. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| x2 | 1270 | 0 | 1 | 1.6 | 3 | -2 | 0 | 0 |
| x1 | 1710 | 1 | 0 | -0.2 | -1 | 4 | 0 | 0 |
| x6 | 178 | 0 | 0 | -0.36 | -0.8 | 0.2 | 1 | 0 |
| x7 | 62 | 0 | 0 | -0.04 | -0.2 | -1.2 | 0 | 1 |
| F(X3) | 395700 | 0 | 0 | 106 | 330 | 180 | 0 | 0 |
Оптимальный план можно записать так:
x1 = 1710, x2 = 1270, x3 = 0
F(X) = 120*1710 + 150*1270 + 110*0 = 395700
Анализ оптимального плана.
В оптимальный план вошла дополнительная переменная x6. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 3-го вида в количестве 178.
В оптимальный план вошла дополнительная переменная x7. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 4-го вида в количестве 62.
Значение 0 в столбце x1 означает, что использование x1 - выгодно.
Значение 0 в столбце x2 означает, что использование x2 - выгодно.
Значение 106> 0 в столбце x3 означает, что использование x3 - не выгодно.
Значение 330 в столбце x4 означает, что теневая цена (двойственная оценка) равна y1=330.
Значение 180 в столбце x5 означает, что теневая цена (двойственная оценка) равна y2=180.
Значение 0 в столбце x6 означает, что теневая цена (двойственная оценка) равна y3=0.
Значение 0 в столбце x7 означает, что теневая цена (двойственная оценка) равна y4=0.
Ответ: максимальная прибыль 395700 при производстве 1710 единиц Продукта 1 и 1270 единиц Продукта 2
№ 2. Распределить план перевозок однотипного груза от трёх поставщиков к четырём потребителям, обеспечив минимальные затраты на перевозку.
Исходные данные представлены в таблице 2.
Таблица 2. Транспортная задача.
| | Тарифы по перемещению единицы груза, тыс. руб. | ||||
| | Потребитель1 | Потребитель2 | Потребитель2 | Потребитель4 | Возможности поставщика |
| Поставщик1 | 7 | 4 | 9 | 3 | 400 |
| Поставщик2 | 2 | 11 | 8 | 4 | 550 |
| Поставщик 3 | 3 | 8 | 6 | 5 | 300 |
| Потребности потребителя | 450 | 250 | 200 | 350 | |
Математическая модель транспортной задачи:
F = ∑∑cijxij, (1)
при условиях:
∑xij = ai, i = 1,2,…, m, (2)
∑xij = bj, j = 1,2,…, n, (3)
xij ≥ 0
Запишем экономико-математическую модель для нашей задачи.
Переменные:
x11 – количество груза из 1-го поставщика к 1-у потребителю.
x12 – количество груза из 1-го поставщика к 2-у потребителю.
x13 – количество груза из 1-го поставщика к 3-у потребителю.
x14 – количество груза из 1-го поставщика к 4-у потребителю.
x21 – количество груза из 2-го поставщика к 1-у потребителю.
x22 – количество груза из 2-го поставщика к 2-у потребителю.
x23 – количество груза из 2-го поставщика к 3-у потребителю.
x24 – количество груза из 2-го поставщика к 4-у потребителю.
x31 – количество груза из 3-го поставщика к 1-у потребителю.
x32 – количество груза из 3-го поставщика к 2-у потребителю.
x33 – количество груза из 3-го поставщика к 3-у потребителю.
x34 – количество груза из 3-го поставщика к 4-у потребителю.
Ограничения по запасам:
x11 + x12 + x13 + x14 ≤ 400 (для 1 базы)
x21 + x22 + x23 + x24 ≤ 550 (для 2 базы)
x31 + x32 + x33 + x34 ≤ 300 (для 3 базы)
Ограничения по потребностям:
x11 + x21 + x31 = 450 (для 1-го потребителя.)
x12 + x22 + x32 = 250 (для 2-го потребителя.)
x13 + x23 + x33 = 200 (для 3-го потребителя.)
x14 + x24 + x34 = 350 (для 4-го потребителя.)
Целевая функция:
7x11 + 4x12 + 9x13 + 3x14 + 2x21 + 11x22 + 8x23 + 4x24 + 3x31 + 8x32 + 6x33 + 5x34 → min
С целью составления двойственной задачи переменные xij в условии