ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 06.12.2023
Просмотров: 27
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Переходим к основному алгоритму симплекс-метода.
Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| x4 | 850 | 1/5 | 2/5 | 3/5 | 1 | 0 | 0 | 0 |
| x5 | 640 | 3/10 | 1/10 | 1/10 | 0 | 1 | 0 | 0 |
| x6 | 730 | 1/10 | 3/10 | 1/10 | 0 | 0 | 1 | 0 |
| x7 | 1000 | 2/5 | 1/5 | 1/5 | 0 | 0 | 0 | 1 |
| F(X1) | 0 | 696/5 | 1401/10 | 1397/10 | 0 | 0 | 0 | 0 |
Оптимальный план можно записать так:
x1 = 0, x2 = 0, x3 = 0, x4 = 850, x5
= 640, x6 = 730, x7 = 1000
F(X) = -1391/5*0 -1401/10*0 -1397/10*0 + 450940 = 450940
№ 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(X) = 12x1+23x2+23x3+12 → min при ограничениях:
7x1+2x2+3x3≤450
4x1+11x2+8x3≤250
9x1+8x2+6x3≤200
3x1+4x2+5x3≤350
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
Для приведения ЗЛП к канонической форме необходимо:
1. Поменять знак у целевой функции.
Сведем задачу F(X) → min к задаче F(X) → max. Для этого умножаем F(X) на (-1).
F(X) = -12x1-23x2-23x3+12
В 1-м неравенстве смысла (≤) вводим базисную переменную x4. В 2-м неравенстве смысла (≤) вводим базисную переменную x5. В 3-м неравенстве смысла (≤) вводим базисную переменную x6. В 4-м неравенстве смысла (≤) вводим базисную переменную x7.
7x1+2x2+3x3+x4 = 450
4x1+11x2+8x3+x5 = 250
9x1+8x2+6x3+x6 = 200
3x1+4x2+5x3+x7 = 350
Целевая функция для решения задачи на min:
F(X) = 12x1+23x2+23x3-12x4-12x5-12x6-12x7+12 → min
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:
| 7 | 2 | 3 | 1 | 0 | 0 | 0 | 450 |
| 4 | 11 | 8 | 0 | 1 | 0 | 0 | 250 |
| 9 | 8 | 6 | 0 | 0 | 1 | 0 | 200 |
| 3 | 4 | 5 | 0 | 0 | 0 | 1 | 350 |
1. В качестве базовой переменной можно выбрать x4.
2. В качестве базовой переменной можно выбрать x5.
3. В качестве базовой переменной можно выбрать x6.
4. В качестве базовой переменной можно выбрать x7.
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (4,5,6,7).
Соответствующие уравнения имеют вид:
7x1+2x2+3x3+x4 = 450
4x1+11x2+8x3+x5 = 250
9x1+8x2+6x3+x6 = 200
3x1+4x2+5x3+x7 = 350
Выразим базисные переменные через остальные:
x4 = -7x1-2x2-3x3+450
x5 = -4x1-11x2-8x3+250
x6 = -9x1-8x2-6x3+200
x7 = -3x1-4x2-5x3+350
Подставим их в целевую функцию:
F(X) = 12x1+23x2+23x3-12(-7x1-2x2-3x3+450)-12(-4x1-11x2-8x3+250)-12(-9x1-8x2-6x3+200)-12(-3x1-4x2-5x3+350)+12
или
F(X) = 288x1+323x2+287x3-14988 → min
Система неравенств:
-7x1-2x2-3x3+450 ≥ 0
-4x1-11x2-8x3+250 ≥ 0
-9x1-8x2-6x3+200 ≥ 0
-3x1-4x2-5x3+350 ≥ 0
Приводим систему неравенств к следующему виду:
7x1+2x2+3x3 ≤ 450
4x1+11x2+8x3 ≤ 250
9x1+8x2+6x3 ≤ 200
3x1+4x2+5x3 ≤ 350
F(X) = 288x1+323x2+287x3-14988 → min
Упростим систему.
7x1+2x2+3x3 ≤ 450
4x1+11x2+8x3 ≤ 250
9x1+8x2+6x3 ≤ 200
3x1+4x2+5x3 ≤ 350
F(X) = 288x1+323x2+287x3-14988 → min
Если задача ЛП решается на поиск max-го значения, то стандартная форма будет иметь следующий вид:
-7x1-2x2-3x3 ≤ -450
-4x1-11x2-8x3 ≤ -250
-9x1-8x2-6x3 ≤ -200
-3x1-4x2-5x3 ≤ -350
F(X) = -288x1-323x2-287x3+14988 → max
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим минимальное значение целевой функции F(X) = 288x1+323x2+287x3-14988 при следующих условиях-ограничений.
При вычислениях значение Fc = -14988 временно не учитываем.
7x1+2x2+3x3+x4+450=450
4x1+11x2+8x3+x5+250=250
9x1+8x2+6x3+x6+200=200
3x1+4x2+5x3+x7+350=350
Расширенная матрица системы ограничений-равенств данной задачи:
| 7 | 2 | 3 | 1 | 0 | 0 | 0 | 450 |
| 4 | 11 | 8 | 0 | 1 | 0 | 0 | 250 |
| 9 | 8 | 6 | 0 | 0 | 1 | 0 | 200 |
| 3 | 4 | 5 | 0 | 0 | 0 | 1 | 350 |
1. В качестве базовой переменной можно выбрать x4.
2. В качестве базовой переменной можно выбрать x5.
3. В качестве базовой переменной можно выбрать x6.
4. В качестве базовой переменной можно выбрать x7.
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (4,5,6,7).
Выразим базисные переменные через остальные:
x4 = -7x1-2x2-3x3+450
x5 = -4x1-11x2-8x3+250
x6 = -9x1-8x2-6x3+200
x7 = -3x1-4x2-5x3+350
Подставим их в целевую функцию:
F(X) = 288x1+323x2+287x3-14988
7x1+2x2+3x3+x4=450
4x1+11x2+8x3+x5=250
9x1+8x2+6x3+x6=200
3x1+4x2+5x3+x7=350
При вычислениях значение Fc = -14988 временно не учитываем.
Решим систему уравнений относительно базисных переменных: x4, x5, x6, x7
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,0,0,450,250,200,350)
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| x4 | 450 | 7 | 2 | 3 | 1 | 0 | 0 | 0 |
| x5 | 250 | 4 | 11 | 8 | 0 | 1 | 0 | 0 |
| x6 | 200 | 9 | 8 | 6 | 0 | 0 | 1 | 0 |
| x7 | 350 | 3 | 4 | 5 | 0 | 0 | 0 | 1 |
| F(X0) | 0 | -288 | -323 | -287 | 0 | 0 | 0 | 0 |
Переходим к основному алгоритму симплекс-метода.
Конец итераций: индексная строка не содержит положительных элементов - найден оптимальный план
Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| x4 | 450 | 7 | 2 | 3 | 1 | 0 | 0 | 0 |
| x5 | 250 | 4 | 11 | 8 | 0 | 1 | 0 | 0 |
| x6 | 200 | 9 | 8 | 6 | 0 | 0 | 1 | 0 |
| x7 | 350 | 3 | 4 | 5 | 0 | 0 | 0 | 1 |
| F(X1) | 0 | -288 | -323 | -287 | 0 | 0 | 0 | 0 |
Оптимальный план можно записать так:
x1 = 0, x2 = 0, x3 = 0, x4 = 450, x5 = 250, x6 = 200, x7 = 350
F(X) = 288*0 + 323*0 + 287*0 -14988 = -14988