Двойственная задача симплекс методом онлайн: Симплекс-метод решения задач линейного программирования. Решение прямой и двойственной задачи. Решение задач и контрольных работ по линейному программированию онлайн

Содержание

Решение задач линейного программирования симплекс-методом. Двойственность ЗЛП

1. Решение задач линейного программирования симплекс-методом. Двойственность ЗЛП.

1
1. Основы симплексного метода
2. Пример решения ЗЛП симплексным
методом
3. Основы теории
двойственности ЗЛП
4. Примеры построения
двойственных задач
2
1. Основы симплексного метода
3
4
5
6
7
8
9
10
11
12
13
14
2. Пример решения ЗЛП симплексным
методом
15
16
17
18
19
20
21
22
23
ПРИМЕР РЕШЕНИЯ ЭТОЙ ЖЕ ЗАДАЧИ В
ПАКЕТЕ MATHCAD
24
25
26
3. Основы теории двойственности
ЗЛП
27
МОДЕЛИ ДВОЙСТВЕННЫХ ЗАДАЧ В
ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
28
29
30
ПРИМЕР
31
32
33
34
ПОЛУЧЕНИЕ РЕШЕНИЯ ДВОЙСТВЕННОЙ
ЗАДАЧИ ПО РЕЗУЛЬТАТАМ РЕШЕНИЯ ПРЯМОЙ
ЗАДАЧИ
Первая теорема двойственности:
Если существует единственное решение
исходной (прямой) задачи, то существует
и единственное решение двойственной
задачи, причем значения целевых функций
на оптимальных решениях совпадают:
max F = min FД.

35
36
При построении двойственной задачи
используются следующие правила:
• каждому ограничению исходной задачи
соответствует переменная двойственной
задачи;
37
• каждой переменной исходной задачи
соответствует ограничение
двойственной, причем коэффициентами
при неизвестных в i-м ограничении
служат коэффициенты при xi в
ограничениях исходной задачи;
38
• коэффициентами при неизвестных в ЦФ
двойственной задачи являются свободные
члены (правые части) в системе
ограничений исходной задачи, а правыми

частями в системе ограничений
двойственной задачи – коэффициенты при
неизвестных в ЦФ исходной, и если
исходная задача формулируется для
нахождения максимума, то двойственная для нахождения минимума (и наоборот).
39
4. Примеры построения двойственных задач
Пример 1. Исходная задача – задача о раскрое
материала (рассматривали ранее)
40
41
42
Кроме того, при использовании
надстройки «Поиск решения» в пакете MS
Excel:
если решить исходную задачу с помощью
этого средства и получить отчет по
устойчивости, то значения в графе
Лагранжа множитель (Теневая цена)
отчета по устойчивости есть оптимальные
значения двойственных переменных:
43
44
Пример 2.

Исходная задача – задача о
планировании производства продукции
45
Пример 2. Исходная задача – задача о
планировании производства продукции
46
47
48
Двойственная задача к рассматриваемой
задаче планирования производства продукции:
49
50
Согласно первой теореме двойственности:
51
Для рассматриваемой задачи можно показать,
что имеется следующее следствие первой
теоремы двойственности —
52
(при использовании надстройки «Поиск
решения» в пакете MS Excel).
53
Удобно использовать надстройку
«Поиск решения» в пакете MS Excel:
если решить исходную задачу с помощью
этого средства и получить отчет по
устойчивости, то значения в графе
Теневая цена отчета по устойчивости
есть оптимальные значения
двойственных переменных.
54

Онлайн Калькулятор: Симплекс Метод

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

Для чего соответствующие ограничения умножаем на -1. После данной манипуляции знак неравенства меняем на противоположный.

Далее необходимо избавиться от неравенств, для чего в левую часть неравенств вводим компенсирующие переменные. Если неравенство вида ≤, то компенсирующая переменная имеет знак +, если неравенство вида ≥, то компенсирующая переменная имеет знак -. Компенсирующие переменные входят в целевую функцию задачи с нулевым коэффициентом.

Теперь в системе ограничений необходимо найти достаточное количество базисных переменных. В каждом ограничении должна быть одна базисная переменная. Базисной является переменная, которая имеет при себе коэффициент 1 и встречается только в одном ограничении. Если в каком-то ограничении нет базисных переменных, то добавляем их искусственно, причем искусственные переменные входят в целевую функцию с коэффициентом -M, если целевая функция стремится к мах и с М, если целевая функция стремится к min.Элементы колонки базис(B)

Переносим в таблицу базовые элементы, которые мы определили на предварительном этапе:

B₁ = x₃;

B₂ = x₄;

B₃ = x₅;

B₄ = x₈;

B₅ = x₉;

Элементы колонки Cb

Каждая ячейка этого столбца равна коэффициенту, который соответствует базовой переменной в соответствующей строке.

Cb₁ = 0;

Cb₂ = 0;

Cb₃ = 0;

Cb₄ = -M;

Cb₅ = -M;

Значения упрявляемых переменных и колонки P

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

P₁ = 600;

P₂ = 225;

P₃ = 1000;

P₄ = 150;

P₅ = 0;

x_1,1 = 2;

x_1,2 = 1;

x_1,3 = 1;

x_1,4 = 0;

x_1,5 = 0;

x_1,6 = 0;

x_1,7 = 0;

x_1,8 = 0;

x_1,9 = 0;

x_2,1 = 0;

x_2,2 = 0;

x_2,3 = 0;

x_2,4 = 1;

x_2,5 = 0;

x_2,6 = 0;

x_2,7 = 0;

x_2,8 = 0;

x_2,9 = 0;

x_3,1 = 5;

x_3,2 = 4;

x_3,3 = 0;

x_3,4 = 0;

x_3,5 = 1;

x_3,6 = 0;

x_3,7 = 0;

x_3,8 = 0;

x_3,9 = 0;

x_4,1 = 0;

x_4,2 = 2;

x_4,3 = 0;

x_4,4 = 0;

x_4,5 = 0;

x_4,6 = -1;

x_4,7 = 0;

x_4,8 = 1;

x_4,9 = 0;

x_5,1 = 0;

x_5,2 = 0;

x_5,3 = 0;

x_5,4 = 0;

x_5,5 = 0;

x_5,6 = 0;

x_5,7 = -1;

x_5,8 = 0;

x_5,9 = 1;

Значение целевой функции

Рассчитываем значение целевой функции, поэлементно умножая столбик Cb на столбик P, сложив результаты произведений.

