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

Решение задач линейного программирования

Назначение сервиса . Онлайн-калькулятор предназначен для решения задач линейного программирования симплексным методом путем перехода к КЗЛП и СЗЛП . При этом задача на минимум целевой функции сводятся к задаче на поиск максимума через преобразование целевой функции F*(X) = -F(X) . Также имеется возможность составить двойственную задачу.

1. Переход к КЗЛП. Любая ЗЛП вида ax ≤ b , ax ≥ b , ax = b ( F(X) → extr ) сводится к виду ax = b , F(X) → max ;
2. Переход к СЗЛП. КЗЛП вида ax = b сводится к виду ax ≤ b , F(X) → max ;
3. Решение симплексным методом;

• Шаг №1
• Шаг №2
• Видеоинструкция
• Оформление Word

Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word .

Переход от задачи минимизации целевой функции к задаче максимизации

Задача минимизации целевой функции F(X) легко может быть сведена к задаче максимизации функции F*(X) при тех же ограничениях путем введения функции: F*(X) = -F(X) . Обе задачи имеют одно и то же решение X*, и при этом min(F(X)) = -max(F*(X)) .
Проиллюстрируем этот факт графически:

F(x) → min

F(x) → max

Для оптимизации функции цели используем следующие понятия и методы.
Опорный план – план с определёнными через свободные базисными переменными.
Базисный план – опорный план с нулевыми базисными переменными.
Оптимальный план – базисный план, удовлетворяющий оптимальной функции цели (ФЦ).

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

Переменные x₁, …, x_m, входящие с единичными коэффициентами только в одно уравнение системы, с нулевыми – в остальные, называются базисными или зависимыми. В канонической системе каждому уравнению соответствует ровно одна базисная переменная. Переход осуществляется с помощью метода Гаусса–Жордана. Основная идея этого метода состоит в сведении системы m уравнений с n неизвестными к каноническому виду при помощи элементарных операций над строками.
Остальные n-m переменных (x_m+1,…, x_n) называются небазисными или независимыми переменными.

Базисное решение называется допустимым базисным решением, если значения входящих в него базисных переменных x_j≥0, что эквивалентно условию неотрицательности b_j≥0.
Допустимое базисное решение является угловой точкой допустимого множества S задачи линейного программирования и называется иногда опорным планом.
Если среди неотрицательных чисел b_j есть равные нулю, то допустимое базисное решение называется вырожденным (вырожденной угловой точкой) и соответствующая задача линейного программирования называется вырожденной.

Пример №1 . Свести задачу линейного программирования к стандартной ЗЛП.
F(X) = x₁ + 2x₂ — 2x₃ → min при ограничениях:
4x₁ + 3x₂ — x₃≤10
— 2x₂ + 5x₃≥3
x₁ + 2x₃=9
Для приведения ЗЛП к канонической форме необходимо:
1. Поменять знак у целевой функции. Сведем задачу F(X) → min к задаче F(X) → max. Для этого умножаем F(X) на (-1). В первом неравенстве смысла (≤) вводим базисную переменную x₄; во втором неравенстве смысла (≥) вводим базисную переменную x₅ со знаком минус.
4x₁ + 3x₂-1x₃ + 1x₄ + 0x₅ = 10
0x₁-2x₂ + 5x₃ + 0x₄-1x₅ = 3
1x₁ + 0x₂ + 2x₃ + 0x₄ + 0x₅ = 9
F(X) = — x₁ — 2x₂ + 2x₃
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:

4	3	-1	1	0	10
0	-2	5	0	-1	3
1	0	2	0	0	9

Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x₄.
2. В качестве базовой переменной выбираем x₂.
Разрешающий элемент РЭ=-2. Строка, соответствующая переменной x₂, получена в результате деления всех элементов строки x₂ на разрешающий элемент РЭ=-2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x₂ записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:

4-(0 • 3):-2	3-(-2 • 3):-2	-1-(5 • 3):-2	1-(0 • 3):-2	0-(-1 • 3):-2	10-(3 • 3):-2
0 : -2	-2 : -2	5 : -2	0 : -2	-1 : -2	3 : -2
1-(0 • 0):-2	0-(-2 • 0):-2	2-(5 • 0):-2	0-(0 • 0):-2	0-(-1 • 0):-2	9-(3 • 0):-2

Получаем новую матрицу:

4	0	6 1 /2	1	-1 1 /2	14 1 /2
0	1	-2 1 /2	0	1 /2	-1 1 /2
1	0	2	0	0	9

3. В качестве базовой переменной выбираем x₃.
Разрешающий элемент РЭ=2. Строка, соответствующая переменной x₃, получена в результате деления всех элементов строки x₃ на разрешающий элемент РЭ=2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x₃ записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:

4-(1 • 6 1 /2):2	0-(0 • 6 1 /2):2	6 1 /2-(2 • 6 1 /2):2	1-(0 • 6 1 /2):2	-1 1 /2-(0 • 6 1 /2):2	14 1 /2-(9 • 6 1 /2):2
0-(1 • -2 1 /2):2	1-(0 • -2 1 /2):2	-2 1 /2-(2 • -2 1 /2):2	0-(0 • -2 1 /2):2	1 /2-(0 • -2 1 /2):2	-1 1 /2-(9 • -2 1 /2):2
1 : 2	0 : 2	2 : 2	0 : 2	0 : 2	9 : 2

