Интерактивный подход к обучению решения задач двойственным симплекс-методом | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Журнал выйдет 6 ноября, печатный экземпляр отправим 10 ноября.

Опубликовать статью в журнале

Автор:

Рубрика: Информационные технологии

Опубликовано в Молодой учёный №22 (156) июнь 2017 г.

Дата публикации: 04.06.2017

Статья просмотрена: 486 раз

Библиографическое описание:

Гордеев, С. Н. Интерактивный подход к обучению решения задач двойственным симплекс-методом / С. Н. Гордеев. — Текст : непосредственный // Молодой ученый. — 2017. — № 22 (156). — С. 122-124. — URL: https://moluch.ru/archive/156/44061/ (дата обращения: 23.10.2021).



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

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

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

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

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

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

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

Двойственное условие оптимальности. Вводимая в базис переменная определяется как переменная, на которой достигается следующий минимум:

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

Реализация программного средства для интерактивного решения задачи двойственным симплекс-методом выполнена на объектно-ориентированном языке программирования Java.

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

2016-12-26

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

Далее переходим ко второму шагу (рисунок 2), где необходимо ввести номер исключаемого и включаемого в базис элемента.

2016-12-26 (16)

Рис. 2. Второй шаг интерактивного решения задачи

На третьем шаге (рисунок 3) необходимо пересчитать симплекс-таблицу и ввести полученные данные.

2016-12-26 (3)

Рис. 3. Третий шаг интерактивного решения задачи

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

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

Литература:

  1. Таха Х. А. Введение в исследование операций 6-е издание. Пер. с англ. — Москва: Издательский дом «Вильямс», 2005. — 912 с.
  2. Зайченко Ю. П. Исследование операций: Учеб. пособие для студентов вузов. — 2-е изд., перераб. и доп.— Киев: Вища школа. Головное изд-во, 1979. 392 с.
  3. Герберт Шилдт. Java 8. Полное руководство. — 9-е изд. — Вильямс, 2017. — 1376 с.
Основные термины (генерируются автоматически): двойственный симплекс-метод, интерактивное решение задачи, задача, интерактивное решение задач, линейное программирование, оптимальное решение, переменная, постановка задачи, решение, целевая функция.


Похожие статьи

Решение многокритериальных задач линейного...

Решение многокритериальных задач линейного программирования (ЗЛП) методом последовательных уступок в MatLab.

%Настройка функции linprog на решение симплекс-методом.

Решение многокритериальных задач линейного...

Решение многокритериальных задач линейного программирования (ЗЛП) методом последовательных уступок в MatLab.

%Настройка функции linprog на решение симплекс-методом.

Интерактивный подход к решению задач линейного...