Max_P = (Cb₁ * P₁) + (Cb₁₁ * P₂ + (Cb₂₁ * P₃ + (Cb₃₁ * P₄ + (Cb₄₁ * P₅ = (0 * 600) + (0 * 225) + (0 * 1000) + (-M * 150) + (-M * 0) = -150M;

Оценки управляемых переменных

Рассчитываем оценки для каждой управляемой переменной, поэлементно умножив значение с колонки переменной, на значение с колонки Cb, суммируем результаты произведений, и с их суммы вычитаем коэффициент целевой функции, при этой переменной.

Max_x₁ = ((Cb₁ * x_1,1) + (Cb₂ * x_2,1) + (Cb₃ * x_3,1) + (Cb₄ * x_4,1) + (Cb₅ * x_5,1) ) — k_x₁ = ((0 * 2) + (0 * 0) + (0 * 5) + (-M * 0) + (-M * 0) ) — 3 = -3;

Max_x₂ = ((Cb₁ * x_1,2) + (Cb₂ * x_2,2) + (Cb₃ * x_3,2) + (Cb₄ * x_4,2) + (Cb₅ * x_5,2) ) — k_x₂ = ((0 * 1) + (0 * 0) + (0 * 4) + (-M * 2) + (-M * 0) ) — 4 = -2M-4;

Max_x₃ = ((Cb₁ * x_1,3) + (Cb₂ * x_2,3) + (Cb₃ * x_3,3) + (Cb₄ * x_4,3) + (Cb₅ * x_5,3) ) — k_x₃ = ((0 * 1) + (0 * 0) + (0 * 0) + (-M * 0) + (-M * 0) ) — 0 = 0;

Max_x₄ = ((Cb₁ * x_1,4) + (Cb₂ * x_2,4) + (Cb₃ * x_3,4) + (Cb₄ * x_4,4) + (Cb₅ * x_5,4) ) — k_x₄ = ((0 * 0) + (0 * 1) + (0 * 0) + (-M * 0) + (-M * 0) ) — 0 = 0;

Max_x₅ = ((Cb₁ * x_1,5) + (Cb₂ * x_2,5) + (Cb₃ * x_3,5) + (Cb₄ * x_4,5) + (Cb₅ * x_5,5) ) — k_x₅ = ((0 * 0) + (0 * 0) + (0 * 1) + (-M * 0) + (-M * 0) ) — 0 = 0;

Max_x₆ = ((Cb₁ * x_1,6) + (Cb₂ * x_2,6) + (Cb₃ * x_3,6) + (Cb₄ * x_4,6) + (Cb₅ * x_5,6) ) — k_x₆ = ((0 * 0) + (0 * 0) + (0 * 0) + (-M * -1) + (-M * 0) ) — 0 = M;

Max_x₇ = ((Cb₁ * x_1,7) + (Cb₂ * x_2,7) + (Cb₃ * x_3,7) + (Cb₄ * x_4,7) + (Cb₅ * x_5,7) ) — k_x₇ = ((0 * 0) + (0 * 0) + (0 * 0) + (-M * 0) + (-M * -1) ) — 0 = M;

Max_x₈ = ((Cb₁ * x_1,8) + (Cb₂ * x_2,8) + (Cb₃ * x_3,8) + (Cb₄ * x_4,8) + (Cb₅ * x_5,8) ) — k_x₈ = ((0 * 0) + (0 * 0) + (0 * 0) + (-M * 1) + (-M * 0) ) — -M = 0;

Max_x₉ = ((Cb₁ * x_1,9) + (Cb₂ * x_2,9) + (Cb₃ * x_3,9) + (Cb₄ * x_4,9) + (Cb₅ * x_5,9) ) — k_x₉ = ((0 * 0) + (0 * 0) + (0 * 0) + (-M * 0) + (-M * 1) ) — -M = 0;

Элементы колонки Q

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

Количество переменных в базисе всегда постоянно, поэтому необходимо выбрать, какую переменную вывести из базиса, для чего мы рассчитываем Q.

Элементы столбика Q рассчитываем поделив значения из колонки P на значение с колонки, соответствующие переменной которая вводится в базис:

Q₁ = P₁ / x_1,2 = 600 / 1 = 600;

Q₂ = P₂ / x_2,2 = 225 / 0 = ∞;

Q₃ = P₃ / x_3,2 = 1000 / 4 = 250;

Q₄ = P₄ / x_4,2 = 150 / 2 = 75;

Q₅ = P₅ / x_5,2 = 0 / 0 = ∞;

Выводим из базиса переменную с наименьшим положительным значением Q.

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

Данный элемент позволит нам рассчитать элементы таблицы следующей итерации.Элементы колонки базис(B)

За результатами вычислений предыдущей итерации убираем с базиса переменную x₈ и ставим на ее место x₂. Все остальные ячейки остаются без изменений.

Элементы колонки Cb

Cb₁ = 0;

Cb₂ = 0;

Cb₃ = 0;

Cb₄ = 4;

Cb₅ = -M;

Значения упрявляемых переменных и колонки P(В качестве исходных данных берутся данные из предыдущей итерации)Заполняем нулями все ячейки, соответствующие переменной, которая только что была введена в базис:(Разрешающий элемент остается без изменений)

x_1,2 = 0;

x_2,2 = 0;

x_3,2 = 0;

x_5,2 = 0;

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

P₄ = P₄ / x_4,2 = 150 / 2 = 75;

x_4,1 = x_4,1 / x_4,2 = 0 / 2 = 0;

x_4,2 = x_4,2 / x_4,2 = 2 / 2 = 1;

x_4,3 = x_4,3 / x_4,2 = 0 / 2 = 0;

x_4,4 = x_4,4 / x_4,2 = 0 / 2 = 0;

x_4,5 = x_4,5 / x_4,2 = 0 / 2 = 0;

x_4,6 = x_4,6 / x_4,2 = -1 / 2 = -0. 5;

x_4,7 = x_4,7 / x_4,2 = 0 / 2 = 0;

x_4,8 = x_4,8 / x_4,2 = 1 / 2 = 0.5;

x_4,9 = x_4,9 / x_4,2 = 0 / 2 = 0;

Остальные пустые ячейки, за исключением строки оценок и колонки Q, рассчитываем методом прямоугольника, относительно разрешающего элемента:

P₁ = (P₁ * x_4,2) — (x_1,2 * P₄) / x_4,2 = ((600 * 2) — (1 * 150)) / 2 = 525;

P₂ = (P₂ * x_4,2) — (x_2,2 * P₄) / x_4,2 = ((225 * 2) — (0 * 150)) / 2 = 225;

P₃ = (P₃ * x_4,2) — (x_3,2 * P₄) / x_4,2 = ((1000 * 2) — (4 * 150)) / 2 = 700;

P₅ = (P₅ * x_4,2) — (x_5,2 * P₄) / x_4,2 = ((0 * 2) — (0 * 150)) / 2 = 0;

x_1,1 = ((x_1,1 * x_4,2) — (x_1,2 * x_4,1)) / x_4,2 = ((2 * 2) — (1 * 0)) / 2 = 2;

x_1,2 = ((x_1,2 * x_4,2) — (x_1,2 * x_4,2)) / x_4,2 = ((1 * 2) — (1 * 2)) / 2 = 0;

x_1,4 = ((x_1,4 * x_4,2) — (x_1,2 * x_4,4)) / x_4,2 = ((0 * 2) — (1 * 0)) / 2 = 0;

x_1,5 = ((x_1,5 * x_4,2) — (x_1,2 * x_4,5)) / x_4,2 = ((0 * 2) — (1 * 0)) / 2 = 0;

x_1,6 = ((x_1,6 * x_4,2) — (x_1,2 * x_4,6)) / x_4,2 = ((0 * 2) — (1 * -1)) / 2 = 0. 5;

x_1,7 = ((x_1,7 * x_4,2) — (x_1,2 * x_4,7)) / x_4,2 = ((0 * 2) — (1 * 0)) / 2 = 0;

x_1,8 = ((x_1,8 * x_4,2) — (x_1,2 * x_4,8)) / x_4,2 = ((0 * 2) — (1 * 1)) / 2 = -0.5;

x_1,9 = ((x_1,9 * x_4,2) — (x_1,2 * x_4,9)) / x_4,2 = ((0 * 2) — (1 * 0)) / 2 = 0;

x_2,1 = ((x_2,1 * x_4,2) — (x_2,2 * x_4,1)) / x_4,2 = ((0 * 2) — (0 * 0)) / 2 = 0;

x_2,2 = ((x_2,2 * x_4,2) — (x_2,2 * x_4,2)) / x_4,2 = ((0 * 2) — (0 * 2)) / 2 = 0;

x_2,4 = ((x_2,4 * x_4,2) — (x_2,2 * x_4,4)) / x_4,2 = ((1 * 2) — (0 * 0)) / 2 = 1;

x_2,5 = ((x_2,5 * x_4,2) — (x_2,2 * x_4,5)) / x_4,2 = ((0 * 2) — (0 * 0)) / 2 = 0;

x_2,6 = ((x_2,6 * x_4,2) — (x_2,2 * x_4,6)) / x_4,2 = ((0 * 2) — (0 * -1)) / 2 = 0;

x_2,7 = ((x_2,7 * x_4,2) — (x_2,2 * x_4,7)) / x_4,2 = ((0 * 2) — (0 * 0)) / 2 = 0;

x_2,8 = ((x_2,8 * x_4,2) — (x_2,2 * x_4,8)) / x_4,2 = ((0 * 2) — (0 * 1)) / 2 = 0;

x_2,9 = ((x_2,9 * x_4,2) — (x_2,2 * x_4,9)) / x_4,2 = ((0 * 2) — (0 * 0)) / 2 = 0;

x_3,1 = ((x_3,1 * x_4,2) — (x_3,2 * x_4,1)) / x_4,2 = ((5 * 2) — (4 * 0)) / 2 = 5;

x_3,2 = ((x_3,2 * x_4,2) — (x_3,2 * x_4,2)) / x_4,2 = ((4 * 2) — (4 * 2)) / 2 = 0;

x_3,4 = ((x_3,4 * x_4,2) — (x_3,2 * x_4,4)) / x_4,2 = ((0 * 2) — (4 * 0)) / 2 = 0;

x_3,5 = ((x_3,5 * x_4,2) — (x_3,2 * x_4,5)) / x_4,2 = ((1 * 2) — (4 * 0)) / 2 = 1;

x_3,6 = ((x_3,6 * x_4,2) — (x_3,2 * x_4,6)) / x_4,2 = ((0 * 2) — (4 * -1)) / 2 = 2;

x_3,7 = ((x_3,7 * x_4,2) — (x_3,2 * x_4,7)) / x_4,2 = ((0 * 2) — (4 * 0)) / 2 = 0;

x_3,8 = ((x_3,8 * x_4,2) — (x_3,2 * x_4,8)) / x_4,2 = ((0 * 2) — (4 * 1)) / 2 = -2;

x_3,9 = ((x_3,9 * x_4,2) — (x_3,2 * x_4,9)) / x_4,2 = ((0 * 2) — (4 * 0)) / 2 = 0;

x_5,1 = ((x_5,1 * x_4,2) — (x_5,2 * x_4,1)) / x_4,2 = ((0 * 2) — (0 * 0)) / 2 = 0;

x_5,2 = ((x_5,2 * x_4,2) — (x_5,2 * x_4,2)) / x_4,2 = ((0 * 2) — (0 * 2)) / 2 = 0;

x_5,4 = ((x_5,4 * x_4,2) — (x_5,2 * x_4,4)) / x_4,2 = ((0 * 2) — (0 * 0)) / 2 = 0;

x_5,5 = ((x_5,5 * x_4,2) — (x_5,2 * x_4,5)) / x_4,2 = ((0 * 2) — (0 * 0)) / 2 = 0;

x_5,6 = ((x_5,6 * x_4,2) — (x_5,2 * x_4,6)) / x_4,2 = ((0 * 2) — (0 * -1)) / 2 = 0;

x_5,7 = ((x_5,7 * x_4,2) — (x_5,2 * x_4,7)) / x_4,2 = ((-1 * 2) — (0 * 0)) / 2 = -1;

x_5,8 = ((x_5,8 * x_4,2) — (x_5,2 * x_4,8)) / x_4,2 = ((0 * 2) — (0 * 1)) / 2 = 0;

x_5,9 = ((x_5,9 * x_4,2) — (x_5,2 * x_4,9)) / x_4,2 = ((1 * 2) — (0 * 0)) / 2 = 1;

Значение целевой функции

Max_P = (Cb₁ * P₁) + (Cb₁₁ * P₂ + (Cb₂₁ * P₃ + (Cb₃₁ * P₄ + (Cb₄₁ * P₅ = (0 * 525) + (0 * 225) + (0 * 700) + (4 * 75) + (-M * 0) = 300;

Оценки управляемых переменных

Max_x₁ = ((Cb₁ * x_1,1) + (Cb₂ * x_2,1) + (Cb₃ * x_3,1) + (Cb₄ * x_4,1) + (Cb₅ * x_5,1) ) — k_x₁ = ((0 * 2) + (0 * 0) + (0 * 5) + (4 * 0) + (-M * 0) ) — 3 = -3;

Max_x₂ = ((Cb₁ * x_1,2) + (Cb₂ * x_2,2) + (Cb₃ * x_3,2) + (Cb₄ * x_4,2) + (Cb₅ * x_5,2) ) — k_x₂ = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 1) + (-M * 0) ) — 4 = 0;

Max_x₃ = ((Cb₁ * x_1,3) + (Cb₂ * x_2,3) + (Cb₃ * x_3,3) + (Cb₄ * x_4,3) + (Cb₅ * x_5,3) ) — k_x₃ = ((0 * 1) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * 0) ) — 0 = 0;

Max_x₄ = ((Cb₁ * x_1,4) + (Cb₂ * x_2,4) + (Cb₃ * x_3,4) + (Cb₄ * x_4,4) + (Cb₅ * x_5,4) ) — k_x₄ = ((0 * 0) + (0 * 1) + (0 * 0) + (4 * 0) + (-M * 0) ) — 0 = 0;

Max_x₅ = ((Cb₁ * x_1,5) + (Cb₂ * x_2,5) + (Cb₃ * x_3,5) + (Cb₄ * x_4,5) + (Cb₅ * x_5,5) ) — k_x₅ = ((0 * 0) + (0 * 0) + (0 * 1) + (4 * 0) + (-M * 0) ) — 0 = 0;

Max_x₆ = ((Cb₁ * x_1,6) + (Cb₂ * x_2,6) + (Cb₃ * x_3,6) + (Cb₄ * x_4,6) + (Cb₅ * x_5,6) ) — k_x₆ = ((0 * 0. 5) + (0 * 0) + (0 * 2) + (4 * -0.5) + (-M * 0) ) — 0 = -2;

Max_x₇ = ((Cb₁ * x_1,7) + (Cb₂ * x_2,7) + (Cb₃ * x_3,7) + (Cb₄ * x_4,7) + (Cb₅ * x_5,7) ) — k_x₇ = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * -1) ) — 0 = M;

Max_x₈ = ((Cb₁ * x_1,8) + (Cb₂ * x_2,8) + (Cb₃ * x_3,8) + (Cb₄ * x_4,8) + (Cb₅ * x_5,8) ) — k_x₈ = ((0 * -0. 5) + (0 * 0) + (0 * -2) + (4 * 0.5) + (-M * 0) ) — -M = M+2;

Max_x₉ = ((Cb₁ * x_1,9) + (Cb₂ * x_2,9) + (Cb₃ * x_3,9) + (Cb₄ * x_4,9) + (Cb₅ * x_5,9) ) — k_x₉ = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * 1) ) — -M = 0;

Элементы колонки Q

Q₁ = P₁ / x_1,1 = 525 / 2 = 262.5;

Q₂ = P₂ / x_2,1 = 225 / 0 = ∞;

Q₃ = P₃ / x_3,1 = 700 / 5 = 140;

Q₄ = P₄ / x_4,1 = 75 / 0 = ∞;

Q₅ = P₅ / x_5,1 = 0 / 0 = ∞;

Выводим из базиса переменную с наименьшим положительным значением Q.

Данный элемент позволит нам рассчитать элементы таблицы следующей итерации.Элементы колонки базис(B)

За результатами вычислений предыдущей итерации убираем с базиса переменную x₅ и ставим на ее место x₁. Все остальные ячейки остаются без изменений.

Элементы колонки Cb

Cb₁ = 0;

Cb₂ = 0;

Cb₃ = 3;

Cb₄ = 4;

Cb₅ = -M;

x_1,1 = 0;

x_2,1 = 0;

x_4,1 = 0;

x_5,1 = 0;

P₃ = P₃ / x_3,1 = 700 / 5 = 140;

x_3,1 = x_3,1 / x_3,1 = 5 / 5 = 1;

x_3,2 = x_3,2 / x_3,1 = 0 / 5 = 0;

x_3,3 = x_3,3 / x_3,1 = 0 / 5 = 0;

x_3,4 = x_3,4 / x_3,1 = 0 / 5 = 0;

x_3,5 = x_3,5 / x_3,1 = 1 / 5 = 0. 2;

x_3,6 = x_3,6 / x_3,1 = 2 / 5 = 0.4;

x_3,7 = x_3,7 / x_3,1 = 0 / 5 = 0;

x_3,8 = x_3,8 / x_3,1 = -2 / 5 = -0.4;

x_3,9 = x_3,9 / x_3,1 = 0 / 5 = 0;

P₁ = (P₁ * x_3,1) — (x_1,1 * P₃) / x_3,1 = ((525 * 5) — (2 * 700)) / 5 = 245;

P₂ = (P₂ * x_3,1) — (x_2,1 * P₃) / x_3,1 = ((225 * 5) — (0 * 700)) / 5 = 225;

P₄ = (P₄ * x_3,1) — (x_4,1 * P₃) / x_3,1 = ((75 * 5) — (0 * 700)) / 5 = 75;

P₅ = (P₅ * x_3,1) — (x_5,1 * P₃) / x_3,1 = ((0 * 5) — (0 * 700)) / 5 = 0;

x_1,1 = ((x_1,1 * x_3,1) — (x_1,1 * x_3,1)) / x_3,1 = ((2 * 5) — (2 * 5)) / 5 = 0;

x_1,3 = ((x_1,3 * x_3,1) — (x_1,1 * x_3,3)) / x_3,1 = ((1 * 5) — (2 * 0)) / 5 = 1;

x_1,4 = ((x_1,4 * x_3,1) — (x_1,1 * x_3,4)) / x_3,1 = ((0 * 5) — (2 * 0)) / 5 = 0;

x_1,5 = ((x_1,5 * x_3,1) — (x_1,1 * x_3,5)) / x_3,1 = ((0 * 5) — (2 * 1)) / 5 = -0. 4;

x_1,6 = ((x_1,6 * x_3,1) — (x_1,1 * x_3,6)) / x_3,1 = ((0.5 * 5) — (2 * 2)) / 5 = -0.3;

x_1,7 = ((x_1,7 * x_3,1) — (x_1,1 * x_3,7)) / x_3,1 = ((0 * 5) — (2 * 0)) / 5 = 0;

x_1,8 = ((x_1,8 * x_3,1) — (x_1,1 * x_3,8)) / x_3,1 = ((-0.5 * 5) — (2 * -2)) / 5 = 0.3;

x_1,9 = ((x_1,9 * x_3,1) — (x_1,1 * x_3,9)) / x_3,1 = ((0 * 5) — (2 * 0)) / 5 = 0;

x_2,1 = ((x_2,1 * x_3,1) — (x_2,1 * x_3,1)) / x_3,1 = ((0 * 5) — (0 * 5)) / 5 = 0;

x_2,3 = ((x_2,3 * x_3,1) — (x_2,1 * x_3,3)) / x_3,1 = ((0 * 5) — (0 * 0)) / 5 = 0;

x_2,4 = ((x_2,4 * x_3,1) — (x_2,1 * x_3,4)) / x_3,1 = ((1 * 5) — (0 * 0)) / 5 = 1;

x_2,5 = ((x_2,5 * x_3,1) — (x_2,1 * x_3,5)) / x_3,1 = ((0 * 5) — (0 * 1)) / 5 = 0;

x_2,6 = ((x_2,6 * x_3,1) — (x_2,1 * x_3,6)) / x_3,1 = ((0 * 5) — (0 * 2)) / 5 = 0;

x_2,7 = ((x_2,7 * x_3,1) — (x_2,1 * x_3,7)) / x_3,1 = ((0 * 5) — (0 * 0)) / 5 = 0;

x_2,8 = ((x_2,8 * x_3,1) — (x_2,1 * x_3,8)) / x_3,1 = ((0 * 5) — (0 * -2)) / 5 = 0;

x_2,9 = ((x_2,9 * x_3,1) — (x_2,1 * x_3,9)) / x_3,1 = ((0 * 5) — (0 * 0)) / 5 = 0;

x_4,1 = ((x_4,1 * x_3,1) — (x_4,1 * x_3,1)) / x_3,1 = ((0 * 5) — (0 * 5)) / 5 = 0;

x_4,3 = ((x_4,3 * x_3,1) — (x_4,1 * x_3,3)) / x_3,1 = ((0 * 5) — (0 * 0)) / 5 = 0;

x_4,4 = ((x_4,4 * x_3,1) — (x_4,1 * x_3,4)) / x_3,1 = ((0 * 5) — (0 * 0)) / 5 = 0;

x_4,5 = ((x_4,5 * x_3,1) — (x_4,1 * x_3,5)) / x_3,1 = ((0 * 5) — (0 * 1)) / 5 = 0;

x_4,6 = ((x_4,6 * x_3,1) — (x_4,1 * x_3,6)) / x_3,1 = ((-0. 5 * 5) — (0 * 2)) / 5 = -0.5;

x_4,7 = ((x_4,7 * x_3,1) — (x_4,1 * x_3,7)) / x_3,1 = ((0 * 5) — (0 * 0)) / 5 = 0;

x_4,8 = ((x_4,8 * x_3,1) — (x_4,1 * x_3,8)) / x_3,1 = ((0.5 * 5) — (0 * -2)) / 5 = 0.5;

x_4,9 = ((x_4,9 * x_3,1) — (x_4,1 * x_3,9)) / x_3,1 = ((0 * 5) — (0 * 0)) / 5 = 0;

x_5,1 = ((x_5,1 * x_3,1) — (x_5,1 * x_3,1)) / x_3,1 = ((0 * 5) — (0 * 5)) / 5 = 0;

x_5,3 = ((x_5,3 * x_3,1) — (x_5,1 * x_3,3)) / x_3,1 = ((0 * 5) — (0 * 0)) / 5 = 0;

x_5,4 = ((x_5,4 * x_3,1) — (x_5,1 * x_3,4)) / x_3,1 = ((0 * 5) — (0 * 0)) / 5 = 0;

x_5,5 = ((x_5,5 * x_3,1) — (x_5,1 * x_3,5)) / x_3,1 = ((0 * 5) — (0 * 1)) / 5 = 0;

x_5,6 = ((x_5,6 * x_3,1) — (x_5,1 * x_3,6)) / x_3,1 = ((0 * 5) — (0 * 2)) / 5 = 0;

x_5,7 = ((x_5,7 * x_3,1) — (x_5,1 * x_3,7)) / x_3,1 = ((-1 * 5) — (0 * 0)) / 5 = -1;

x_5,8 = ((x_5,8 * x_3,1) — (x_5,1 * x_3,8)) / x_3,1 = ((0 * 5) — (0 * -2)) / 5 = 0;

x_5,9 = ((x_5,9 * x_3,1) — (x_5,1 * x_3,9)) / x_3,1 = ((1 * 5) — (0 * 0)) / 5 = 1;

Значение целевой функции

Max_P = (Cb₁ * P₁) + (Cb₁₁ * P₂ + (Cb₂₁ * P₃ + (Cb₃₁ * P₄ + (Cb₄₁ * P5) = (0 * 245) + (0 * 225) + (3 * 140) + (4 * 75) + (-M * 0) = 720;

Оценки управляемых переменных

Max_x₁ = ((Cb₁ * x_1,1) + (Cb₂ * x_2,1) + (Cb₃ * x_3,1) + (Cb₄ * x_4,1) + (Cb₅ * x_5,1) ) — k_x₁ = ((0 * 0) + (0 * 0) + (3 * 1) + (4 * 0) + (-M * 0) ) — 3 = 0;

Max_x₂ = ((Cb₁ * x_1,2) + (Cb₂ * x_2,2) + (Cb₃ * x_3,2) + (Cb₄ * x_4,2) + (Cb₅ * x_5,2) ) — k_x₂ = ((0 * 0) + (0 * 0) + (3 * 0) + (4 * 1) + (-M * 0) ) — 4 = 0;

Max_x₃ = ((Cb₁ * x_1,3) + (Cb₂ * x_2,3) + (Cb₃ * x_3,3) + (Cb₄ * x_4,3) + (Cb₅ * x_5,3) ) — k_x₃ = ((0 * 1) + (0 * 0) + (3 * 0) + (4 * 0) + (-M * 0) ) — 0 = 0;

Max_x₄ = ((Cb₁ * x_1,4) + (Cb₂ * x_2,4) + (Cb₃ * x_3,4) + (Cb₄ * x_4,4) + (Cb₅ * x_5,4) ) — k_x₄ = ((0 * 0) + (0 * 1) + (3 * 0) + (4 * 0) + (-M * 0) ) — 0 = 0;

Max_x₅ = ((Cb₁ * x_1,5) + (Cb₂ * x_2,5) + (Cb₃ * x_3,5) + (Cb₄ * x_4,5) + (Cb₅ * x_5,5) ) — k_x₅ = ((0 * -0. 4) + (0 * 0) + (3 * 0.2) + (4 * 0) + (-M * 0) ) — 0 = 0.6;

Max_x₆ = ((Cb₁ * x_1,6) + (Cb₂ * x_2,6) + (Cb₃ * x_3,6) + (Cb₄ * x_4,6) + (Cb₅ * x_5,6) ) — k_x₆ = ((0 * -0.3) + (0 * 0) + (3 * 0.4) + (4 * -0.5) + (-M * 0) ) — 0 = -0.8;

Max_x₇ = ((Cb₁ * x_1,7) + (Cb₂ * x_2,7) + (Cb₃ * x_3,7) + (Cb₄ * x_4,7) + (Cb₅ * x_5,7) ) — k_x₇ = ((0 * 0) + (0 * 0) + (3 * 0) + (4 * 0) + (-M * -1) ) — 0 = M;

Max_x₈ = ((Cb₁ * x_1,8) + (Cb₂ * x_2,8) + (Cb₃ * x_3,8) + (Cb₄ * x_4,8) + (Cb₅ * x_5,8) ) — k_x₈ = ((0 * 0. 3) + (0 * 0) + (3 * -0.4) + (4 * 0.5) + (-M * 0) ) — -M = M+0.8;

Max_x₉ = ((Cb₁ * x_1,9) + (Cb₂ * x_2,9) + (Cb₃ * x_3,9) + (Cb₄ * x_4,9) + (Cb₅ * x_5,9) ) — k_x₉ = ((0 * 0) + (0 * 0) + (3 * 0) + (4 * 0) + (-M * 1) ) — -M = 0;

Элементы колонки Q

Q₁ = P₁ / x_1,6 = 245 / -0.3 = -816.67;

Q₂ = P₂ / x_2,6 = 225 / 0 = ∞;

Q₃ = P₃ / x_3,6 = 140 / 0.4 = 350;

Q₄ = P₄ / x_4,6 = 75 / -0.5 = -150;

Q₅ = P₅ / x_5,6 = 0 / 0 = ∞;

Выводим из базиса переменную с наименьшим положительным значением Q.

Данный элемент позволит нам рассчитать элементы таблицы следующей итерации.Элементы колонки базис(B)

За результатами вычислений предыдущей итерации убираем с базиса переменную x₁ и ставим на ее место x₆. Все остальные ячейки остаются без изменений.

Элементы колонки Cb

Cb₁ = 0;

Cb₂ = 0;

Cb₃ = 0;

Cb₄ = 4;

Cb₅ = -M;

x_1,6 = 0;

x_2,6 = 0;

x_4,6 = 0;

x_5,6 = 0;

P₃ = P₃ / x_3,6 = 140 / 0. 4 = 350;

x_3,1 = x_3,1 / x_3,6 = 1 / 0.4 = 2.5;

x_3,2 = x_3,2 / x_3,6 = 0 / 0.4 = 0;

x_3,3 = x_3,3 / x_3,6 = 0 / 0.4 = 0;

x_3,4 = x_3,4 / x_3,6 = 0 / 0.4 = 0;

x_3,5 = x_3,5 / x_3,6 = 0.2 / 0.4 = 0.5;

x_3,6 = x_3,6 / x_3,6 = 0.4 / 0.4 = 1;

x_3,7 = x_3,7 / x_3,6 = 0 / 0. 4 = 0;

x_3,8 = x_3,8 / x_3,6 = -0.4 / 0.4 = -1;

x_3,9 = x_3,9 / x_3,6 = 0 / 0.4 = 0;

P₁ = (P₁ * x_3,6) — (x_1,6 * P₃) / x_3,6 = ((245 * 0.4) — (-0.3 * 140)) / 0.4 = 350;

P₂ = (P₂ * x_3,6) — (x_2,6 * P₃) / x_3,6 = ((225 * 0. 4) — (0 * 140)) / 0.4 = 225;

P₄ = (P₄ * x_3,6) — (x_4,6 * P₃) / x_3,6 = ((75 * 0.4) — (-0.5 * 140)) / 0.4 = 250;

P₅ = (P₅ * x_3,6) — (x_5,6 * P₃) / x_3,6 = ((0 * 0.4) — (0 * 140)) / 0.4 = 0;

x_1,1 = ((x_1,1 * x_3,6) — (x_1,6 * x_3,1)) / x_3,6 = ((0 * 0.4) — (-0.3 * 1)) / 0.4 = 0.75;

x_1,2 = ((x_1,2 * x_3,6) — (x_1,6 * x_3,2)) / x_3,6 = ((0 * 0. 4) — (-0.3 * 0)) / 0.4 = 0;

x_1,3 = ((x_1,3 * x_3,6) — (x_1,6 * x_3,3)) / x_3,6 = ((1 * 0.4) — (-0.3 * 0)) / 0.4 = 1;

x_1,4 = ((x_1,4 * x_3,6) — (x_1,6 * x_3,4)) / x_3,6 = ((0 * 0.4) — (-0.3 * 0)) / 0.4 = 0;

x_1,5 = ((x_1,5 * x_3,6) — (x_1,6 * x_3,5)) / x_3,6 = ((-0.4 * 0.4) — (-0.3 * 0.2)) / 0.4 = -0.25;

x_1,6 = ((x_1,6 * x_3,6) — (x_1,6 * x_3,6)) / x_3,6 = ((-0. 3 * 0.4) — (-0.3 * 0.4)) / 0.4 = 0;

x_1,8 = ((x_1,8 * x_3,6) — (x_1,6 * x_3,8)) / x_3,6 = ((0.3 * 0.4) — (-0.3 * -0.4)) / 0.4 = 0;

x_1,9 = ((x_1,9 * x_3,6) — (x_1,6 * x_3,9)) / x_3,6 = ((0 * 0.4) — (-0.3 * 0)) / 0.4 = 0;

x_2,1 = ((x_2,1 * x_3,6) — (x_2,6 * x_3,1)) / x_3,6 = ((0 * 0.4) — (0 * 1)) / 0.4 = 0;

x_2,2 = ((x_2,2 * x_3,6) — (x_2,6 * x_3,2)) / x_3,6 = ((0 * 0. 4) — (0 * 0)) / 0.4 = 0;

x_2,3 = ((x_2,3 * x_3,6) — (x_2,6 * x_3,3)) / x_3,6 = ((0 * 0.4) — (0 * 0)) / 0.4 = 0;

x_2,4 = ((x_2,4 * x_3,6) — (x_2,6 * x_3,4)) / x_3,6 = ((1 * 0.4) — (0 * 0)) / 0.4 = 1;

x_2,5 = ((x_2,5 * x_3,6) — (x_2,6 * x_3,5)) / x_3,6 = ((0 * 0.4) — (0 * 0.2)) / 0.4 = 0;

x_2,6 = ((x_2,6 * x_3,6) — (x_2,6 * x_3,6)) / x_3,6 = ((0 * 0. 4) — (0 * 0.4)) / 0.4 = 0;

x_2,8 = ((x_2,8 * x_3,6) — (x_2,6 * x_3,8)) / x_3,6 = ((0 * 0.4) — (0 * -0.4)) / 0.4 = 0;

x_2,9 = ((x_2,9 * x_3,6) — (x_2,6 * x_3,9)) / x_3,6 = ((0 * 0.4) — (0 * 0)) / 0.4 = 0;

x_4,1 = ((x_4,1 * x_3,6) — (x_4,6 * x_3,1)) / x_3,6 = ((0 * 0.4) — (-0.5 * 1)) / 0.4 = 1.25;

x_4,2 = ((x_4,2 * x_3,6) — (x_4,6 * x_3,2)) / x_3,6 = ((1 * 0. 4) — (-0.5 * 0)) / 0.4 = 1;

x_4,3 = ((x_4,3 * x_3,6) — (x_4,6 * x_3,3)) / x_3,6 = ((0 * 0.4) — (-0.5 * 0)) / 0.4 = 0;

x_4,4 = ((x_4,4 * x_3,6) — (x_4,6 * x_3,4)) / x_3,6 = ((0 * 0.4) — (-0.5 * 0)) / 0.4 = 0;

x_4,5 = ((x_4,5 * x_3,6) — (x_4,6 * x_3,5)) / x_3,6 = ((0 * 0.4) — (-0.5 * 0.2)) / 0.4 = 0.25;

x_4,6 = ((x_4,6 * x_3,6) — (x_4,6 * x_3,6)) / x_3,6 = ((-0. 5 * 0.4) — (-0.5 * 0.4)) / 0.4 = 0;

x_4,8 = ((x_4,8 * x_3,6) — (x_4,6 * x_3,8)) / x_3,6 = ((0.5 * 0.4) — (-0.5 * -0.4)) / 0.4 = 0;

x_4,9 = ((x_4,9 * x_3,6) — (x_4,6 * x_3,9)) / x_3,6 = ((0 * 0.4) — (-0.5 * 0)) / 0.4 = 0;

x_5,1 = ((x_5,1 * x_3,6) — (x_5,6 * x_3,1)) / x_3,6 = ((0 * 0.4) — (0 * 1)) / 0.4 = 0;

x_5,2 = ((x_5,2 * x_3,6) — (x_5,6 * x_3,2)) / x_3,6 = ((0 * 0. 4) — (0 * 0)) / 0.4 = 0;

x_5,3 = ((x_5,3 * x_3,6) — (x_5,6 * x_3,3)) / x_3,6 = ((0 * 0.4) — (0 * 0)) / 0.4 = 0;

x_5,4 = ((x_5,4 * x_3,6) — (x_5,6 * x_3,4)) / x_3,6 = ((0 * 0.4) — (0 * 0)) / 0.4 = 0;

x_5,5 = ((x_5,5 * x_3,6) — (x_5,6 * x_3,5)) / x_3,6 = ((0 * 0.4) — (0 * 0.2)) / 0.4 = 0;

x_5,6 = ((x_5,6 * x_3,6) — (x_5,6 * x_3,6)) / x_3,6 = ((0 * 0. 4) — (0 * 0.4)) / 0.4 = 0;

x_5,8 = ((x_5,8 * x_3,6) — (x_5,6 * x_3,8)) / x_3,6 = ((0 * 0.4) — (0 * -0.4)) / 0.4 = 0;

x_5,9 = ((x_5,9 * x_3,6) — (x_5,6 * x_3,9)) / x_3,6 = ((1 * 0.4) — (0 * 0)) / 0.4 = 1;

Значение целевой функции

Max_P = (Cb₁ * P₁) + (Cb₁₁ * P₂ + (Cb₂₁ * P₃ + (Cb₃₁ * P₄ + (Cb₄₁ * P₅ = (0 * 350) + (0 * 225) + (0 * 350) + (4 * 250) + (-M * 0) = 1000;

Оценки управляемых переменных

Max_x₁ = ((Cb₁ * x_1,1) + (Cb₂ * x_2,1) + (Cb₃ * x_3,1) + (Cb₄ * x_4,1) + (Cb₅ * x_5,1) ) — k_x₁ = ((0 * 0.75) + (0 * 0) + (0 * 2.5) + (4 * 1.25) + (-M * 0) ) — 3 = 2;

Max_x₂ = ((Cb₁ * x_1,2) + (Cb₂ * x_2,2) + (Cb₃ * x_3,2) + (Cb₄ * x_4,2) + (Cb₅ * x_5,2) ) — k_x₂ = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 1) + (-M * 0) ) — 4 = 0;

Max_x₃ = ((Cb₁ * x_1,3) + (Cb₂ * x_2,3) + (Cb₃ * x_3,3) + (Cb₄ * x_4,3) + (Cb₅ * x_5,3) ) — k_x₃ = ((0 * 1) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * 0) ) — 0 = 0;

Max_x₄ = ((Cb₁ * x_1,4) + (Cb₂ * x_2,4) + (Cb₃ * x_3,4) + (Cb₄ * x_4,4) + (Cb₅ * x_5,4) ) — k_x₄ = ((0 * 0) + (0 * 1) + (0 * 0) + (4 * 0) + (-M * 0) ) — 0 = 0;

Max_x₅ = ((Cb₁ * x_1,5) + (Cb₂ * x_2,5) + (Cb₃ * x_3,5) + (Cb₄ * x_4,5) + (Cb₅ * x_5,5) ) — k_x₅ = ((0 * -0. 25) + (0 * 0) + (0 * 0.5) + (4 * 0.25) + (-M * 0) ) — 0 = 1;

Max_x₆ = ((Cb₁ * x_1,6) + (Cb₂ * x_2,6) + (Cb₃ * x_3,6) + (Cb₄ * x_4,6) + (Cb₅ * x_5,6) ) — k_x₆ = ((0 * 0) + (0 * 0) + (0 * 1) + (4 * 0) + (-M * 0) ) — 0 = 0;

Max_x₇ = ((Cb₁ * x_1,7) + (Cb₂ * x_2,7) + (Cb₃ * x_3,7) + (Cb₄ * x_4,7) + (Cb₅ * x_5,7) ) — k_x₇ = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * -1) ) — 0 = M;

Max_x₈ = ((Cb₁ * x_1,8) + (Cb₂ * x_2,8) + (Cb₃ * x_3,8) + (Cb₄ * x_4,8) + (Cb₅ * x_5,8) ) — k_x₈ = ((0 * 0) + (0 * 0) + (0 * -1) + (4 * 0) + (-M * 0) ) — -M = M;

Max_x₉ = ((Cb₁ * x_1,9) + (Cb₂ * x_2,9) + (Cb₃ * x_3,9) + (Cb₄ * x_4,9) + (Cb₅ * x_5,9) ) — k_x₉ = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * 1) ) — -M = 0;

Ответ:

Поскольку среди оценок управляемых переменных нет отрицательных значений, текущая таблица имеет оптимальное решение.

Значение целевой функции:

F* = 1000

Переменные которые присутствуют в базисе, равны соответствующим ячейкам колонки P, все остальные переменные равны нулю:

x₁ = 0;

x₂ = 250;

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

Ниже приведено условие и решение задачи. Закачка решения в формате doc начнется автоматически через 10 секунд.

На предприятии имеется возможность выпускать n видов продукции . При ее изготовлении используются ресурсы Р1, Р2 и Р3. Размеры допустимых затрат ресурсов ограничены соответственно величинами b1, b2 и b3. Расход ресурса i-го вида на единицу продукции j-го вида составляет аij единиц. Цена единицы продукции j-го вида равна сj ден. ед.

а11	а12	а13	а14	b1		1	1	1	1	6000
а21	а22	а23	а24	b2	=	0. 5	1	5	0.5	5000
а31	а32	а33	а34	b3		0.5	0.5	20	0.5	9000
с1	с2	с3	с4			80	100	300	80

Требуется:

1) составить экономико-математическую модель задачи, позволяющую найти сбалансированный по ресурсам план выпуска продукции, обеспечивающий предприятию максимальный доход;

