Задача линейного программирования java

Программирование на C, C# и Java

Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы

ОСТОРОЖНО МОШЕННИКИ! В последнее время в социальных сетях участились случаи предложения помощи в написании программ от лиц, прикрывающихся сайтом vscode.ru. Мы никогда не пишем первыми и не размещаем никакие материалы в посторонних группах ВК. Для связи с нами используйте исключительно эти контакты: vscoderu@yandex.ru, https://vk.com/vscode

Симплекс-метод. Реализация

В этой статье рассматривается симплекс-метод, который применяется при решении задач линейного программирования (ЗЛП). Приводится алгоритм метода, а также его реализация на языке C#. Реализация представлена в конце статьи.

Определения

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

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

Оптимизация — задача нахождения минимума или максимума (экстремума) целевой функции.

Целевая функция — это функция нескольких переменных, подлежащая оптимизации в целях решения какой-либо оптимизационной задачи (например, задачи объемного планирования).

Алгоритм симплекс-метода

В начале исходную задачу линейного программирования приводят к каноническому виду, затем составляют симплекс-таблицу вида:

где в столбце «базис» указываются базисные переменные, а в последней строке столбца «базис» пишется f(x). В столбец «B» записываются свободные члены ограничений b_i и значение целевой функции (на 1-м этапе оно равно 0, т.е. никакой прибыли).

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

В последней строке -c_j — это коэффициенты при переменных целевой функции взятые с противоположным знаком.

Симплекс-таблица составлена, теперь опишем сам симплекс-метод.

Шаг 1: Выполняется проверка полученного базисного плана на оптимальность по условию: если при каком-либо ДБР (допустимое базисное решение) в симплекс-таблице все коэффициенты строки f(x) (то есть -c_j) не отрицательны, то данное ДБР оптимально, следовательно КОНЕЦ решения. В противном случае:

Шаг 2: Переход к новому базисному плану. Для этого из числа небазисных переменных с отрицательными значениями в последней строке (то есть -c_j < 0) выбирается переменная, вводимая в базис — x_k, это переменная которой соответствует наибольшая по модулю отрицательная оценка:

Столбец, отвечающий переменной x_k, называется главным, или ведущим. Элементы данного столбца обозначаются через a_ik.

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

Шаг 3: Выбираем переменную r — переменную, которая выводится из базиса. Данная переменная находится из соотношения:

Строка таблицы, в которой получено наименьшее отношение элемента столбца «В» к соответствующему положительному элементу ведущего столбца, является ведущей, или главной.

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

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

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

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

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

а) элементы главной строки необходимо разделить на ведущий элемент:

б) элементы полученной строки умножаются на -a_ik, и результаты складываются с i-той строкой, причем i ≠ k:

После определения новой симплекс-таблицы переходят к шагу 1.

Симплекс-метод. Реализация C#

Приводим программную реализацию симплекс-метода. Программа написана на языке программирования C#.

Важная информация! Пожалуйста прочтите!

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

Формат входных данных: двумерный массив из элементов типа double.

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

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

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

Формат выходных данных: двумерный массив из элементов типа double и одномерный массив из элементов типа double.

Источник

Русские Блоги

«Интересные алгоритмы» Глава 7 Линейное программирование Реализация сетевого потокового кода (Java)

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