Получаем новую матрицу:

3 /4	0	0	1	-1 1 /2	-14 3 /4
1 1 /4	1	0	0	1 /2	9 3 /4
1 /2	0	1	0	0	4 1 /2

Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (4,2,3).
Соответствующие уравнения имеют вид:
3 /₄x₁ + x₄ — 1 1 /₂x₅ = -14 3 /₄
1 1 /₄x₁ + x₂ + 1 /₂x₅ = 9 3 /₄
1 /₂x₁ + x₃ = 4 1 /₂
Выразим базисные переменные через остальные:
x₄ = — 3 /₄x₁ + 1 1 /₂x₅-14 3 /₄
x₂ = — 1 1 /₄x₁ — 1 /₂x₅+9 3 /₄
x₃ = — 1 /₂x₁+4 1 /₂
Подставим их в целевую функцию:
F(X) = — x₁ — 2(- 1 1 /₄x₁ — 1 /₂x₅+9 3 /₄) + 2(- 1 /₂x₁+4 1 /₂)
или
F(X) = 1 /₂x₁ + x₅-10 1 /₂ → max
Система неравенств:
— 3 /₄x₁ + 1 1 /₂x₅-14 3 /₄ ≥ 0
— 1 1 /₄x₁ — 1 /₂x₅+9 3 /₄ ≥ 0
— 1 /₂x₁+4 1 /₂ ≥ 0
Приводим систему неравенств к следующему виду:
3 /₄x₁ — 1 1 /₂x₅ ≤ -14 3 /₄
1 1 /₄x₁ + 1 /₂x₅ ≤ 9 3 /₄
1 /₂x₁ ≤ 4 1 /₂
F(X) = 1 /₂x₁ + x₅-10 1 /₂ → max
Упростим систему.
3 /₄x₁ — 1 1 /₂x₂ ≤ -14 3 /₄
1 1 /₄x₁ + 1 /₂x₂ ≤ 9 3 /₄
1 /₂x₁ ≤ 4 1 /₂
F(X) = 1 /₂x₁ + x₂-10 1 /₂ → max

Источник

Решение транспортной задачи – онлайн калькулятор

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

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

Исходные данные задачи

Метод ввода данных:
Вручную Из электронной таблицы

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

Руководство по использованию калькулятора

Математическая модель задачи

Пусть некоторый продукт, который будем называть грузом, нужно перевезти от m поставщиков к n потребителям. При этом у поставщика с номером i имеется a_i единиц груза, ; потребителю с номером j требуется b_j единиц груза, . Величины a_i и b_j мы будем называть, соответственно, мощностью i — го поставщика и мощностью j — го потребителя. Известны величины стоимости c_ij перевозки единицы груза от i — го поставщика к j — му потребителю. Пусть x_ij – количество груза, перевезенного от i — го поставщика к j — му потребителю. Организовать перевозки можно различными способами, то есть величины x_ij можно выбрать с помощью различных вариантов. Требуется определить такие значения величин x_ij , при которых суммарные затраты F на перевозки будут минимальными: .

Таким образом, математическая модель задачи имеет следующий вид:

.

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

Ввод исходных данных

Исходными данными являются мощности поставщиков a_i , мощности потребителей b_j и затраты на перевозки c_ij . Все исходные данные вводятся в таблице, у которой m + 1 строк и n + 1 столбцов. При этом либо первая слева клетка (1, 1) , либо клетка (m + 1, n + 1) справа в последнем ряду, пустая.

Существует два способа ввода данных:
1. Вручную, вводом значений в соответствующие поля.
2. Загружая данные из электронной таблицы.

Ввод данных вручную

Чтобы ввести исходные данные вручную нужно выполнить следующие действия.
1. В строке ′Метод ввода данных′ ⇑, нужно поставить переключатель в положение ′Вручную′.
2. Ввести число поставщиков a , число потребителей b , и нажать кнопку ′Применить′.
3. В появившейся таблице заполнить столбец мощностей поставщиков a_i , строку мощностей потребителей b_j , и матрицу затрат c_ij .
4. Выбрать метод расчета начального опорного плана – отметить либо ′Метод наименьшей стоимости′, либо ′Метод северо-западного угла′.
5. Нажать кнопку ′Рассчитать′. В результате появится подробное решение задачи.
6. После расчета можно сохранить исходные данные. Для этого в строке ′Метод ввода данных′ ⇑, нужно отметить ′Из электронной таблицы′. В текстовом поле будут исходные данные задачи. Их можно скопировать в буфер обмена и вставить в электронную таблицу или текстовый документ. Для этого нужно нажать кнопку ′Копировать′. Данные будут скопированы в буфер обмена. Далее можно открыть электронную таблицу или текстовый документ, и вставить данные из буфера обмена, нажимая Ctrl-V . После чего сохранить изменения в документе.

Ввод данных из электронной таблицы

Исходные данные можно ввести из электронной таблицы. При этом разделителем строк является перенос строки. В качестве разделителя столбцов может быть символ табуляции, запятая ′,′, точка с запятой ′;′, двоеточие ′:′ или пробел ′ ′. Вводить мощности поставщиков и потребителей можно двумя способами.

В первом способе, первое поле первой строки должно быть пустым. Далее, в первой строке следуют величины мощностей потребителей b_j . В следующих строках, первым элементом является мощность поставщика a_i . За ним следуют элементы матрицы затрат c_ij .

Источник