2) симплексным методом найти оптимальный план выпуска продукции по видам; (дать содержательный ответ, раскрыв экономический смысл всех переменных, приведенных в решении задачи);

3) сформулировать в экономических терминах двойственную задачу и составить ее математическою модель;

4) найти компоненты оптимального плана двойственной задачи (двойственные оценки используя решение исходной задачи и соответствие между двойственными переменными.

Решение

Обозначим через Х1 , Х2 , Х3— количество единиц продукции соответственно П1, П2, П3, планируемой к выпуску, а через f—величину прибыли от реализации этой продукции. Тогда , учитывая значение прибыли от единицы продукции П1 =80 ден. ед., П2=100 ден. ед., П3=300 ден. ед., запишем суммарную величину прибыли — целевую функцию — в следующем виде:

f = 80Х1 + 100Х2 +300Х3. (2.1)

Переменные Х1, Х2 , Х 3 должны удовлетворять ограничениям, накладываемым на расход имеющихся в распоряжении предприятия ресурсов. Так, затраты ресурса P1 на выполнение плана (Х1 , Х2 , Х3) составят (Х1 +Х2 +Х3) ед., где Х1 — затраты ресурса P1на выпуск Х1 ед. продукции П1; Х2- затраты ресурсы P1 на выпуск Х2 ед. продукции П2 и т.д. Понятно, что указанная сумма не может превышать имеющийся запас P1 в 6000 ед., т.е.

Х1 +Х2 +Х3 ≤6000. (2.2)

Аналогично получаем ограничения по расходу ресурсов P2 и P3:

0. 5 Х1 +Х2 +5Х3 ≤5000. (2.3)

0.5Х1 +0.5Х2 +20Х3 ≤9000. (2.4)

По смыслу задачи переменные Х1, Х2 , Х 3 не могут выражаться отрицательными числами, т.е.

Хj ≥0 (j=1,3) (2.5)

Соотношения (2.1) — (2.5) образуют экономико-математическую модель данной задачи.

Итак, математически задача сводится к нахождению числовых значений Х1*, Х2*, Х 3* переменных Х1, Х2 , Х 3 , удовлетворяющих линейным неравенствам (2.2) — (2.5) и доставляющих максимум линейной функции (2.1)

2. Прежде чем решать задачу линейного программирования симплекс-методом, ее модель приводят к канонической форме. Основным признаком канонической формы является запись ограничений задачи в виде равенств. В нашем же случае ограничения (2.2) — (2.4) имеют вид неравенств типа «≤». Чтобы преобразовать их в эквивалентные уравнения, введем в левые части неравенств дополнительные (балансовые) неотрицательные переменные Х4 , Х5 , Х6 , обозначающие разности между правыми и левыми частями этих неравенств.

В результате модель можно записать в виде

f = 80Х1 +100Х2 +300Х3 (max) (2.6)

Х1 +Х2 +Х3 + Х4 = 6000

0,5Х1 +Х2 +5Х3 + Х5 =5000 (2.7)

0.5Х1 +0.5Х2 +20Х3 + Х6 =9000

Хj ≥0 (j=1,6) (2.8)

Заметим здесь же, что дополнительные переменные Х4 , Х5 , Х6 имеют вполне определенный экономический смысл — это возможные остатки ресурсов соответственно P1, P2, P3 . Их еще называют резервами.

Анализируя каноническую модель (2.6) — (2.8), замечаем, что каждая из переменных Х4 , Х5 , Х6 входит только в одно из уравнений системы (2.7). Это обстоятельство свидетельствует о том, что в системе (2.7) переменные Х4 , Х5 , Х6 являются базисными, а остальные переменные Х1 , Х2 , Х3 — свободными. В связи с этим в первую симплекс-таблицу систему ограничительных уравнений (2. 7) можно записать в виде, разрешенном относительно базиса Х4 , Х5 , Х6 (табл. 2.1).

Таблица 2.1

БП	1	СП
БП	1	— Х1	— Х2	— Х3
Х4=	6000	1	1	1
Х5=	5000	0.5	1	5
Х6=	9000	0.5	0.5	20
f	0	-80	-100	-300

Все элементы столбца свободных членов положительны, поэтому содержащийся в табл. 2.1 план (0; 0; 0; 6000;5000; 9000), является опорным. Однако этот план не является оптимальным: в f — строке имеются отрицательные элементы.

Чтобы получить опорный план, более близкий к оптимальному, выполним симплексное преобразование табл. 2.1. С этой целью выберем переменные, участвующие в преобразовании базиса Х4 , Х5 , Х6 в новый базис. Наибольший по модулю отрицательный элемент (-300) f-строки указывает, что в новый базис следует ввести переменную Х3 ,т.е. в качестве разрешающего в предстоящем симплексном преобразовании надо взять первый столбец. Чтобы определить переменную, выводимую из базиса, составляем симплексные отношения и выбираем наименьшее из них

Min(6000/1;5000/5;9000/20)=9000/20=450

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

В f-строке табл. 2.2 есть отрицательные элементы, значит, опорный

план (0;0; 450;5550;2750;0) оптимальным не является.

Таблица 2.2

БП	1	СП
БП	1	— Х1	— Х2	— Х6
Х4=	5550	0.975	0.975	-0.05
Х5=	2750	0.375	0.875	-0.25
Х3=	450	0.025	0. 025	0.05
f	135000	-72.5	-92.5	15

Рассуждая аналогично предыдущему, устанавливаем, что для улучшения этого плана надо выполнить очередное симплексное преобразование с разрешающим элементом 0.875 . В результате получаем табл. 2.3

Таблица 2.3

БП	1	СП
БП	1	— Х1	— Х5	— Х6
Х4=	2486	0.557	-1.11	0. 229
Х2=	3143	0.429	1.143	-0.286
Х3=	371.4	0.014	-0.029	0.057
f	425714.3	-32.86	106	11.43

В f-строке табл. 2.2 есть отрицательные элементы, значит, опорный план оптимальным не является. Рассуждая аналогично предыдущему, устанавливаем, что для улучшения этого плана надо выполнить очередное симплексное преобразование с разрешающим элементом 0.557 . В результате получаем табл. 2.4

Таблица 2.4

БП	1	СП
БП	1	— Х4	— Х5	— Х6
Х1=	4462
Х2=	1231
Х3=	307. 7
f	572307.7	59	40	2.05

Следовательно, опорный план (4462 ; 1231 ; 307.7 ; 0 ; 0 ; 0 ) является оптимальным, а соответствующее ему значение 572307.7 целевой функции будет максимальным.

Итак, по оптимальному плану следует изготовить 4462 ед. продукции П1 , 1231 ед. продукции П2, 307.7 ед. продукции П3 .

При этом предприятие получит максимальную прибыль в размере 572307.7 ден. ед. Pесурсы будут израсходованы полностью.

3. Двойственная переменная Yi. выступает коэффициентом при b i ,следовательно определяет зависимость целевой функции от изменения ресурсов b i на единицу.

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

задачи (2. 1)- (2.5) в следующем виде:

1	1	1	6000
0.5	1	5	5000
0.5	0.5	20	9000
80	100	300	f max

Транспонируем матрицу (2.9). В результате получим матрицу (2.10) двойственной задачи:

1	0.5	0.5	80
1	1	0. 5	100
1	5	20	300
6000	5000	9000	φ min

По матрице (2.10) легко написать модель задачи, двойственной к исходной задаче:

φ =6000Y1 + 5000Y2 +9000Y3 (min) (2.11)

Y1 +0.5Y2 +0.5Y3 ≥80

Y1 +Y2 +0.5Y3 ≥100

Y1 +5Y2 +20Y3 ≥300 (2.12)

Yi ≥0 (j=1,3) (2.13)

4. Из теорем двойственности следует, что если решена одна из пары двойственных задач, то одновременно найдено решение и другой задачи. Компоненты оптимального плана этой задачи находятся в строке целевой функции последней симплекс — таблицы решенной задачи.

В п. 2 мы нашли оптимальный план исходной задачи, его компоненты находятся в

табл. 2.3. В f-строке этой же таблицы содержатся и компоненты Yi* оптимального плана двойственной задачи (2.11) — (2.13). Выписать компоненты Yi* поможет соответствие между переменными двойственных задач. Чтобы установить это соответствие, преобразуем ограничения-неравенства (2.12) в эквивалентные уравнения, вычитая из левых частей дополнительные неотрицательные переменные Y1, Y2 и Y3 , равные разностям между левыми и правыми частями этих неравенств. Тогда модель (2.11)— (2.13) запишется в виде

φ = 6000Y1 + 5000Y2 +9000Y3 (min)

Y1 +0.5Y2 +0.5Y3 — Y4=80

Y1 +Y2 +0.5Y3 — Y5=100

Y1 +5Y2 +20Y3 — Y6=300

Yi ≥0 (j=1,6)

В этой записи переменные Y4, Y5 и Y6 являются базисными, а Y1, Y2 и Y3 — свободными. В исходной задаче (2.6) — (2.8) переменные Х1 , Х2 и Х3 являются свободными, a Х4 , Х5 и Х6 — базисными.

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

Х4  Y1, Х5  Y2, Х6  Y3, Х1  Y4, Х2  Y5, Х3  Y6, (2.14)

Воспользуемся соответствием (2.14) следующим образом. Как видно, переменная Y1 связана с переменной Х4 (поэтому их называют двойственными переменными. Y1 соответствует Х4, а в табл.2.4 под Х4 в f- строке находится элемент 59 ,следовательно, Y1* = 59. Точно так же устанавливается, что Y2* = 40, Y3* = 2.05; Y4* = 0 ; Y5* = 0 ; Y6* = 0 .

Из теорем двойственности следует, что экстремальные значения целевых функций разрешимых двойственных задач совпадают, поэтому φ min = f max =572307.7

Двойственный симплекс-метод — Энциклопедия по экономике

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

В противном случае необходимо ввести новое отсечение на базе полученной таблицы и вновь воспользоваться двойственным симплекс-методом. Если на некоторой итерации при использовании двойственного симплекс-метода обнаружится отсутствие допустимого решения, то рассматриваемая задача не имеет допустимого целочисленного решения. [c.469]

Используя двойственный симплекс-метод, находят решение задачи, получающейся в результате присоединения дополнительного ограничения. [c.470]

Двойственный симплекс-метод. Начнем с анализа геометрической картины, связанной с задачей линейного программирования. На рис. 76 изображен (качественно) многогранник Р, причем одна ось — прямая е, в качестве второй оси на рис. 76 принято иг-мерное пространство. Граница Р состоит из т мерных граней (на рис. 76 они изображены отрезками). Каждая грань определяется вектором g, ортогональным данной грани. Мы будем считать этот вектор нормированным условием (g, е) = 1. Такие векторы определяют нижние грани Р, при нормировке (g, e) =—1 получим верхние. Это следует понимать так коль скоро задан вектор g, соответствующая ему грань определяется как совокупность точек х вида [c.426]

Заметим сразу же, что произвольному вектору g обычно соответствует вершина, т. е. нет ни одного индекса га, для которого С ) )—0. Однако при реализации двойственного симплекс-метода [c.427]