В процессе решения задач линейного программирования (далее — ЗЛП) часто возникает ситуация, когда пользователь не может решить задачу обычным симплекс-методом (то есть в системе ограничений присутствует не только условие вида « », но и условия видов « » и...

Интерактивный подход к решению задач линейного...

В процессе решения задач линейного программирования (далее — ЗЛП) часто возникает ситуация, когда пользователь не может решить задачу обычным симплекс-методом (то есть в системе ограничений присутствует не только условие вида « », но и условия видов « » и...

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

Решение задачи осуществляется симплексным методом [1, с. 176] с помощью сервисной функции MS Excel «Поиск решения». Описание шагов алгоритма «метода ветвей и границ». Решение вспомогательной задачи линейного программирования.

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

Решение задачи осуществляется симплексным методом [1, с. 176] с помощью сервисной функции MS Excel «Поиск решения». Описание шагов алгоритма «метода ветвей и границ». Решение вспомогательной задачи линейного программирования.

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

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

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

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

Решение интервальной задачи дробно-линейного...

Решив задачу симплекс-методом, получим следующие значения переменных

Решение многокритериальных задач линейного программирования (ЗЛП) методом

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

Решение интервальной задачи дробно-линейного...

Решив задачу симплекс-методом, получим следующие значения переменных

Решение многокритериальных задач линейного программирования (ЗЛП) методом

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

Организация решения задач исследования операций в MATHCAD

2. Решение задачи линейного программирования в MathCAD. В задаче линейного программирования целевая функция и ограничения

Каноническая задача линейного программирования решается с помощью хорошо известного симплекс метода [1–3].

Организация решения задач исследования операций в MATHCAD

2. Решение задачи линейного программирования в MathCAD. В задаче линейного программирования целевая функция и ограничения

Каноническая задача линейного программирования решается с помощью хорошо известного симплекс метода [1–3].

Применение метода линейного программирования для...

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

Другими словами, необходимо максимизировать (минимизировать) линейную функцию L. Покажем, как решается указанная задача...

Применение метода линейного программирования для...

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

Другими словами, необходимо максимизировать (минимизировать) линейную функцию L. Покажем, как решается указанная задача...

Линейное программирование | Статья в журнале «Молодой...»

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

Линейное программирование | Статья в журнале «Молодой...»

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

Интерактивный подход к решению транспортной задачи...

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

Интерактивный подход к решению транспортной задачи...

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

Похожие статьи

Решение многокритериальных задач линейного...

Решение многокритериальных задач линейного программирования (ЗЛП) методом последовательных уступок в MatLab.

%Настройка функции linprog на решение симплекс-методом.

Решение многокритериальных задач линейного...

Решение многокритериальных задач линейного программирования (ЗЛП) методом последовательных уступок в MatLab.

%Настройка функции linprog на решение симплекс-методом.

Интерактивный подход к решению задач линейного...

В процессе решения задач линейного программирования (далее — ЗЛП) часто возникает ситуация, когда пользователь не может решить задачу обычным симплекс-методом (то есть в системе ограничений присутствует не только условие вида « », но и условия видов « » и...

Интерактивный подход к решению задач линейного...

В процессе решения задач линейного программирования (далее — ЗЛП) часто возникает ситуация, когда пользователь не может решить задачу обычным симплекс-методом (то есть в системе ограничений присутствует не только условие вида « », но и условия видов « » и...

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

Решение задачи осуществляется симплексным методом [1, с. 176] с помощью сервисной функции MS Excel «Поиск решения». Описание шагов алгоритма «метода ветвей и границ». Решение вспомогательной задачи линейного программирования.

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

Решение задачи осуществляется симплексным методом [1, с. 176] с помощью сервисной функции MS Excel «Поиск решения». Описание шагов алгоритма «метода ветвей и границ». Решение вспомогательной задачи линейного программирования.

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

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

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

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

Решение интервальной задачи дробно-линейного...

Решив задачу симплекс-методом, получим следующие значения переменных

Решение многокритериальных задач линейного программирования (ЗЛП) методом

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

Решение интервальной задачи дробно-линейного...

Решив задачу симплекс-методом, получим следующие значения переменных

Решение многокритериальных задач линейного программирования (ЗЛП) методом

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

Организация решения задач исследования операций в MATHCAD

2. Решение задачи линейного программирования в MathCAD. В задаче линейного программирования целевая функция и ограничения

Каноническая задача линейного программирования решается с помощью хорошо известного симплекс метода [1–3].

Организация решения задач исследования операций в MATHCAD

2. Решение задачи линейного программирования в MathCAD. В задаче линейного программирования целевая функция и ограничения

Каноническая задача линейного программирования решается с помощью хорошо известного симплекс метода [1–3].

Применение метода линейного программирования для...

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

Другими словами, необходимо максимизировать (минимизировать) линейную функцию L. Покажем, как решается указанная задача...

Применение метода линейного программирования для...

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

Другими словами, необходимо максимизировать (минимизировать) линейную функцию L. Покажем, как решается указанная задача...

Линейное программирование | Статья в журнале «Молодой...»

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

Линейное программирование | Статья в журнале «Молодой...»

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

Интерактивный подход к решению транспортной задачи...

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

Интерактивный подход к решению транспортной задачи...

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

Задать вопрос