import java.util.Scanner; public class Test7_1 < static int n, m, i, j; // m представляет количество неосновных переменных, то есть количество столбцов в матрице, а n представляет количество базовых переменных, то есть количество строк в матрице static int [] FJL = new int [100]; // Сохраняем неосновные переменные static int [] JL = new int [100]; // сохраняем базовые переменные static float [] [] kernel = new float [100] [100]; // сохраняем симплексную таблицу public static void main(String[] args) < Scanner scanner=new Scanner(System.in); System.out.println ("Введите количество неосновных переменных и индексы неосновных переменных:"); m=scanner.nextInt(); for(int i=1;i<=m;i++) FJL[i]=scanner.nextInt(); System.out.println ("Введите количество основных переменных и индекс основных переменных:"); n=scanner.nextInt(); for(int i=1;i<=n;i++) JL[i]=scanner.nextInt(); System.out.println ("Параметры входных ограничений стандартной начальной симплексной таблицы:"); for(int i=0;i<=n;i++) < for(int j=0;j<=m;j++) kernel [i] [j] = scanner.nextFloat (); // Контрольный номер помещается в первую строку, постоянный элемент помещается в первый столбец, а коэффициент неосновной переменной используется в качестве значения >print (); // вывод симплексной таблицы DCXA(); scanner.close(); > / * Вывод симплексной таблицы * / public static void print() < System.out.println(); System.out.println ("Симплексная таблица выглядит следующим образом:"); System.out.print(" "+"b "); for(i=1;i<=m;i++) System.out.print("x"+FJL[i]+" "); System.out.println(); System.out.println("c "); for(i=0;i<=n;i++) < if(i>=1) System.out.print("x"+JL[i]+" "); for(j=0;j <=m;j++) System.out.print(kernel[i][j]+" "); System.out.println(); >> / * Решающая функция * / public static void DCXA() < float max1; // используется для хранения наибольшего количества проверок float max2; // используется для хранения максимального коэффициента базовой переменной, соответствующего максимальному положительному числу теста int e = -1; // Запись в базовый столбец int k = -1; // Запись от базовой линии float min; while (true) if (max1  for (i = 1; i  0&&temp > System.out.println ("Базовая переменная столбца: x" + FJL [e]); System.out.println ("Внешняя переменная: x" + JL [k]); if (max2 == 0) // Меняем местами внутренняя и внешняя переменные int temp=FJL[e]; FJL[e]=JL[k]; JL[k]=temp; // Рассчитываем симплексную таблицу for (i = 0; i  > > > for (i = 0; i  for (j = 0; j  kernel [k] [e] = 1 / kernel [k] [e]; // Расчет перекрестной позиции print(); > > > 

Результаты программы следующие:

Интеллектуальная рекомендация

TypeError: reduction operation ‘argmax‘ not allowed for this dtype

Напишите код для укрепления алгоритма обучения Q в обучении и сообщите об ошибке: Вначале «Argmax» был отброшен. Вместо этого вам нужно использовать «idxmax». Используйте функц.

Синтаксис конвейера Jenkins (in)

Директивы Окружающая обстановка environmentВ инструкции указывается серия пар «ключ-значение». Эти пары «ключ-значение» будут определены как переменные среды для всех шагов или опр.

Примечания к исследованию Rabbitmq 5: модель публикации / подписки

1. Концепции и модели В модели публикации и подписки одно и то же сообщение отправляется нескольким потребителям. Этот режим реализуется путем добавления маршрутизации. Производитель сообщения отправл.

Поток Python (2): простая синхронизация потока реализации блокировки

В Python есть два типа замков. Один блокировка -это исходный замок (примитивный), который не может быть повторен, а другой -рекурсивный блокировка, который может быть переведен. Вместо этого модуль по.

Как создать эффективную разбивку на страницы в ASP.NET Core

содержание Вступление фон Создать проект Обработка пейджинга в бэкэнде Создайте элемент управления пользовательского интерфейса подкачки Добавить поисковый фильтр Пользовательские элементы управления .

Источник

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Приложение, решающее задачу Линейного Программирования симплекс методом, графическим методом и методом искусственного базиса.

overcomzi/simplex_method

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Приложение, которое решает задачу Линейного Программирования графическим и симплекс методом

Задача линейного программирования (ЛП) – это задача, в которой требуется найти максимум или минимум функции, называемой целевой функцией, при ограничениях, заданных системой линейных неравенств или уравнений.

Приложене реализует 3 способа решения:

• Приложения отображает каждый промежуточный результат. Если нужен ответ, то достаточно нажать кнопку «Получить ответ«
• Имеется история промежуточных результатов, поэтому легко откатиться назад
• Можно загружать и выгружать условия задачи
  Файл -> Открыть / Сохранить условие задачи
• Отображение чисел можно представить в виде обыкновенных (1/2) или десятичных (0.5) дробей
• Есть возможность выбирать базисный вектор самостоятельно на каждом этапе решения

About

Приложение, решающее задачу Линейного Программирования симплекс методом, графическим методом и методом искусственного базиса.

Источник