ДВОЙСТВЕННЫЙ СИМПЛЕКС- МЕТОД [c.68]

Основные идеи двойственного симплекс-метода. [c.68]

Здесь следует подчеркнуть, что двойственный симплекс-метод непосредственно нацелен на нахождение решения прямой задачи. [c.72]

По аналогии со стандартным симплекс-методом вычислительную процедуру двойственного симплекс-метода удобно оформлять в виде таблиц, приведенных на рис. 1.5. Очевидно, что с формальной стороны их структура остается неизменной. Иногда считается целесообразным добавить к двойственной симплекс-таблице строку, содержащую строку со значениями А,у, [c.74]

Таким образом, при решении задачи вида (1.66)-(1.68) двойственный симплекс-метод имеет несомненные преимущества по сравнению с прямым. [c.76]

Другое важное направление использования двойственного симплекс-метода связано с поиском оптимальных планов в тех задачах, условия которых претерпели некоторые изменения после того, как они уже были решены с помощью стандартной симплекс-процедуры. Типичными примерами таких изменений являются [c.76]

В первом случае, т. е. при изменении вектора 6, достоинства двойственного симплекс-метода очевидны, так как ранее найденный оптимальный базис можно использовать в качестве исходного сопряженного базиса при продолжении решения. Второй случай более подробно будет рассмотрен в гл. 4 при рассмотрении методов решения целочисленных задач. [c.76]

Двойственный симплекс-метод — метод последовательного уточнения оценок. [c.79]

Перечислите основные идеи, на которых базируется алгоритм двойственного симплекс-метода. [c.81]

Сформулируйте критерий оптимальности, используемый в алгоритме двойственного симплекс-метода. [c.81]

По каким признакам можно определить, что множество допустимых планов задачи, решаемой двойственным симплекс-методом, пусто [c. 81]

В каких ситуациях могут быть реализованы преимущества двойственного симплекс-метода [c.81]

В соответствии с алгоритмом двойственного симплекс-метода переходим к следующему базису Af(p(2 2)) = 0, 2, 3 . [c.149]

Для любой задачи линейного программирования можно сформулировать задачу-двойник, или, иначе, двойственную задачу. Эта задача-двойник является своеобразным «зеркальным отражением» исходной задачи, поскольку ее формулировка использует те же параметры, что и исходная задача, а ее решение может быть получено одновременно с решением исходной задачи. Фактически при решении исходной задачи симплекс-методом одновременно решается и двойственная задача, и наоборот. Следует также заметить, что исходная и двойственная задачи совершенно симметричны. Если двойственную задачу рассматривать как исходную, то исходная будет для нее двойственной. [c.65]

Перейдя к вектору — g, получим вторую точную грань Р, соответствующую данному набору индексов М. В настоящее время разработано большое число алгоритмов точного решения задачи Л. Все они объединяются общим термином симплекс-метод, однако различают прямые и двойственные варианты симплекс-метода. С этими двумя вариантами связаны две основные качественные идеи, в той или иной мере лежащие в основании большинства алгоритмов как точного, так и приближенного решения задачи линейного программирования. [c.419]

Симплекс-метод двойственный 426 [c.486]

Задачи линейного программирования (7.61 — 7.90) решите симплекс-методом и проведите анализ моделей на чувствительность, сформулируйте двойственную задачу к исходной и решите ее. [c.265]

Использование теоремы двойственности и связанного с ней признака оптимальности допустимого плана лежит в основе большинства эффективных методов решения задач линейного программирования. В 2 было продемонстрировано решение задачи о раскрое с помощью метода последовательного улучшения плана. Близко к нему примыкает симплекс-метод, разработанный американским математиком. Дж. Данцигом. Здесь мы приведем лишь краткое описание этого метода. [c.31]

Описанный вариант симплекс-метода не является единственным. На практике обычно употребляется более совершенный вариант — модифицированный симплекс-метод, связанный с использованием двойственной задачи (оценок) и по существу близкий к описанному выше методу последовательного улучшения плана. [c.35]

Таким образом, существенным преимуществом модифицированного симплекс-метода является то, что он позволяет одновременно найти оптимальные планы как прямой, так и двойственной задачи. [c.63]

В заключение отметим, что в настоящем параграфе был рассмотрен вариант двойственного алгоритма, соответствующий стандартному симплекс-методу. Нетрудно догадаться, что существует и вариант, построенный на базе модифицированного симплекса (схемы, связанной с преобразованием обратных матриц), но, поскольку этот вопрос представляет интерес в основном с точки зрения техники организации вычислений, мы на нем останавливаться не будем. При желании с глубоким и детальным описанием данной версии алгоритма можно ознакомиться в [1]. Отметим лишь, что она обладает теми же принципиальными преимуществами, что и модифицированный симплекс-метод. [c.77]

Понятие базисного множества и базисного решения. Допустимые и двойственно допустимые базисы. Общая схема последовательного улучшения, конкретизация для прямой и двойственной задачи в канонической несимметричной форме. Получение начального решения. Связь с симплекс методом. Проблема вырожденности. [c.47]

Двойственный симплекс-метод основан на том, что, исходя из некоторого вектора g, устраивают последовательные его повороты, причем каждый поворот (переход от g к g ) сопровождается ростом F (g). Этим обеспечивается сходимость g ->g , признаком того, что текущий вектор g уже есть g, служит невозможность его изменения. Однако, после того как встретилась неулучшаемая грань М, следует еще решить систему (т+1) линейных уравнений [c.428]

Непосредственное приложение теории двойственности к вычислительным алгоритмам линейного программирования позволило разработать еще один метод решения ЗЛП, получивший название двойственного симплекс-метода, или метода последовательного уточнения оценок. Впервые он был предложен Лемке в 1954 г. [c.68]

В процессе изложения идей, положенных в основу двойственного симплекс-метода, еще раз воспользуемся второй геометрической интерпретацией ЗЛП. Рассмотрим некоторую КЗЛП (1.48). На рис. 1.11 изображен конус К положительных линейных комбинаций расширенных векторов условий а1 для случая т = 2, п = 6, а на рис. 1.12 — (для большей наглядности) — поперечное сечение данного конуса некоторой плоскостью L, проходящей параллельно оси аппликат. [c.68]

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

Критерий оптимальности псевдоплана х в двойственном симплекс-методе заключается в том, что х одновременно должен являться допустимым планом прямой задачи, т. е. все его компоненты должны быть неотрицательны Ц>0). [c.71]

Таким образом, в двойственном симплекс-методе признаком отсутствия допустимых планов у решаемой КЗЛП является неотрицательность каких-либо r-х компонент во всех столбцах а1, представленных в текущем базисе р (аг/(р)>0, е п),если 6г(р)[c.72]

Алгоритм и табличная реализация двойственного симплекс-метода. Обобщая сказанное в предыдущем пункте, приведем в сжатом виде алгоритм двойственного симплекс-метода для решения КЗЛП. [c.73]

Особенности применения двойственного симплекс-метода. Алгоритм двойственного симплекс-метода (как и остальные симплекс-алгоритмы) предполагает знание исходного сопряженного базиса. Очевидно, что в общем случае его нахождение является достаточно непростой задачей, сводящей на нет потенциальные преимущества двойственного алгоритма. Однако в ряде случаев исходный псевдоплан может быть определен достаточно легко. [c.75]

Пример решения ЗЛП двойственным симплекс-методом. Рассмотрим на конкретном примере процесс решения КЗЛП двойственным симплекс-методом. Для этого, опять-таки, вернемся к задаче (1.34)-(1.35), решенной в п. 1.4.3 и п. 1.5.2. Предположим, что произошли изменения в векторе ограничений 6, в результате которых [c.77]

Поскольку в начальном псевдоплане имеется только одна отрицательная компонента (- 6с, ), то из базиса должен быть выведен соответствующий ей вектор an+l. Далее, следуя рекомендациям алгоритма двойственного симплекс-метода, находим оптимальный план. Если он не является целочисленным, то описанные действия итеративно повторяются. [c.147]

Двойственный симплекс-метод является основой для метода Гомори, так как он позволяет учитывать новые дополнительные ограничения (правильные отсечения) и переходить от текущего псевдоплана к новому оптимальному плану. [c.147]

