Как решать задачи на симплекс-метод?

Ответ: Для решения используем этот сервис. Задание. Для изготовления различных изделий А, и В предприятие использует три различных вида сырья. Нормы расхода сырья на производство одного изделия каждого вида, цена одного изделия А и В, а также общее количество сырья каждого вида, которое может быть использовано предприятием, приведены в табл.

Решение. br>
Решим прямую задачу линейного программирования симплекс-методом..
Определим максимальное значение целевой функции F(X) = 40x1 + 30x2 при следующих условиях-ограничений.
x1 + 3x2<=300
3x1 + 4x2<=477
4x1 + x2<=441
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (<=) вводим базисную переменную x3. В 2-м неравенстве смысла (<=) вводим базисную переменную x4. В 3-м неравенстве смысла (<=) вводим базисную переменную x5.
1x1 + 3x2 + 1x3 + 0x4 + 0x5 = 300
3x1 + 4x2 + 0x3 + 1x4 + 0x5 = 477
4x1 + 1x2 + 0x3 + 0x4 + 1x5 = 441
Введем новую переменную x0 = 40x1 + 30x2.
Выразим базисные переменные <3, 4, 5> через небазисные.
x0 = 0+40x1+30x2
x3 = 300-x1-3x2
x4 = 477-3x1-4x2
x5 = 441-4x1-x2
Переходим к основному алгоритму симплекс-метода.
Поскольку задача решается на максимум, то переменную для включения в текущий план выбирают по максимальному положительному числу в уравнении для x0.
1. Проверка критерия оптимальности.
В выражении для x0 присутствуют отрицательные элементы. Следовательно, текущий план неоптимален
2. Определение новой базисной переменной.
max(40,30,0,0,0) = 40
x0 = 0+40x1+30x2
x3 = 300-x1-3x2
x4 = 477-3x1-4x2
x5 = 441-4x1-x2
В качестве новой переменной выбираем x1.
3. Определение новой свободной переменной.
Вычислим значения Di по всем уравнениям для этой переменной: bi / ai1
и из них выберем наименьшее:
min (300 : 1 , 477 : 3 , 441 : 4 ) = 1101/4
Вместо переменной x5 в план войдет переменная x1.
4. Пересчет всех уравнений.
Выразим переменную x1 через x5
x1 = 441/4-1/4x2-1/4x5
и подставим во все выражения.
x0 = 0+40(441/4-1/4x2-1/4x5)+30x2
x3 = 300-(441/4-1/4x2-1/4x5)-3x2
x4 = 477-3(441/4-1/4x2-1/4x5)-4x2
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = 4410+20x2-10x5
x3 = 759/4-11/4x2+1/4x5
x4 = 585/4-13/4x2+3/4x5
x1 = 441/4-1/4x2-1/4x5
Полагая небазисные переменные x = (3, 4, 1) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (0, -20, 0, 0, 10), x0 = 4410
1. Проверка критерия оптимальности.
В выражении для x0 присутствуют отрицательные элементы. Следовательно, текущий план неоптимален
2. Определение новой базисной переменной.
max(0,20,0,0,-10) = 20
x0 = 4410+20x2-10x5
x3 = 759/4-11/4x2+1/4x5
x4 = 585/4-13/4x2+3/4x5
x1 = 441/4-1/4x2-1/4x5
В качестве новой переменной выбираем x2.
3. Определение новой свободной переменной.
Вычислим значения Di по всем уравнениям для этой переменной: bi / ai2
и из них выберем наименьшее:
min (1893/4 : 23/4 , 1461/4 : 31/4 , 1101/4 : 1/4 ) = 45
Вместо переменной x4 в план войдет переменная x2.
4. Пересчет всех уравнений.
Выразим переменную x2 через x4
x2 = 45-4/13x4+3/13x5
и подставим во все выражения.
x0 = 4410+20(45-4/13x4+3/13x5)-10x5
x3 = 1893/4-23/4(45-4/13x4+3/13x5)+1/4x5
x1 = 1101/4-1/4(45-4/13x4+3/13x5)-1/4x5
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = 5310-80/13x4-70/13x5
x3 = 66+11/13x4-5/13x5
x2 = 45-4/13x4+3/13x5
x1 = 99+1/13x4-4/13x5
Полагая небазисные переменные x = (3, 2, 1) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (0, 0, 0, 80/13, 70/13), x0 = 5310
Выражение для x0 не содержит положительных элементов. Найден оптимальный план.
Окончательный вариант системы уравнений:
x0 = 5310-80/13x4-70/13x5
x3 = 66+11/13x4-5/13x5
x2 = 45-4/13x4+3/13x5
x1 = 99+1/13x4-4/13x5
Оптимальный план можно записать так:
x3 = 66
x2 = 45
x1 = 99
F(X) = 5310

Анализ оптимальной симплекс-таблицы

В оптимальный план вошла дополнительная переменная x3. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 1-го вида в количестве 66
Значение 0 в столбце x1 означает, что использование x1 - выгодно.
Значение 0 в столбце x2 означает, что использование x2 - выгодно.
Значение 62/13 в столбце x4 означает, что теневая цена (двойственная оценка) равна 62/13.
Значение 55/13 в столбце x5 означает, что теневая цена (двойственная оценка) равна 55/13.

Задание. Цех выпускает два вида продукции, используя два вида полуфабрикатов. Продукция используется при комплектовании изделий, при этом на каждую единицу продукции первого вида требуется не более двух единиц продукции второго вида. Нормы расхода полуфабрикатов каждого вида на единицу выпускаемой продукции, общие объемы полуфабрикатов и прибыль от единицы каждой продукции представлены в таблице. Определите план производства, обеспечивающий максимальную прибыль.

Решение.
Скачать решение в Excel

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

Решение.
Скачать решение

загрузка...