Проведенные преобразования системы ограничений D q позволили явно выделить сопряженный базис, образуемый столбцами с номерами 1,. .., т, п+1, и соответствующий ему псевдоплан (alf. .., dm, 0,. .., О, 4dJ), т. е. для решения задачи (Д(симплекс-таблицы, показанному на рис. 4.5. [c.155]

Какую роль играет алгоритм двойственного симплекс-метода при решении целочисленной линейной задачи методом Гомори [c.157]

Как уже отмечалось, при решении симплекс-методом исходной задачи сразу же решается и двойственная. Если «Поиск решения» MS-Ex el получил решение задачи об оптимальном плане продукции, то он нашел и теневые цены ресурсов. Никаких дополнительных операций по решению двойственной задачи на практике делать не нужно. Полученные нами значения двойственных цен ресурсов мебельного цеха У, = 40 Y2 = 0 У3 = 60 можно найти в колонке «Теневые цены» таблицы «Ограничения» отчета об устойчивости для прямой задачи об оптимальном плане выпуска продукции (рис. 14). [c.75]

Если среди внебазисных переменных нет ни одной, которую можно проварьировать с убыванием л, это свидетельствует о том, что данное допустимое решение — оптимально. Этот факт нам будет удобно доказать несколько ниже, в связи с двойственным вариантом симплекс-метода. [c.422]

Описанный вариант симплекс-метода не является единственным. На практике обычно употребляется более совершенный вариант — модифицированный симплекс-метод, связанный с использованием двойственной задачи (о. о. оценок). Существуют и другие методы решения задач линейного программирования. Упомянем и коротко поясним один из них — метод блочного программирова- [c.42]

Связь матричных игр с линейным программированием и нахождение NEm. Доказательство Сл. 1.1 для антагонистических (матричных) игр двух лиц можно проводить и независимо от теоремы Нэша, через линейное программирование, что дает также способ поиска NEm для этих игр. Для этого задачу 1-го игрока записывают в форме максимизации (неизвестной ему заранее) цены игры //0 по переменным //о,/А при ограничениях ц, > О, Sf li/ = lr fJ-ak > ц0 (k = 1,…,п2), где ak e Rni — столбцы матрицы платежей (а ) = (MI(X ,X )). Здесь ограничения типа > выражают гипотезу 1-го о неблагоприятном поведении противника (максимин). Легко проверить, что задача противника есть двойственная к описанной задаче. Таким образом симплекс методом можно найти седловую пару в игре Gm, она является и Нэшевской парой. Для случая биматричной игры 2×2 также легко найти NEm графически, строя функции (или отображения) NRi(x i) отклика игроков на действия партнеров. [c.7]

Онлайн калькулятор: Dual Simplex

По результатам расчетов предыдущей итерации убираем из базы переменную x ₈ и ставим на ее место x ₂ . Все остальные ячейки остаются без изменений.

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

Остальные пустые ячейки, кроме строки оценок и столбца Q, вычисляются методом прямоугольника, относительно разрешающего элемента:

P ₁ = (P ₁ * x _4,2 ) — (x _1,2 * P ₄ ) / x _{4, 2} = ((600 * 2) — (1 * 150)) / 2 = 525;

Р ₂ = (Р ₂ * х _4,2 ) — (х _2,2 * Р ₄ ) / х _4,2 = (()-225 * ()-225 * 0 * 150)) / 2 = 225;

Р ₃ = (Р ₃ * х _4,2 ) — (х _3,2 * Р ₄ ) / х _4,2 = ((2) -000 4*150))/2=700;

P ₅ = (P ₅ * x _4,2 ) — (x _5,2 * P ₄ ) / x _4,2 = — (0 * 2) 0 * 150)) / 2 = 0;

х _1,1 = ((х _1,1 * х _4,2 ) — (х _1,2 * х _4,1 )) / х _4,2 = ((2 * 2) — (1 * 0)) / 2 = 2;

х _1,2 = ((х _1,2 * х _4,2 ) — (х _1,2 * х _4,2 )) / х _4,2 = ((1 * 2) — (1 * 2)) / 2 = 0;

х _1,4 = ((х _1,4 * х _4,2 ) — (х _1,2 * х _4,4 )) / х _4,2 = ((0 * 2) — (1 * 0)) / 2 = 0;

х _1,5 = ((х _1,5 * х _4,2 ) — (х _1,2 * х _4,5 )) / х _4,2 = ((0 * 2) — (1 * 0)) / 2 = 0;

х _1,6 = ((х _1,6 * х _4,2 ) — (х _1,2 * х _4,6 )) / х _4,2 = ((0 * 2) — (1 * -1)) / 2 = 0. 5;

х _1,7 = ((х _1,7 * х _4,2 ) — (х _1,2 * х _4,7 )) / х _4,2 = ((0 * 2) — (1 * 0)) / 2 = 0;

х _1,8 = ((х _1,8 * х _4,2 ) — (х _1,2 * х _4,8 )) / х _4,2 = ((0 * 2) — (1 * 1)) / 2 = -0,5;

х _1,9 = ((х _1,9 * х _4,2 ) — (х _1,2 * х _4,9 )) / х _4,2 = ((0 * 2) — (1 * 0)) / 2 = 0;

х _2,1 = ((х _2,1 * х _4,2 ) — (х _2,2 * х _4,1 )) / х _4,2 = ((0 * 2) — (0 * 0)) / 2 = 0;

х _2,2 = ((х _2,2 * х _4,2 ) — (х _2,2 * х _4,2 )) / х _4,2 = ((0 * 2) — (0 * 2)) / 2 = 0;

х _2,4 = ((х _2,4 * х _4,2 ) — (х _2,2 * х _4,4 )) / х _4,2 = ((1 * 2) — (0 * 0)) / 2 = 1;

х _2,5 = ((х _2,5 * х _4,2 ) — (х _2,2 * х _4,5 )) / х _4,2 = ((0 * 2) — (0 * 0)) / 2 = 0;

х _2,6 = ((х _2,6 * х _4,2 ) — (х _2,2 * х _4,6 )) / х _4,2 = ((0 * 2) — (0 * -1)) / 2 = 0;

х _2,7 = ((х _2,7 * х _4,2 ) — (х _2,2 * х _4,7 )) / х _4,2 = ((0 * 2) — (0 * 0)) / 2 = 0;

х _2,8 = ((х _2,8 * х _4,2 ) — (х _2,2 * х _4,8 )) / х _4,2 = ((0 * 2) — (0 * 1)) / 2 = 0;

х _2,9 = ((х _2,9 * х _4,2 ) — (х _2,2 * х _4,9 )) / х _4,2 = ((0 * 2) — (0 * 0)) / 2 = 0;

х _3,1 = ((х _3,1 * х _4,2 ) — (х _3,2 * х _4,1 )) / х _4,2 = ((5 * 2) — (4 * 0)) / 2 = 5;

х _3,2 = ((х _3,2 * х _4,2 ) — (х _3,2 * х _4,2 )) / х _4,2 = ((4*2) — (4*2))/2=0;

х _3,4 = ((х _3,4 * х _4,2 ) — (х _3,2 * х _4,4 )) / х _4,2 = ((0 * 2) — (4 * 0)) / 2 = 0;

х _3,5 = ((х _3,5 * х _4,2 ) — (х _3,2 * х _4,5 )) / х _4,2 = ((1 * 2) — (4 * 0)) / 2 = 1;

х _3,6 = ((х _3,6 * х _4,2 ) — (х _3,2 * х _4,6 )) / х _4,2 = ((0*2)-(4*-1))/2=2;

х _3,7 = ((х _3,7 * х _4,2 ) — (х _3,2 * х _4,7 )) / х _4,2 = ((0 * 2) — (4 * 0)) / 2 = 0;

х _3,8 = ((х _3,8 * х _4,2 ) — (х _3,2 * х _4,8 )) / х _4,2 = ((0 * 2) — (4 * 1)) / 2 = -2;

х _3,9 = ((х _3,9 * х _4,2 ) — (х _3,2 * х _4,9 )) / х _4,2 = ((0 * 2) — (4 * 0)) / 2 = 0;

х _5,1 = ((х _5,1 * х _4,2 ) — (х _5,2 * х _4,1 )) / х _4,2 = ((0 * 2) — (0 * 0)) / 2 = 0;

х _5,2 = ((х _5,2 * х _4,2 ) — (х _5,2 * х _4,2 )) / х _4,2 = ((0 * 2) — (0 * 2)) / 2 = 0;

х _5,4 = ((х _5,4 * х _4,2 ) — (х _5,2 * х _4,4 )) / х _4,2 = ((0 * 2) — (0 * 0)) / 2 = 0;

х _5,5 = ((х _5,5 * х _4,2 ) — (х _5,2 * х _4,5 )) / х _4,2 = ((0 * 2) — (0 * 0)) / 2 = 0;

х _5,6 = ((х _5,6 * х _4,2 ) — (х _5,2 * х _4,6 )) / х _4,2 = ((0 * 2) — (0 * -1)) / 2 = 0;

х _5,7 = ((х _5,7 * х _4,2 ) — (х _5,2 * х _4,7 )) / х _4,2 = ((-1 * 2) — (0 * 0)) / 2 = -1;

х _5,8 = ((х _5,8 * х _4,2 ) — (х _5,2 * х _4,8 )) / х _4,2 = ((0 * 2) — (0 * 1)) / 2 = 0;

х _5,9 = ((х _5,9 * х _4,2 ) — (х _5,2 * х _4,9 )) / х _4,2 = ((1 * 2) — (0 * 0)) / 2 = 1;

Вычислим значение целевой функции, поэлементно умножив столбец Cb на столбец P, сложив результаты произведений.

MAX _P = (CB ₁ * P ₁) + (CB ₁₁ * P ₂ + (CB ₂₁ * P ₃ + (CB ₃₁ * P ₄ + (Cb ₄₁ * P ₅ = (0 * 525) + (0 * 225) + (0 * 700) + (4 * 75) + (-М * 0) = 300;

Вычисляем оценки для каждой контролируемой переменной путем поэлементного умножения значения из столбца переменной на значение из столбца Cb, суммирования результатов произведений и вычитания из их суммы коэффициента целевой функции с этой переменной .

Макс. _{x ₁} = ((Cb ₁ * x _1,1 ) + (Cb ₂ * x _2,1 ) + (Cb 3 0 4 *

0 ) + (Cb ₄ * x _4,1 ) + (Cb ₅ * x _5,1 ) ) — k _{x ₁} = ((0 * 2) + (0 * 0) + (0 * 5) + (4 * 0) + (-М * 0)) — 3 = -3;

Макс. _{x ₂} = ((Cb ₁ * x _1,2 ) + (Cb ₂ * x _2,2 ) + 3 0 4 *

3 ) + (Cb ₄ * x _4,2 ) + (Cb ₅ * x _5,2 ) ) — k _{x ₂} = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 1) + (-М * 0)) — 4 = 0;

Макс. _{x ₃} = ((Cb ₁ * x _1,3 ) + (Cb ₂ * x _2,3 ) + 3 0 4 *

3 ) + (Cb ₄ * x _4,3 ) + (Cb ₅ * x _5,3 ) ) — k _{x ₃} = ((0 * 1) + (0 * 0) + (0 * 0) + (4 * 0) + (-М * 0)) — 0 = 0;

Макс. _{x ₄} = ((Cb ₁ * x _1,4 ) + (Cb ₂ * x _2,4 ) + (Cb 3 0 4 *

3 ) + (Cb ₄ * x _4,4 ) + (Cb ₅ * x _5,4 ) ) — k _{x ₄} = ((0 * 0) + (0 * 1) + (0 * 0) + (4 * 0) + (-М * 0)) — 0 = 0;

Max _{x ₅} = ((Cb ₁ * x _1,5 ) + (Cb ₂ * x _2,5 ) + (Cb 3 0 4 *

0 ) + (Cb ₄ * x _4,5 ) + (Cb ₅ * x _5,5 ) ) — k _{x ₅} = ((0 * 0) + (0 * 0) + (0 * 1) + (4 * 0) + (-М * 0)) — 0 = 0;

Max _{x ₆} = ((Cb ₁ * x _1,6 ) + (Cb ₂ * x _2,6 ) + (Cb 3 0 4 *

0 ) + (Cb ₄ * x _4,6 ) + (Cb ₅ * x _5,6 ) ) — k _{x ₆} = ((0 * 0.

5) + (0 * 0) + (0 * 2) + (4 * -0,5) + (-М * 0)) — 0 = -2;

Max _{x ₇} = ((Cb ₁ * x _1,7 ) + (Cb ₂ * x _2,7 ) + (Cb 3 0 4

0 ) + (Cb ₄ * x _4,7 ) + (Cb ₅ * x _5,7 ) ) — k _{x ₇} = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 0) + (-М * -1)) — 0 = М;

Макс. _{x ₈} = ((Cb ₁ * x _1,8 ) + (Cb ₂ * x _2,8 ) + (Cb 3 4 *

3 ) + (Cb ₄ * x _4,8 ) + (Cb ₅ * x _5,8 ) ) — k _{x ₈} = ((0 * -0.

5) + (0 * 0) + (0 * -2) + (4 * 0,5) + (-М * 0)) — -М = М+2;

Макс. _{x ₉} = ((Cb ₁ * x _1,9 ) + (Cb ₂ * x _2,9 ) + (Cb 3 0 4 *

0 ) + (Cb ₄ * x _4,9 ) + (Cb ₅ * x _5,9 ) ) — k _{x ₉} = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 0) + (-М * 1)) — -М = 0;

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

Количество переменных в базе всегда постоянно, поэтому необходимо выбрать, какую переменную вывести из базы, для которой вычисляем Q.

Элементы столбца Q вычисляются делением значений из столбец P на значение из столбца, соответствующего переменной, которая занесена в базу:

Выводим из базы переменную с наименьшим положительным значением Q.

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

Эгвальд Исследование операций — Линейное программирование

Исследование операций — Линейное программирование — Генератор двойных симплексных таблиц

Элмер Г. Винс

Популярные веб-страницы Egwald предоставляются пользователям бесплатно.
Поддержите нас, присоединившись к Egwald Web Services в качестве поклонника Facebook:
Подпишитесь на Элмера Винса в Твиттере:

пример задачи | твой л. п. проблема | симплексный алгоритм | использованная литература

Метод двойного симплекса преобразует исходную таблицу в конечную таблицу, содержащую решения прямой и двойственной задач.Каждый этап алгоритма генерирует промежуточную таблицу по мере того, как алгоритм нащупывает решение.

Эта веб-страница позволяет вам ввести свою собственную задачу линейного программирования и создать эти таблицы с помощью удобного для пользователя интерфейса. Вы можете указать до 6 переменных и 10 ограничений в основной задаче с любым сочетанием ограничений = и =.

Чтобы проиллюстрировать процедуру, которую необходимо выполнить, рассмотрим задачу:

Основная линейная программа
Максимизируйте целевую функцию (P)
P = 15 х ₁ + 10 х ₂ + 17 х ₃ с учетом
Л1: 1.0 х ₁ + 1,0 х ₂ + 1,0 х ₃ L2: 1,25 x ₁ + 0,5 x ₂ + 1,0 x ₃ >= 90
L3: 0,6 х ₁ + 1,0 х ₂ + 0,5 х ₃ = 55
х ₁ >= 0; х ₂ >= 0; x ₃ >= 0

с диаграммой:

Для создания формы, используемой для входа в л. п. данные вы должны установить параметры, которые определяют ваш л.п. проблема, как я сделал ниже для проблемы выше.

После того, как вы заполните форму и нажмете «Отправить параметры», откроется веб-страница с таблицей, подобной приведенной ниже, где вы можете ввести данные своего l.p. проблема. Обратите внимание, что вам не нужно ни умножать = constrainst на -1, ни преобразовывать >= ограничения в Таблица форм =

После того, как вы введете свои данные и нажмете кнопку «Отправить», программа автоматически рассчитает последовательность таблиц, которая решает прямую и двойную l.п. проблемы. Изучите следующие таблицы, чтобы увидеть, как метод двойного симплекса работает над поиском решения.

Чтобы выполнить анализ чувствительности вашей задачи линейного программирования, измените данные в таблице выше и нажмите Submit L.P. еще раз.

Двойной симплексный алгоритм.

Стандартная форма исходной двойной симплексной таблицы:

-C ^T

Начальный Cableau


0
o	o ₃ ^T

Двойной симплекс последовательность картинок. Таблица ^k имеет вид:

после объединения центрального 2 на 2 блока матриц.

«трехфазный метод» двойного симплексного алгоритма :

Фаза 0 — свести все искусственные переменные (связанные с = ограничениями) к нулю, т.е. исключить их из базы;

Фаза I — найти таблицу с Ø >= 0, т.е. допустимую двойную программу;

Фаза II — генерировать таблицы, которые уменьшают значение µ, превращая ß >= 0, без возврата к Фазе 0 или I, т.е.е. найти допустимую базовую двойственную программу, минимизирующую целевую функцию D.

Фаза 0: Вывести искусственные переменные из основы.

+ 91 049 -91,75 3

Таблица ⁰
	б ⁰	х ⁰ ₁	х ⁰ ₂	х ⁰ ₃	с ⁰ ₁	с ⁰ ₂	с* ⁰ ₃	строки сум
л ⁰ ₁	85	1	1	1	1	0	0	89
л ⁰ ₂	-90	-1. 25		-0,5 -1	0		1 0
л девяносто одна тысяча семьдесят три ⁰	55	0,6	1		0,5 0	0		1 58,1
Р 0		0 -15 -10			-17 0 0			0 -42
	0	0	0	0	0	0	0	0	0	0	0

Основа для Tableau ⁰: [S ₁, S ₂, S ₃,]. Значение целевой функции = 0,

Перейти к следующей таблице следующим образом:

Фаза 0: Вывести искусственные переменные из основы.

А. В таблице ⁰ :

1. Выбрать искусственную переменную в базе: s ^* ₃ . Сводная строка = 3.

2. Выбрать ненулевой элемент в строке L ₃ как стержень: Û _3,2 = 1. Сводной столбец = 2.

B. Для создания таблицы ¹ :

3. Вычислить строку L ¹ ₃ = L ⁰ ₃ / (1).

4. Вычтите кратные строки L ¹ ₃ из всех остальных строк таблицы ⁰ так, чтобы x ¹ ₂ = e 9,2 ₃

в таблице

Фаза I: Цель: получить Ø >= 0.

Таблица ¹
	б ¹	x ¹ ₁	x ¹ ₂	x ¹ ₃	с ¹ ₁	с ¹ ₂	с* ¹ ₃	ROW SUM
L ¹ ¹ 1 = L ^{0 = L ⁰ ₁ — (1) * L ¹ ₃}	30	0. 4	0	0	0	0 9	1	0	-1	-1	30.9
L ¹ ₂ = L ⁰ ₂ — (-0.5) * L ¹ ₃	-62.5	-62.5		-0988	-098 9	0	-0.75	0	1	0. 5	-62.7
L ¹ ₃ = L ⁰ ₃ / (1)	55	0.6	1	1	0	0	0	0	1	58.1 9088	58.1
P ¹ = P ⁰ — (-10) * L ¹ ₃	550	550	550	550	550	550	550	550	-9	0	0	-12	0	0	10	539
-PR ¹ / L ¹ ₃	0	15	0	24	0	0	0	0	0	0

Основа для Tableau ¹: [S ₁, S ₂, X ₂,]. Значение целевой функции = 550,

Перейти к следующей таблице следующим образом:

Фаза 0: Завершена.

Этап I: Цель: получить Ø >= 0.

A. В таблице ¹ :

1. Выберите целевой столбец , tcol, с Ø _tcol 1 ₁ = -9, tcol = 1.

2. Выберите любую строку r с положительной записью в tcol = 1 в качестве сводной строки : строка = 3, связанная с Û _3,1 = 0.6 и ограничение L ₃ .

3. Рассчитайте отношения -Ø / L ₃ согласно последней строке. Отбросьте коэффициенты, которые не являются положительными, и коэффициенты, связанные с искусственными переменными. Выберите столбец с наименьшим положительным отношением в качестве опорного столбца : столбец = 1, связанный с 15. Таким образом, х _3,1 = 0,6 является опорным ; переменная x ₂ уйдет из базы; переменная x ₁ войдет в основу.

Б.Для создания таблицы ² :

4. Вычислить строку L ² ₃ = L ¹ ₃ / (0,6).

5. Вычтите кратные строки L ² ₃ из всех остальных строк Таблицы ¹ так, что x ₁ = e ₃ в Таблице ².

1,583 29,292 0,833 +

Таблица ²
	б ²	x ² ₁	x ² ₂	x ² ₃	с ² ₁	с ² ₂	с* ² ₃	ряд сумма
л ² ₁ = л ¹ ₁ — (0. 4) * L ² ₃		-6,667 0		-0,667 0,167		1 0		-1,667 -7,833
^{2 л} 2 = L ¹ ₂ — (-0,95) * L ² ₃		24,583 0		0,042	0		1 2,083
^{л 2} ₃ = L ¹ ₃ / (0. 6)		91,667 1	1,667			0 0		1,667 96,833
Р девяносто одна тысяча сорок девять ² = Р ¹ — (-9) * L ² ₃	1375	0	15	15	-4.5 9 9088 9	0	0	25	1410.5 9
-PR ² / L ² ₃	0	0	0	5. 4	0	0	0	0	0	0	0

Основа для Tableau ²: [S ₁, S ₂, X ₁,]. Значение целевой функции = 1375,

Перейти к следующей таблице следующим образом:

Фаза 0: Завершена.

Этап I: Цель: получить Ø >= 0.

A. В таблице ² :

1. Выберите целевой столбец , tcol, с Ø _tcol 2 ₃ = -4.5, tкол = 3,

2. Выберите любую строку r с положительной записью в tcol = 3 в качестве опорной строки : строка = 3, связанная с Û _3,3 = 0,833 и ограничением L ₃ .

3. Рассчитайте отношения -Ø / L ₃ согласно последней строке. Отбросьте коэффициенты, которые не являются положительными, и коэффициенты, связанные с искусственными переменными. Выберите столбец с наименьшим положительным соотношением в качестве сводного столбца : столбцов = 3, связанных с 5.4. Таким образом, х _3,3 = 0,833 является осью ; переменная x ₁ уйдет из базы; переменная x ₃ войдет в основу.

B. Для создания таблицы ³ :

4. Вычислить строку L ³ ₃ = L ² ₃ / (0,833).

5. Вычтите кратные строки L ³ ₃ из всех остальных строк Таблицы ² так, что x ₃ = e ₃ в Таблице ³.

Фаза II: Цель: получить ß >= 0.

-0.2 -1 9 0

Таблица ³
	б ³	x ³ ₁	x ³ ₂	x ³ ₃	с ³ ₁	с ³ ₂	с* ³ ₃	ряд сумма
л ³ ₁ = л ² ₁ — (0. 167) * L ³ 3	-25	-0.2	0	1	0	-2	-27.2
L ³ ₂ = L ² ² ₂ — (0,042) * L ³ ₃	20	-0.05	1,5	0	0	1	2	24.45
9 ³ ₃ = L ² ₃ / (0. 833)	110	1 2	2	2	0	0	0	2	116.2
P ³ = P ² — (-4.5) * L ³ ₃	1870888	1870	5	5.4	0	0	0	0	3	1933. 4
-PR ³ / L ³ ₁	0	27	27	24	0	0	0	0	0	0	0	0

Основа для Tableau ³: [S ₁, S ₂, X ₃,].Значение целевой функции = 1870,

Перейти к следующей таблице следующим образом:

Фаза 0: Завершена.

Фаза I: Завершена.

Этап II: Цель: получить ß >= 0.

А. В таблице ³ :

1. Выберите сводную строку , строку, с помощью b ³ _строку 3 ₁ = -25.

2. Рассчитайте отношения -Ø / L ₁ согласно последней строке.Отбросьте коэффициенты, которые не являются положительными, и коэффициенты, связанные с искусственными переменными. Выберите столбец с наименьшим положительным отношением в качестве опорного столбца : col = 2, связанный с 24. Таким образом, Û _1,2 = -1 является опорным ; переменная s ₁ уйдет из базы; переменная x ₂ войдет в основу.

B. Для создания таблицы ⁴ :

3. Вычислить строку L ⁴ ₁ = L ³ ₁ / (-1).

4. Вычтите кратные строки L ⁴ ₁ из всех остальных строк Таблицы ³ так, чтобы x ₂ = e ₁ в Таблице ⁴.

Таблица ⁴
	б ⁴	x ⁴ ₁	x ⁴ ₂	x ⁴ ₃	с ⁴ ₁	с ⁴ ₂	с* ⁴ ₃	ряд сумма
L ⁴ ₁ = L ³ ₁ / (-1)	25 _0,0.2	1	1	0	-1	-1	2	2	2 9
L ⁴ ₂ = L ³ ₂ — (1. 5) * L ⁴ ₁	-17.5	-17.5	-0.35	0	0	1.5	1	-1	-1	-16.35
L ⁴ ₃ = L ^{3 — ( 2) * L ⁴ ₁}	60	0.8	0	0	2	2	0	-2	-2	— 2	61. 8
P ⁴ = P ³ — (24) * L ⁴ ₁	1270	0,6		0 0	24	0		-14 1280,6
^{4 -P} / л ⁴ ₂	0		1,714 0 0		0	0	0	0	0	0

Основа для Cableau ⁴: [x ₂, S ₂, x ₃,]. Значение целевой функции = 1270,

Перейти к следующей таблице следующим образом:

Фаза 0: Завершена.

Фаза I: Завершена.

Этап II: Цель: получить ß >= 0.

А. В таблице ⁴ :

1. Выберите сводную строку , строку, с помощью b ⁴ _строку 4 ₂ = -17,5.

2. Рассчитайте отношения -Ø / L ₂ согласно последней строке.Отбросьте коэффициенты, которые не являются положительными, и коэффициенты, связанные с искусственными переменными. Выберите столбец с наименьшим положительным соотношением в качестве сводного столбца : столбцов = 1, связанных с 1,714. Таким образом, х _2,1 = -0,35 является точкой опоры ; переменная s ₂ уйдет из базы; переменная x ₁ войдет в основу.

B. Для создания таблицы ⁵ :

3. Вычислить строку L ⁵ ₂ = L ⁴ ₂ / (-0. 35).

4. Вычтите кратные строки L ⁵ ₂ из всех остальных строк Таблицы ⁴ так, чтобы x ₁ = e ₂ в Таблице ⁵.

Таблица ⁵
	б ⁵	x ⁵ ₁	x ⁵ ₂	x ⁵ ₃	с ⁵ ₁	с ⁵ ₂	с* ⁵ ₃	ряд сумма
л ⁵ ₁ = л ⁴ ₁ — (0. 2) * l ⁵ 2	15	0	1	0	-0.143	0.571	1.429	17.857	17.857
L ⁵ ₂ = L ⁴ ₂ / (-0.35)	50	50	0	0	0	-4.286 _{_{-2 -2.857}}	2,857	46. 714
L ⁵ ₃ = L ⁴ ₃ — (0.8) * L ⁵ 2	20	0	0	1	5	5.429	2.286	—4.286	24.429
P ⁴ = P ⁴ — ( 0,6) * L 5	1240		0 0	0		26,571 1,714		-15,714 1252,571
^{-P 5} / л ⁵ _-1	0	0	0	0	0	0	0	0	0

основы для Tableau ⁵: [X ₂, X ₁, X ₃ , ]. Значение целевой функции = 1240,

Фаза 0: Завершена.

Фаза I: Завершена.

Фаза II: Завершена.

Первичный раствор: [x ₂, x ₁, x ₃, ] = [15, 50, 20, ]; Р = 1240.

(Первичные переменные x, не входящие в базис, имеют значение 0).

Двойное решение: [y ₁, y ₂, y ₃, ] = [26,571, 1,714, -15,714, ]; Д = 1240.

Конец двойного симплексного метода линейного программирования

Справочник по линейному программированию.

Рестрепо, Родриго А. Теория игр и программирование: конспект лекций по математике . Ванкувер: Университет Британской Колумбии, 1967.
Рестрепо, Родриго А. Линейное программирование и дополнительность. Ванкувер: Университет Британской Колумбии, 1994.
Таха, Хамди А. Исследование операций: введение. 2-е издание . Нью-Йорк: Макмиллан, 1976.
Ву, Неса и Ричард Коппинс. Линейное программирование и расширения. Нью-Йорк: Макгроу-Хилл, 1981.

Решатель симплексного метода

Эта веб-страница, по сути, просто решает указанную линейную программу с использованием симплекс-метода и показывает ее полную работу. Задача может быть представлена в канонической матричной форме (с резервными переменными) или в нематричной форме.

Матричная форма

Каноническая форма матрицы: Различные матрицы могут быть введены с использованием нотации MATLAB. В случае $A$ точки с запятой используются для разделения строк и запятые или пробелы для разделения отдельных элементов строки. $\mathbf{b}$, $\mathbf{c}$, $\mathbf{x}$ и $x_{\mathbf{B}}$ могут иметь отдельные элементы, разделенные запятыми, точки с запятой или пробелы.

Нематричная форма

Задачи также можно вводить в более обычном формате в последнее текстовое поле на этой веб-странице.Если вы хотите это сделать, вы должны отметить кружок рядом с «Использовать нематричный формат?» перед нажатием «Нажмите, чтобы решить проблему». Если вы решаете двойную задачу, хотите, чтобы этот факт упоминался в тексте статьи, и вы хотите, чтобы использовались разные имена двойных переменных, нажмите «Решить двойную?» кнопка.

В текстовом поле >= или ≥ используется для обозначения «больше или равно»,

«Максимизировать», «Максимизировать» или «Максимум» (без учета регистра) можно использовать для обозначения проблемы максимизации, в то время как «Минимизировать», «Минимизировать» или «Min» (без учета регистра) можно использовать, чтобы указать, что это проблема минимизации.

Предполагается неотрицательность ограничений (и нужно ли указывать , а не ).

Вы можете включить фразу «При условии» или «st. » (с двоеточием или без него) в новой строке перед указанием структурных ограничений, но вам нужно сделать , а не .

Запятые и точки нельзя использовать в качестве разделителей тысяч. Для обозначения десятичного разряда используется точка.

Дробные коэффициенты должны стоять перед переменной, к которой они относятся.Например:

                5/6x1

нормально, как и 5/6 x1 , но:

                5x1/6

будет не правильно прочитан.

Все переменные решения должны появляться в целевой функции, даже если они просто умножаются на 0. В ограничениях не обязательно должны появляться все переменные решения.

Анализ чувствительности

Для этой веб-страницы анализ чувствительности всегда использует ввод в матричном разделе формы.Он предполагает, что целевая функция называется «z» и цель состоит в том, чтобы максимизировать ее, поэтому, если ваша первоначальная задача была задачей минимизации, вы должны умножить любой результат, который она дает, на -1, чтобы вернуть ответ к правильному знаку.

Добавить ограничения

Чтобы добавить новые ограничения к задаче после ее первого решения, вы должны заменить запись для $A$ новой строкой(ами) для $A$, соответствующей этим новым ограничениям. Вы также должны заменить $\mathbf{b}$ новыми элементами, которые будут добавлены к задаче.Затем, наконец, щелкните кружок рядом с « Добавить ограничение(я)? » и нажмите кнопку «Нажмите, чтобы решить проблему».

Добавить переменные

Чтобы добавить новые переменные в задачу после того, как исходная задача была решена, просто замените $A$, $\mathbf{b}$, $\mathbf{c}$ и $\mathbf {x}$ с тем, что к ним нужно добавить, затем щелкните кружок рядом с « Новая переменная(ы)? » и нажмите кнопку «Нажмите, чтобы решить проблему».

Изменить коэффициент(ы) ограничений

Чтобы изменить коэффициент(ы) ограничения после того, как решатель решил исходную задачу, просто измените соответствующие записи в $\mathbf{A}$ (помня, что анализ чувствительности может быть выполнен только для коэффициентов неосновных переменных), затем щелкните кружок рядом с « Constraint LHS change? » и нажмите кнопку «Нажмите, чтобы решить проблему».

Изменить коэффициент(ы) целевой функции

Чтобы изменить коэффициент(ы) целевой функции после того, как решатель решил исходную задачу, просто измените соответствующие записи в $\mathbf{c}$, щелкните кружок слева от » Изменить коэффициент(ы) целевой функции? » и нажмите кнопку «Нажмите, чтобы решить проблему».

Изменение ресурса

Чтобы изменить значение (я) ресурса (значения $\mathbf{b}$) после того, как решатель решил исходную задачу, просто измените соответствующие записи в $\mathbf{b}$, щелкните кружок рядом с » Изменение ресурса? » и нажмите кнопку «Нажмите, чтобы решить проблему».

Пример по умолчанию

На этой веб-странице используется следующий пример по умолчанию: чтобы проиллюстрировать, как задачи должны вводиться в обе формы. Нажмите, чтобы решить проблему Удалить картины

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

В этом разделе представлены разработка и реализация параллельной двойного симплекс-метода pami. Он расширяет схему субоптимизации Розандера [21], включая (последовательные) алгоритмические методы и используя параллелизм в нескольких итерациях.

Понятие пами было введено Холлом и Хуанфу [9], где оно упоминалось как ParISS. Этот прототип реализации был основан на обновлении PF и был относительно простым как в алгоритмическом, так и в вычислительном отношении. Последующие изменения и уточнения, включающие передовые алгоритмические методы, изложенные в разд. 2, а также обновления FT и некоторые новые функции, представленные в этом разделе, привели к гораздо более сложной и эффективной реализации. В частности, наша реализация pami превосходит ParISS почти на порядок в последовательном режиме и для достижения ускорения, продемонстрированного в разд.5 потребовал новых уровней параллелизма задач и методов параллельного алгоритмического управления, описанных в разд. 3.2 и 3.3, в дополнение к методам линейной алгебры, введенным Хуангфу и Холлом в [16].

Раздел 3.1 содержит обзор схемы распараллеливания pami и раздела 3. 1. 3.2 подробно описывается задача параллельных операций ftran на этапе основного обновления и способы ее упрощения. В разд. 3.3.

Обзор инфраструктуры pami

В этом разделе подробно описана общая схема распараллеливания pami со ссылкой на структуру субоптимизации, представленную в разд.2.3.

Основной тест оптимальности

Основной тест оптимальности включает только основные операции chuzr, в которых из кандидатов выбираются (если возможно) с использованием структуры DSE. В pami значение s — это количество используемых процессоров. Это векторная операция, которую можно легко распараллелить, хотя ее общая вычислительная стоимость невелика, поскольку она выполняется только один раз для каждой основной операции. Тем не менее, алгоритмический дизайн chuzr важен, и разд.3.3 обсуждает это подробно.

Второстепенная инициализация

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

Второстепенные итерации

В второстепенных итерациях есть три основные операции.

(а)
Младший чузр просто выбирает лучших кандидатов из множества ${\mathcal {P}}$.Поскольку это тривиально с вычислительной точки зрения, использование параллелизма не рассматривается. Однако следует учитывать вероятность того, что привлекательность лучшего оставшегося кандидата в ${\mathcal {P}}$ значительно снизилась. В таких обстоятельствах может быть нежелательно, чтобы эта переменная покидала базис. Это соображение приводит к возможной схеме контроля качества, представленной в разд. 3.3.
(б)
Тест второстепенного отношения является основным источником распараллеливания и повышения производительности. Поскольку результат btran известен (см. ниже), тест минорного соотношения состоит из spmv, chuzc1 и chuzc2. Операция spmv представляет собой произведение разреженной матрицы на вектор, а chuzc1 — выборку за один проход, основанную на результате spmv. В реальной реализации они могут совместно использовать одну параллельную инициализацию. С другой стороны, chuzc2 часто включает несколько итераций рекурсивного выбора, что при использовании параллелизма требует многих операций синхронизации. Согласно профилированию компонентов в таблице 1, chuzc2 является относительно дешевой операцией, поэтому в pami она не распараллеливается.Параллелизм данных используется в spmv и chuzc1 путем разделения переменных между процессорами перед выполнением любых симплексных итераций. Это делается случайным образом с целью достижения баланса нагрузки в spmv.
(с)
Незначительное обновление состоит из обновления двойных переменных и обновления результатов btran. Первое выполняется в второстепенном обновлении, потому что двойные переменные требуются в тесте отношения следующей второстепенной итерации.{-1}\) дает векторную операцию, которую можно распараллелить. После того, как результаты btran были обновлены, веса DSE оставшихся кандидатов пересчитываются напрямую с небольшими затратами.

Основное обновление

После t второстепенных итераций этап основного обновления завершает основную итерацию. Он состоит из трех типов операций: до 3 t операций ftran (включая ftran-dse и ftran-bfrt), векторное обновление первичных переменных и весов DSE и обновление базисного обратного представления.{-1} \widehat{{{\varvec{e}}}}_p\}} — это параллельные операции с векторными данными.

Обновление обратимого представления B выполняется с использованием коллективного обновления FT, за исключением случаев, когда желательно или необходимо выполнить инвертирование для повторного инвертирования B . Обратите внимание, что обе эти операции выполняются последовательно. Хотя (коллективное) обновление FT является относительно дешевым (см. Таблицу 1) и поэтому мало влияет на производительность, во время последовательного инвертирования происходит значительное бездействие процессора.{-1}\) и преобразования PF называются обратной и обновляемой частями соответственно. Множественные обратные части легко организовать как задачу параллельного вычисления. Часть обновления обычных операций ftran требует результатов других систем переадресации в той же группе и, таким образом, не может выполняться как параллельные вычисления задачи. Однако возможно и полезно использовать параллелизм данных при применении отдельных обновлений PF, когда $\widehat{{{\varvec{a}}}}_{q_i}$ большой и плотный. Для группы ftran-dse можно полностью использовать параллелизм задач, если эта группа вычислений выполняется после обычного ftran.Однако при реализации pami как ftran-dse, так и обычный ftran выполняются вместе, чтобы увеличить количество независимых обратных частей в интересах балансировки нагрузки.

Группа до т линейных систем, связанных с BFRT, немного отличается от двух других групп систем. Во-первых, может быть что-то от нуля до – линейных систем в зависимости от того, сколько второстепенных итераций связано с фактическими переворотами границы. Что еще более важно, результаты используются только для обновления значений основных переменных ${{\varvec{x}}}_{\scriptscriptstyle B}$ путем простого сложения векторов.{-1}\) применяется к объединенному результату. Этот подход значительно снижает общую стоимость последовательного решения систем прямой линейной логики, связанных с BFRT. Дополнительным преимуществом этой комбинации является то, что основная операция обновления также сводится к одной операции после комбинированной операции ftran-bfrt.

Путем объединения нескольких потенциальных операций ftran-bfrt в одну количество решаемых прямых линейных систем сокращается до $2t + 1$, или 2 t , когда не выполняются перевороты границ.Дополнительным преимуществом этого сокращения является то, что при $t\le s-1$ общее количество решаемых систем прямого линейного уравнения меньше, чем 2 s , так что каждый из s процессоров будет решать не более двух линейных систем. Однако, когда $t = s$ и ftran-bfrt нетривиальны, один из процессоров s требуется для решения трех линейных систем, а другим процессорам назначаются только две, что приводит к «сиротской задаче». Чтобы избежать этой ситуации, количество второстепенных итераций ограничено до $t = s-1$, если в предыдущих $s-2$ итерациях были выполнены связанные перевороты.

Схема выполнения параллельных операций ftran, рассмотренных выше, показана на рис. 1. В реальной реализации операции $2t + 1$ ftran запускаются одновременно с параллельными задачами, а процессоры решить, какие из них выполнять.

Рис. 1

Задача параллельная схема всех операций ftran в пами

Кандидатская настойчивость и контроль качества в чузр

Старший чузр формирует множество ${\mathcal {P}}$, а младший чузр выбирает из него кандидатов.Конструкция chuzr вносит значительный вклад в последовательную эффективность схем субоптимизации, поэтому заслуживает тщательного обсуждения.

При выполнении субоптимизации кандидат, выбранный для выхода из базиса в первой второстепенной итерации, совпадает с тем, который был бы выбран без субоптимизации. После этого кандидаты, оставшиеся в ${\mathcal {P}}$, могут быть менее привлекательными, чем наиболее привлекательные из кандидатов, не входящих в ${\mathcal {P}}$, из-за того, что первые становятся менее привлекательными и/ или последний становится более привлекательным.Действительно, некоторые кандидаты в ${\mathcal {P}}$ могут стать непривлекательными. Если кандидаты в исходном ${\mathcal {P}}$ не попадают в базу, то работа их операций btran (и любых последующих обновлений) тратится впустую. Однако, если второстепенные итерации выбирают менее привлекательных кандидатов для ухода из базы, можно ожидать, что количество симплексных итераций, необходимых для решения данной проблемы ЛП, увеличится. Решение этой проблемы сохраняемости кандидатов является ключевой алгоритмической проблемой при реализации субоптимизации. Необходимо определить количество кандидатов в исходном наборе ${\mathcal {P}}$ и определить стратегию для оценки того, должен ли конкретный кандидат оставаться в ${\mathcal {P}}$.

Для балансировки нагрузки во время дополнительной инициализации начальное количество кандидатов $s=|{\mathcal {P}}|$ должно быть целым числом, кратным количеству используемых процессоров. Множественные числа, превышающие единицу, обеспечивают лучший баланс нагрузки из-за большего объема работы, которую нужно распараллелить, особенно до и после второстепенных итераций, но практический опыт с прототипами pami ясно показал, что это более чем компенсируется объемом ненужных вычислений и увеличением в количестве итераций, необходимых для решения задачи.i, \end{aligned}$$

, тогда индекс p удаляется из ${\mathcal {P}}$. Ясно, что если переменная становится приемлемой или непривлекательной ($\alpha _p\le 0$) тогда она отбрасывается независимо от значения $\psi $.

Чтобы определить значение $\psi $ для использования в пами, была проведена серия экспериментов с использованием эталонного набора из 30 задач LP, приведенных в таблице 3 раздела. 5.1, с коэффициентами отсечки от 1,001 до 0,01. Результаты вычислений представлены в таблице 2, в которой указан (геометрический) средний коэффициент ускорения и количество задач, для которых коэффициент ускорения равен 1 соответственно.6, 1.8 и 2.0.

Таблица 2. Эксперименты с различными пороговыми значениями для контроля качества кандидатов в pami

Коэффициент отсечения $\psi = 1,001$ соответствует особой ситуации, когда выбираются только кандидаты, связанные с повышенной привлекательностью. Как и следовало ожидать, ускорение при таком значении $\psi $ оставляет желать лучшего. Коэффициент отсечения $\psi = 0,999$ соответствует пограничной ситуации, когда кандидаты, чья привлекательность снижается, отбрасываются.Достигнуто среднее ускорение 1,52.

Для различных коэффициентов отсечки в диапазоне $0,9 \le \psi \le 0,999$ нет реальной разницы в производительности pami: среднее ускорение и большее ускорение относительно стабильны. Начиная с $\psi = 0,9$, уменьшение коэффициента отсечки приводит к явному уменьшению среднего ускорения, хотя большее ускорение остается стабильным до $\psi = 0,5$.

Таким образом, эксперименты показывают, что любое значение в интервале [0,9, 0.999].

Сверхразреженные задачи LP

В обсуждениях выше при использовании параллелизма данных в векторных операциях предполагается, что для большинства компонентов вектора должно быть выполнено одно независимое скалярное вычисление. Например, в update-dual и update-primal кратный компонент добавляется к соответствующему компоненту другого вектора. В chuzr и chuzc1 компонент (если он не равен нулю) используется для вычисления и последующего сравнения соотношения.Поскольку эти скалярные вычисления не нужно выполнять для нулевых компонентов вектора, когда проблема LP демонстрирует гиперразреженность, это используется в эффективных последовательных реализациях [13]. Когда стоимость последовательной векторной операции снижается таким образом, использование параллелизма данных становится неэффективным, поэтому, когда плотность вектора ниже определенного порога, pami возвращается к последовательным вычислениям. Производительность pami не чувствительна к используемым пороговым значениям 5–10%.

Двойной симплексный метод.Это часть курса… | Родион Чачура

Это часть курса «Оптимизация для программистов».

Репозиторий GitHub с исходным кодом

В предыдущих частях мы рассмотрели симплекс-метод для решения линейных программ, и это не единственный алгоритм. За прошедшие годы были предложены десятки различных алгоритмов линейного программирования, например, метод эллипсоидов и вся группа из методов внутренних точек .

Несколько других алгоритмов, тесно связанных с симплекс-методом, также используются для линейного программирования.В этой части мы рассмотрим двойной симплексный метод . Его можно грубо описать как симплекс-метод, примененный к двойной линейной программе. Но прежде чем мы углубимся в метод двойного симплекса, мы должны понять, что такое двойная линейная программа.

Рассмотрим линейную программу.

С самого начала мы видим, что максимум целевой функции не превышает 12 .

Еще лучшая верхняя оценка, если мы сначала разделим первое неравенство на два.

  2x₁ + 3x₂ ≤ 2x₁ + 4x₂ ≤ 6

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

По сути, из ограничений мы пытаемся вывести неравенство вида:

  d₁x₁ + d₂x₂ ≤ h 
, где d₁ ≥ 2, d₂ ≥ 3, h как можно меньше.

Тогда мы можем утверждать, что:

 для всех  x₁, x₂ ≥ 0 имеем 
 2x₁ + 3x₂ ≤ d₁x₁ + d₂x₂ ≤ h

Следовательно, .Мы можем вывести такие неравенства, комбинируя три неравенства в линейной программе с некоторыми неотрицательными коэффициентами y₁, y₂, y₃ .

Как выбрать лучшие коэффициенты y₁, y₂, y₃ ? Решая линейную программу:

Она называется линейной программой, двойственной линейной программе, с которой мы начали. Двойная линейная программа «охраняет» исходную программу сверху в том смысле, что каждое допустимое решение (y₁, y₂, y₃) двойственной линейной программы обеспечивает верхнюю границу максимума целевой функции.

Больше никакой прокрастинации. У вас есть время для целей! Увеличитель поможет вам.

Интеллект метода двойного симплекса для решения дробно-линейной нечеткой транспортной задачи

Представлен подход к решению нечеткой транспортной задачи с дробно-линейной нечеткой целевой функцией. В этом предлагаемом подходе дробно-нечеткая транспортная задача разбивается на две линейные нечеткие транспортные задачи. Оптимальное решение двух линейно-нечетких перевозок решается двойственным симплекс-методом и получается оптимальное решение дробно-нечеткой транспортной задачи.Предлагаемый метод подробно поясняется на примере.

1. Введение

Транспортная задача относится к частному случаю задачи линейного программирования. Основная транспортная задача была разработана Хичкоком в 1941 г. [1]. В математике и экономике теория транспорта — это название, данное изучению оптимальной транспортировки и распределения ресурсов. Проблема была формализована французским математиком Гаспаром Монжем. Толстой был одним из первых, кто математически изучил транспортную задачу.Транспортная задача касается распределения одного товара из различных источников предложения в различные пункты назначения таким образом, чтобы общие транспортные расходы были минимальны. Чтобы решить транспортную проблему, параметры решения, такие как доступность, требования и удельная транспортная стоимость модели, должны быть зафиксированы на четких значениях.

При применении ИЛИ-методов к инженерным задачам, например, проблемы, которые необходимо смоделировать и решить, обычно достаточно четкие, хорошо описанные и четкие.Как правило, их можно смоделировать и решить с помощью классической математики, которая носит дихотомический характер. Если появляется неопределенность, то обычно она имеет стохастический характер и может быть правильно смоделирована с помощью теории вероятностей. Это верно для многих областей, таких как теория запасов, управление трафиком и планирование, в которых теория вероятностей применяется через теорию массового обслуживания. Одной из наиболее важных областей, в которых неопределенность отличается от случайности, является, вероятно, область принятия решений.В принятие решений вступает человеческий фактор со всей его нечеткостью восприятия, субъективностью, установками целей и представлений. В транспортных задачах предложение, спрос и удельная стоимость перевозки могут быть неопределенными из-за нескольких факторов; эти неточные данные могут быть представлены нечеткими числами. Когда спрос, предложение или стоимость единицы транспортной задачи принимают нечеткое значение, оптимальное значение этой задачи также является нечетким, поэтому она становится нечеткой транспортной задачей.

Линейное дробное программирование относится к тому классу задач математического программирования, в которых отношения между переменными являются линейными; отношение ограничений должно иметь линейную форму, а оптимизируемая целевая функция должна быть отношением двух линейных функций. Область задач линейно-дробного программирования была разработана венгерским математиком Б. Матросом в 1960 году. В последние десятилетия задача линейно-дробного программирования является важным инструментом планирования, который применяется в различных дисциплинах, таких как инженерия, бизнес, финансы и экономика. Линейно-дробная задача обычно используется для моделирования реальных проблем с одной или несколькими целями, такими как прибыль-затраты, запасы-продажи, фактические затраты-стандартные затраты и производительность-сотрудник; Проблемы многоуровневого программирования часто встречаются в иерархической организации, на заводе, в логистических компаниях и т.д.С практической точки зрения возникает необходимость рассмотреть большую задачу структурного программирования. Даже теоретически решить эту проблему можно, но на практике решить ее непросто. Существуют определенные ограничения, ограничивающие усилия аналитика. Главным из этих ограничений является проблема размерности. Это наводит на мысль о разработке методов решения, которые не должны использовать одновременно все данные задачи; одним из таких подходов является принцип декомпозиции Данцига [2] для линейных программ. Принцип требует решения серии задач линейного программирования меньшего размера, чем исходная задача. В этой статье мы предложили новый метод поиска оптимального решения дробно-нечеткой транспортной задачи, основанный на двойном симплексном подходе.

Этот документ организован следующим образом. В Разделе 2 представлена соответствующая работа. В разделе 3 представлены предварительные сведения о теории нечетких множеств. Задача линейно-дробно-нечеткого программирования объясняется в разделе 4. В разделе 5 появилась постановка задачи дробно-нечеткой транспортной задачи.Процедура для предлагаемого метода приведена в разделе 6. Наглядный пример приведен для объяснения этого предлагаемого метода, а выводы приведены в разделах 7 и 8, соответственно.

2. Родственные работы

Дробно-нечеткая транспортная задача представляет собой особый тип задачи линейного программирования и является активной областью исследований. Есть много статей в этой области, которые не могут быть рассмотрены полностью, и только некоторые из них рассмотрены здесь. Чарнс и Купер [3] разработали метод преобразования для преобразования метода дробного программирования в метод линейного программирования, Сваруп [4] ввел алгоритм симплексного типа для дробной программы, а Битран и Новаес [5] преобразовали дробно-линейную задачу в последовательность линейных программ и метод получил широкое распространение.Тантави [6] разработал метод двойного решения для дробной программы. Хасан и Ачарджи [7] использовали преобразование дробно-линейной задачи в однократное линейное программирование и вычислили в MATHEMATICA . Джоши и Гупта [8] решили дробно-линейную задачу с помощью прямодвойственного подхода. Шарма и Бансал [9] предложили метод, основанный на симплексном методе, в котором переменные расширяются. Джейн и др. В [10] предложен алгоритм ABC для решения задачи дробно-линейного программирования с использованием языка C.Сулейман и Басия [11] использовали технику преобразования.

Верма и др. В [12] разработан алгоритм, ранжирующий допустимые решения задачи целочисленного дробного программирования в порядке убывания значений целевой функции. Метев и Йорданова-Маркова [13] применили метод реперных точек. Пандиан и Джаялакшми [14] использовали метод разложения и метод ограничения знаменателя для преобразования дробной задачи в линейную. Чандра [15] предложил принцип декомпозиции для решения дробно-линейной задачи.Шарма и Бансал [9] дали целочисленное решение для дробно-линейной задачи. Дейя [16] дал оптимальное решение дробно-линейной задачи с нечеткими числами. Гузель и др. В [17] предложен алгоритм, использующий ряды Тейлора первого порядка для преобразования интервальной линейно-дробной транспортной задачи в линейную многокритериальную задачу. Мадхури [18] дал метод решения минимального времени линейной фракционной транспортной задачи с примесями. Джейн и Арья [19] решили обратную транспортную задачу с дробно-линейной целевой функцией.

Вдохновленный работой Güzel et al. [17], в данной статье автор предлагает новый метод поиска оптимального решения дробно-нечеткой транспортной задачи. Некоторые из ограничений существующих методов заключаются в том, что в методах Чарнса и Купера для получения решения необходимо решать линейную задачу двухфазным методом на каждом шаге, что становится длительным и громоздким. В методе Битрана и Нова нужно решить ряд задач, для решения которых иногда может потребоваться много итераций.В этом методе если для всех, то этот метод не работает. В методе Сварупа, когда ограничения не в канонической форме, этот метод становится громоздким, а его вычислительный процесс усложняется на каждой итерации. В методе Харви он преобразует дробно-линейную задачу в линейную при условии, что . Если этот метод не работает.

Чтобы преодолеть эти ограничения, в этой статье предлагается новый метод, в котором линейная дробная транспортная задача разлагается на две линейные нечеткие транспортные задачи в предположении, что значения равны нулю.Эти линейные транспортные задачи решаются методом двойного симплекса.

3. Предварительные сведения

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

3.1. Fuzzy Set [20]

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

3.2. Нечеткое число [20]

Нечеткое число — это нечеткое множество, функция принадлежности которого удовлетворяет следующим условиям. (i) является кусочно-непрерывным. (ii) нечеткое множество универсума дискурса выпукло. (iii) нечеткое множество Вселенной дискурса называется нормальным нечетким множеством, если существует .

3.3. Трапециевидное нечеткое число [20]

Нечеткое число называется трапециевидным нечетким числом, если его функция принадлежности задается выражением

3.4. Арифметические операции

Пусть и — два нечетких трапециевидных числа; арифметические операторы над этими числами следующие.

Дополнение:

Вычитание:

Скалярное умножение:

3.5. Функция ранжирования

Следующая функция ранжирования, определенная здесь, используется для сравнения нечетких значений при выполнении метода двойного симплекса. Функция ранжирования, которая отображает каждое нечеткое число в реальную строку. представляет собой множество всех трапециевидных нечетких чисел.Если – любая ранжирующая функция, то .

3.6. Эффективная точка

Допустимая точка называется эффективным решением для , если не существует другой допустимой точки задачи такой, что и .

3.7. Идеальное решение

Позвольте быть оптимальным решением проблемы , ; то значение целевой функции , называется идеальным решением задачи.

3.8. Лучшее компромиссное решение

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

Лемма 1. Допустимое решение задачи считается эффективным тогда и только тогда, когда не существует других допустимых решений, для которых мы получаем лучшее значение хотя бы по одному критерию, при котором значение остальных критериев остается неизменным .

Теорема 2. Если множество эффективных точек для задачи , то является подмножеством множества всех эффективных точек .

Доказательство. Позвольте быть множество эффективных точек .Позвольте быть множество эффективных точек . В виде , . Множество всех эффективных точек , содержится в .

Теорема 3. Позвольте быть оптимальным решением и пусть быть оптимальным решением ; то является оптимальным решением данной задачи, где все являются элементами , .

Доказательство. Позвольте быть оптимальным решением . Это решение является эффективным решением, если нет допустимого решения; эти множества эффективных решений содержатся в . Аналогично множество эффективных решений содержится в .Итак, по теореме 2 эти решения являются множеством эффективных решений уравнения .

4. Введение в задачу дробно-линейного нечеткого программирования (LFFPP)

Одной из основных целей этой статьи является расширение задачи дробно-линейного нечеткого программирования до задачи дробно-линейного нечеткого программирования.

LFFPP можно представить следующим образом: где и — линейные функции, а множество определяется как . Вот нечеткая матрица; будем считать, что это ограниченный многогранник и для всех .Хорошо известно, что целевая функция в max имеет функцию глобального максимума и не имеет других локальных максимумов. Этот максимум достигается в крайней точке .

LFFPP (5) теперь можно записать как Тогда по теореме 3, если и тогда множество эффективных точек для задачи , , является подмножеством множества всех эффективных точек .

5. Постановка задачи

Предлагаемая нечеткая транспортная модель основана на следующем предположении.

Набор указателей. Учтите, что ниже приведен исходный индекс для всех файлов . индекс назначения для всех .

Параметры. Рассмотрим следующее количество единиц, перевезенных из источника в пункт назначения. на единицу прибыли затраты на транспортировку от источника до места назначения. это удельная стоимость перевозки от источника до места назначения.

Целевая функция. Рассмотрим следующее. (i) Дробная транспортная задача. Значения и считаются трапецеидальными нечеткими числами.

Ограничения. Рассмотрим следующее.

(i) Ограничения на предложение для всех источников

(ii) Ограничения на спрос для каждого пункта назначения

Неотрицательные ограничения. Рассмотрим следующее.

(i) Неотрицательные ограничения на переменные решения Вышеупомянутая LFFTP будет иметь базовое допустимое решение только тогда, когда .

6. Процедура для предлагаемого метода

Здесь мы представляем новый метод решения линейно-дробно-нечеткой транспортной задачи.

Рассмотрим линейно-дробно-нечеткую транспортную задачу как Поскольку целевая функция является дробной целевой функцией, мы разделяем задачу на две линейные нечеткие транспортные задачи по (6) следующим образом: Мы решаем эти две линейные нечеткие транспортные задачи двойственными симплекс-методами. Таким образом, решение получается для и по отдельности. По теореме 3 оптимальное решение получается при получении оптимального решения и.

7. Численный пример

Чтобы проиллюстрировать предлагаемый метод, рассмотрим следующий пример для линейно-дробно-нечеткой транспортной задачи: Задача представляет собой линейно-дробно-нечеткую транспортную задачу, в которой целевая функция имеет трапециевидное нечеткое число; значения спроса и предложения являются четкими значениями.Теперь с помощью нашей вычислительной техники вышеуказанная задача может быть записана как Учтите: линейная задача может быть выражена в стандартной форме как Теперь решается двойным симплекс-методом.

Начальная итерация проблемы приведена в таблице 1.



		(-6, -4, -2, 0)	(-7, −6, −2, −1)	(−6, −5, −4, −1)	(−8, −5, −4, −3)	0	0	0	0

0	60	1	1	0	0	1	0	0	0
0	45	0	0	1	1	0	1	0	0
0	−50	−1	0	−1 90 888	0	0	0	0	1	0
0	-55	-55 9	-1	-1	0	-1	0	0	0	1
		(0, 2, 4, 6)	(1, 2, 6, 7)	(1, 4, 5, 6)	(3, 4, 5, 8)	0	0	0	0
		3	4	4	5	0	0	0	0

От начальной итерации мы видим, что небасическая переменная входит в основу, и базовая переменная покидает основу.

Применяя метод двойного симплекса и после нескольких итераций, мы получаем Таблицу 2. В Таблице 2 все значения положительны, и оптимальное решение получается следующим образом: Учтите: линейная задача может быть выражена в стандартной форме как Теперь решается двойным симплекс-методом.


			(-6, -4, -2, 0)	(-7, -6, -2, -1)	(-6 , -5, -4, -1)	(-8, -5, -4, -3)	0	0	0	0

(-8, -5, -4, -3)	45	0	0	1	1	-1	0	-1 9088	-1	-1	-1
0		9	0	0	0	0	1	1	1	1
(- 6, −5, −4, −1)	5	1	0	0	−1	1	0	0	0	1
(-7, -6, -2, -1)	55	0	1	0	1	0	0	0	-1

		0	0	0	0	(-5, 8, 6, 9)	(-5, 0, 3, 6)	0	(1, 4, 5, 6)	(−4, 2, 9, 13)

Начальная итерация задачи приведена в табл. 3.

0 (0, 1, 3 , 4)


				(-4, -3, -1, 0)	(-6, -5, -3, -2)	(-7) , -5, -3, -1)	(-9, -7, -6, -2)	0	0	0	0

0		60	1	1	0	0	1	0	0	0
0		45		0		1 1	0		1 0	0
	0		-50 -1	0	— 1	0	0	0	1	0
0	9		-55	-55	-1	-1	-1	-1	0	0	0	1

(2, 3, 5, 6)	(1, 3, 5, 7)	(2, 6, 7, 9)	0	0	0 _{8 9}
			2	4	4	6	0	0	0	0

Из начальной итерации мы видим, что неосновная переменная входит в базис, а базовая переменная выходит из него.

Применяя метод двойного симплекса и после нескольких итераций, мы получаем Таблицу 4. В Таблице 4 все значения положительны, и оптимальное решение получается следующим образом: По теореме 3 получено оптимальное решение дробно-нечеткой транспортной задачи.


			(-4, -3, -1, 0)	(-6, -5, -3, -2)	(-7) , -5, -3, -1)	(-9, -7, -6, -2)	0	0	0	0

(-7, -5, -3, -1)	45	0	0	1	1	-1	0	-1 9088	-1	-1	-1
0		9	0	0	0	0	1	1	1	1
(- 4, −3, −1, 0)	5	1	0	0	−1	1	0	0	0	1	9
(-6, -5, -3, -2)	55	0	1	0	1	0	0	0	-1

		0	0	0	0	(8, -2, 3, 3)	(-3, 0, 4, 7)	0	(1, 3, 5, 7)	(−1, 3. 9, 13)

Таким образом

8. Заключение

В настоящей статье предлагается метод решения линейно-дробно-нечеткой транспортной задачи, в котором в целевой функции используются трапециевидные нечеткие числа. Обсуждаются ограничения существующих методов. Преимущество вычислительной техники в том, что метод работает даже при нулевых значениях. Двойной симплексный метод является одним из лучших методов получения оптимального решения.Метод может быть легко реализован для решения любой транспортной задачи. Методы решения проиллюстрированы примером. Результат показывает высокую эффективность решения, и это может быть распространено на дробно-квадратичные задачи. Симплексный метод можно использовать вместо двойного симплекса, если все ограничения относятся к ограничениям типа ≤.

Конфликт интересов

Авторы заявляют об отсутствии конфликта интересов в отношении публикации данной статьи.

Благодарность

Авторы хотели бы поблагодарить анонимных рецензентов за различные предложения, которые привели к улучшению как качества, так и ясности статьи.

Двойной симплексный метод

Когда дело доходит до симплексного метода, он известен как общий и мощный метод, и он считается доступным методом, используемым для решения различных задач линейного программирования. Углубляясь в процедуру симплексных вычислений, вы поймете следующие шаги:

Шаг 1 : Необходимо сформулировать данную задачу относительно стандартной максимизации LPP

Шаг 2 : Выберите начальное базовое допустимое решение, которое может инициировать любые итерации

Шаг 3 : Найдите целевую функцию и найдите любую неосновную переменную, которая может помочь улучшить целевую функцию, и найдите основное решение.Если такая переменная существует, перейдите к следующему шагу.

Шаг 4 : Протестируйте любое данное решение для обеспечения оптимальности

Шаг 5 : Продолжить итерации и получить оптимальное решение, которое может указывать на возможность наличия неограниченного решения

Симплексный метод линейного программирования

Симплекс-метод используется для решения задач, связанных с линейным программированием. Прежде чем перейти к симплексному методу, необходимо преобразовать линейную программу в стандартную форму:

Макс. c1x1+c2x2+…+cnxnc1x1+c2x2+…+cnxn

С учетом: a11x1+a12x2+….+a1nxn=b1a11x1+a12x2+….+a1nxn=b1

a21x1+a22x2+….+a2nxn=b2a21x1+a22x2+….+a2nxn=b2

……………………………………

am1x1+am2x2+….+amnxn=bmam1x1+am2x2+….+amnxn=bm

x1x1 ≥≥ 0, x1x1 ≥≥ 0, …….., xnxn ≥≥ 0.

Причины для изучения метода двойного симплекса

Помогает выбрать начальный базис даже без добавления какой-либо искусственной переменной
Позволяет проводить различные виды тестирования чувствительности
Позволяет решать любые задачи целочисленного программирования

Шаги в двойном симплексном алгоритме

Сформулируйте любую математическую модель, связанную с данной задачей линейного программирования.Вам нужно преобразовать ограничение неравенства в LPP в ограничение равенства, и это, наконец, может помочь в написании задачи в стандартной форме.
Вычислите любое начальное базовое допустимое решение, задав нулевое значение для переменных решения. Это решение можно найти в исходной двойной симплексной таблице.
В случае, если значения в столбце X ₅ ≥ 0, убедитесь, что метод двойного симплекса не используется, так как оптимальное решение может быть получено симплексным методом. С другой стороны, если значение ниже столбца X ₅ <0, текущее решение становится невозможным.
Выберите любое наименьшее отрицательное значение меньше X ₅ В строке также может быть указано любое наименьшее отрицательное значение.
Выберите неосновные переменные в индексной строке (Z ₁ C ₁ ) и, наконец, разделите значение на соответствующие значения любой ключевой строки.

Ключевой столбец =

Мин.

z _j c _j
——–
a _ij

a _ij < 0

Непосредственное использование двойного симплекс-метода

Выберите таблицу и, наконец, решите задачу с помощью метода двойного симплекса:

Сделать любой указанный двойной симплексный шарнир дает:

Ссылки предыдущей основной темы: —

Ссылки на следующие темы финансов: —

РубрикаРазное

Решение задач линейного программирования симплекс-методом. Двойственность ЗЛП

1. Решение задач линейного программирования симплекс-методом. Двойственность ЗЛП.

Онлайн Калькулятор: Симплекс Метод

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

Решение

Двойственный симплекс-метод — Энциклопедия по экономике

Онлайн калькулятор: Dual Simplex

Эгвальд Исследование операций — Линейное программирование

Решатель симплексного метода

Матричная форма

Нематричная форма

Анализ чувствительности

Добавить ограничения

Добавить переменные

Изменить коэффициент(ы) ограничений

Изменить коэффициент(ы) целевой функции

Изменение ресурса

Пример по умолчанию

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

Обзор инфраструктуры pami

Основной тест оптимальности

Второстепенная инициализация

Второстепенные итерации

Основное обновление

Кандидатская настойчивость и контроль качества в чузр

Сверхразреженные задачи LP

Двойной симплексный метод.Это часть курса… | Родион Чачура

Интеллект метода двойного симплекса для решения дробно-линейной нечеткой транспортной задачи

1. Введение

2. Родственные работы

3. Предварительные сведения

3.1. Fuzzy Set [20]

3.2. Нечеткое число [20]

3.3. Трапециевидное нечеткое число [20]

3.4. Арифметические операции

3.5. Функция ранжирования

3.6. Эффективная точка

3.7. Идеальное решение

3.8. Лучшее компромиссное решение

4. Введение в задачу дробно-линейного нечеткого программирования (LFFPP)

5. Постановка задачи

6. Процедура для предлагаемого метода

7. Численный пример

8. Заключение

Конфликт интересов

Благодарность

Двойной симплексный метод

Добавить комментарий Отменить ответ