Решить задачу линейного программирования симплекс-методом с искусственным базисом.
Пример 1:
Решить задачу линейного программирования симплекс-методом с искусственным базисом.
Решение от преподавателя:
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
2x1+x2-x3 = 1
x1+4x2+x4 = 3
Введем искусственные переменные x: в 1-м равенстве вводим переменную x5;
2x1+x2-x3+x5 = 1
x1+4x2+x4 = 3
Для постановки задачи на минимум целевую функцию запишем так:
F(X) = 10x1+2x2+Mx5 → min
Из уравнений выражаем искусственные переменные:
x5 = 1-2x1-x2+x3
которые подставим в целевую функцию:
F(X) = 10x1 + 2x2 + M(1-2x1-x2+x3) → min
или
F(X) = (10-2M)x1+(2-M)x2+(M)x3+(M) → min
Решим систему уравнений относительно базисных переменных: x5, x4
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,0,0,3,1)
Базис | B | x1 | x2 | x3 | x4 | x5 |
x5 | 1 | 2 | 1 | -1 | 0 | 1 |
x4 | 3 | 1 | 4 | 0 | 1 | 0 |
F(X0) | M | -10+2M | -2+M | -M | 0 | 0 |
Переходим к основному алгоритму симплекс-метода.
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (1 : 2 , 3 : 1 ) = 0.5
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.
Базис | B | x1 | x2 | x3 | x4 | x5 | min |
x5 | 1 | 2 | 1 | -1 | 0 | 1 | 0. |
x4 | 3 | 1 | 4 | 0 | 1 | 0 | 3 |
F(X1) | M | -10+2M | -2+M | -M | 0 | 0 |
5
Формируем следующую часть симплексной таблицы. Вместо переменной x5 в план 1 войдет переменная x1.
Получаем новую симплекс-таблицу:
Базис | B | x1 | x2 | x3 | x4 | x5 |
x1 | 0. | 1 | 0.5 | -0.5 | 0 | 0.5 |
x4 | 2.5 | 0 | 3.5 | 0.5 | 1 | -0.5 |
F(X1) | 5 | 0 | 3 | -5 | 0 | 5-M |
5
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
min (0.5 : 0.5 , 2.5 : 3.5 ) = 0.714
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (3.5) и находится на пересечении ведущего столбца и ведущей строки.
Базис | B | x1 | x2 | x3 | x4 | x5 | min |
x1 | 0. | 1 | 0.5 | -0.5 | 0 | 0.5 | 1 |
x4 | 2.5 | 0 | 3.5 | 0.5 | 1 | -0.5 | 0.714 |
F(X2) | 5 | 0 | 3 | -5 | 0 | 5-M |
5
Формируем следующую часть симплексной таблицы.
Вместо переменной x4 в план 2 войдет переменная x2.
Получаем новую симплекс-таблицу:
Базис | B | x1 | x2 | x3 | x4 | x5 |
x1 | 0.143 | 1 | 0 | -0.571 | -0.143 | 0.571 |
x2 | 0. | 0 | 1 | 0.143 | 0.286 | -0.143 |
F(X2) | 2.857 | 0 | 0 | -5.429 | -0.857 | 5.429-M |
714
Конец итераций: индексная строка не содержит положительных элементов — найден оптимальный план
Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
Базис | B | x1 | x2 | x3 | x4 | x5 |
x1 | 0. | 1 | 0 | -0.571 | -0.143 | 0.571 |
x2 | 0.714 | 0 | 1 | 0.143 | 0.286 | -0.143 |
F(X3) | 2.857 | 0 | 0 | -5.429 | -0.857 | 5.429-M |
143
Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым.
Оптимальный план можно записать так:
x1 = 0.143, x2 = 0.714
F(X) = 10·0.143 + 2· 0.714 = 2.857
Интерактивный подход к обучению решения задач двойственным симплекс-методом
Автор: Гордеев Сергей Николаевич
Рубрика: Информационные технологии
Опубликовано в Молодой учёный №22 (156) июнь 2017 г.
Дата публикации: 04.06.2017 2017-06-04
Статья просмотрена: 534 раза
Скачать электронную версию
Скачать Часть 2 (pdf)
Библиографическое описание: Гордеев, С.
Во многих университетах студенты изучают важную дисциплину «Теория принятия решений», которая использует методы математики, экономики, статистики и психологии с целью изучения закономерностей выбора людьми путей решения проблем и задач, а также способов достижения желаемого результата.
Одним из методов, которые изучают студенты, является двойственный симплекс-метод. Для того чтобы, помочь студентам быстро освоить данный метод была разработана обучающая программа, включающая теорию по данному методу, интерактивное решение задач и проверочный тест, включающая вопросы по теории и практике.
Несмотря на вычислительные ресурсы, которые доступны в современном мире, без оптимизированных методов для решения тех или иных задач не обойтись.
В частности двойственный симплекс-метод способствует уменьшению количества ограничений, что существенно упрощает решение больших и ресурсоемких задач.
Перед интерактивным решением задач двойственным симплекс-методом необходимо изучить теорию по данному разделу и получить навыки решения задач линейного программирования симплекс-методом.
В двойственном симплекс-методе решение задачи линейного программирования начинается с недопустимого, но лучшего, чем оптимальное решения. Последовательные итерации этого метода приближают решение к области допустимости без нарушения оптимальности промежуточных решений. Когда будет достигнута область допустимых решений, процесс вычислений заканчивается, так как последнее решение будет оптимальным. В двойственном симплекс-методе начальная симплекс-таблица обязательно должна иметь в базисном решении недопустимую (т. е. отрицательную) переменную.
Реализация двойственного симплекс-метода предполагает наличие двух условий:
Двойственное условие допустимости.
В качестве исключаемой переменной xr выбирается базисная переменная, имеющая наибольшее по абсолютной величине отрицательное значение.
Двойственное условие оптимальности. Вводимая в базис переменная определяется как переменная, на которой достигается следующий минимум:
где — коэффициент целевой функции, – коэффициент из симплекс-таблицы, расположенный на пересечении ведущей строки и столбца, соответствующего переменной xi. При наличии нескольких альтернативных переменных выбор делается произвольно. Коэффициент должен быть строго отрицательным.
Реализация программного средства для интерактивного решения задачи двойственным симплекс-методом выполнена на объектно-ориентированном языке программирования Java.
На рисунке 1 представлена постановка задачи и таблица для заполнения начальными значениями.
Рис. 1. Постановка задачи
Далее переходим ко второму шагу (рисунок 2), где необходимо ввести номер исключаемого и включаемого в базис элемента.
Рис. 2. Второй шаг интерактивного решения задачи
На третьем шаге (рисунок 3) необходимо пересчитать симплекс-таблицу и ввести полученные данные.
Рис. 3. Третий шаг интерактивного решения задачи
Таким образом производится пересчет симплекс-таблицы пока не будет получено допустимое и оптимальное решение.
Всего для интерактивного решения представлено две задачи на нахождения минимума целевой функции и одна задача на нахождение максимума. Также программное обеспечение предоставляет возможность ознакомиться с теорией по двойственному симплекс-методу и решить тест из десяти вопросов для проверки полученных знаний.
Литература:
- Таха Х. А. Введение в исследование операций 6-е издание. Пер. с англ. — Москва: Издательский дом «Вильямс», 2005. — 912 с.
- Зайченко Ю. П. Исследование операций: Учеб. пособие для студентов вузов. — 2-е изд., перераб. и доп.— Киев: Вища школа. Головное изд-во, 1979.
392 с. - Герберт Шилдт. Java 8. Полное руководство. — 9-е изд. — Вильямс, 2017. — 1376 с.
392 с.Основные термины (генерируются автоматически): двойственный симплекс-метод, интерактивное решение задачи, задача, интерактивное решение задач, линейное программирование, оптимальное решение, переменная, постановка задачи, решение, целевая функция.
Похожие статьи
Решение многокритериальных задач линейного…Решение многокритериальных задач линейного программирования (ЗЛП) методом последовательных уступок в MatLab.
%Настройка функции linprog на решение симплекс—методом.
Решение многокритериальных задач линейного…Решение многокритериальных задач линейного программирования (ЗЛП) методом последовательных уступок в MatLab.
%Настройка функции linprog на решение симплекс—методом.
Интерактивный подход к решению задач линейного…В процессе решения задач линейного программирования (далее — ЗЛП) часто возникает ситуация, когда пользователь не может решить задачу обычным симплекс—методом (то есть в системе ограничений присутствует не только условие вида « », но и условия видов « » и…
Интерактивный подход к решению задач линейного…В процессе решения
задач линейного программирования (далее — ЗЛП) часто возникает ситуация, когда пользователь не может решить задачу обычным симплекс—методом (то есть в системе ограничений присутствует не только условие вида « », но и условия видов « » и.
..Целочисленное
решение задач линейного программирования…Решение задачи осуществляется симплексным методом [1, с. 176] с помощью сервисной функции MS Excel «Поиск решения». Описание шагов алгоритма «метода ветвей и границ». Решение вспомогательной
Целочисленное
решение задач линейного программирования…Решение задачи осуществляется симплексным методом [1, с. 176] с помощью сервисной функции MS Excel «Поиск решения». Описание шагов алгоритма «метода ветвей и границ».
Решение вспомогательной задачи линейного программирования.
Создание и использование программы для статистического…
В данной работе решается задача сбора статистических данных при использовании программы, которая решает экономические задачи теории игр, сводя их к задачам линейного программирования (ЗЛП).
Создание и использование программы для статистического…
В данной работе решается задача сбора статистических данных при использовании программы, которая решает экономические задачи теории игр, сводя их к задачам линейного программирования (ЗЛП).
Решение интервальной задачи дробно-линейного.
..Решив задачу
Решение многокритериальных задач линейного программирования (ЗЛП) методом
Решение изопериметрической пространственной задачи методами нелинейного программирования.
Решение интервальной задачи дробно-линейного…Решив задачу симплекс—методом, получим следующие значения переменных
Решение многокритериальных задач линейного программирования (ЗЛП) методом
Решение изопериметрической пространственной задачи методами нелинейного программирования.
Организация
решения задач исследования операций в MATHCAD2. Решение задачи линейного программирования в MathCAD. В задаче линейного программирования целевая функция и ограничения
Каноническая задача линейного программирования решается с помощью хорошо известного симплекс метода [1–3].
Организация
решения задач исследования операций в MATHCAD2. Решение задачи линейного программирования в MathCAD. В задаче линейного программирования целевая функция и ограничения
Каноническая задача линейного программирования решается с помощью хорошо известного симплекс метода [1–3].
Применение
метода линейного программирования для…Среди неотрицательных решений этой системы требуется найти такое решение, при котором целевая функция линейного вида.
Другими словами, необходимо максимизировать (минимизировать) линейную функцию L. Покажем, как решается указанная задача…
Применение
метода линейного программирования для…Среди неотрицательных решений этой системы требуется найти такое решение, при котором целевая функция линейного вида.
Другими словами, необходимо максимизировать (минимизировать) линейную функцию L.
Покажем, как решается указанная задача…
В данной статье рассматривается задача линейного программирования и возможный способ её решения — симплекс метод. Приведены примеры, поясняющие, что такое линейное программирование и симплекс метод.
Линейное программирование | Статья в журнале «Молодой…» В данной статье рассматривается задача линейного программирования и возможный способ её решения — симплекс метод. Приведены примеры, поясняющие, что такое линейное программирование и симплекс метод.
Транспортные задачи составляют класс задач линейного программирования, специфика математической модели которых позволяет применять для их решения наряду с общими методами ЛП специальные методы, значительно сокращающие процесс вычислений.
Интерактивный подход к решению транспортной задачи… Транспортные задачи составляют класс задач линейного программирования, специфика математической модели которых позволяет применять для их решения наряду с общими методами ЛП специальные методы, значительно сокращающие процесс вычислений.
Похожие статьи
Решение многокритериальных задач линейного…Решение многокритериальных задач линейного программирования (ЗЛП) методом последовательных уступок в MatLab.
%Настройка функции linprog на решение симплекс—методом.
Решение многокритериальных задач линейного…Решение многокритериальных задач линейного программирования (ЗЛП) методом последовательных уступок в MatLab.
%Настройка функции linprog на решение симплекс—методом.
Интерактивный подход к решению задач линейного.
..В процессе решения задач линейного программирования (далее — ЗЛП) часто возникает ситуация, когда пользователь не может решить задачу обычным симплекс—методом (то есть в системе ограничений присутствует не только условие вида « », но и условия видов « » и…
Интерактивный подход к решению задач линейного… В процессе решения задач линейного программирования (далее — ЗЛП) часто возникает ситуация, когда пользователь не может решить задачу обычным симплекс—методом (то есть в системе ограничений присутствует не только условие вида « », но и условия видов « » и.
..
Целочисленное
решение задач линейного программирования…Решение задачи осуществляется симплексным методом [1, с. 176] с помощью сервисной функции MS Excel «Поиск решения». Описание шагов алгоритма «метода ветвей и границ». Решение вспомогательной задачи линейного программирования.
Целочисленное
решение задач линейного программирования…Решение задачи осуществляется симплексным методом [1, с. 176] с помощью сервисной функции MS Excel «Поиск решения». Описание шагов алгоритма «метода ветвей и границ».
Решение вспомогательной задачи линейного программирования.
Создание и использование программы для статистического…
В данной работе решается задача сбора статистических данных при использовании программы, которая решает экономические задачи теории игр, сводя их к задачам линейного программирования (ЗЛП).
Создание и использование программы для статистического…
В данной работе решается задача сбора статистических данных при использовании программы, которая решает экономические задачи теории игр, сводя их к задачам линейного программирования (ЗЛП).
Решив задачу симплекс—методом, получим следующие значения переменных
Решение многокритериальных задач линейного программирования (ЗЛП) методом
Решение изопериметрической пространственной задачи методами нелинейного программирования.
Решение интервальной задачи дробно-линейного…Решив задачу симплекс—методом, получим следующие значения переменных
Решение многокритериальных задач линейного программирования (ЗЛП) методом
Решение изопериметрической пространственной задачи методами нелинейного программирования.
Организация
решения задач исследования операций в MATHCAD2. Решение задачи линейного программирования в MathCAD. В задаче линейного программирования целевая функция и ограничения
Каноническая задача линейного программирования решается с помощью хорошо известного симплекс метода [1–3].
Организация
решения задач исследования операций в MATHCAD2. Решение задачи линейного программирования в MathCAD. В задаче линейного программирования целевая функция и ограничения
Каноническая задача линейного программирования решается с помощью хорошо известного симплекс метода [1–3].
Применение
метода линейного программирования для…Среди неотрицательных решений этой системы требуется найти такое решение, при котором целевая функция линейного вида.
Другими словами, необходимо максимизировать (минимизировать) линейную функцию L. Покажем, как решается указанная задача…
Применение
метода линейного программирования для…Среди неотрицательных решений этой системы требуется найти такое решение, при котором целевая функция линейного вида.
Другими словами, необходимо максимизировать (минимизировать) линейную функцию L.
Покажем, как решается указанная задача…
В данной статье рассматривается задача линейного программирования и возможный способ её решения — симплекс метод. Приведены примеры, поясняющие, что такое линейное программирование и симплекс метод.
Линейное программирование | Статья в журнале «Молодой…» В данной статье рассматривается задача линейного программирования и возможный способ её решения — симплекс метод. Приведены примеры, поясняющие, что такое линейное программирование и симплекс метод.
Транспортные задачи составляют класс задач линейного программирования, специфика математической модели которых позволяет применять для их решения наряду с общими методами ЛП специальные методы, значительно сокращающие процесс вычислений.
Интерактивный подход к решению транспортной задачи… Транспортные задачи составляют класс задач линейного программирования, специфика математической модели которых позволяет применять для их решения наряду с общими методами ЛП специальные методы, значительно сокращающие процесс вычислений.
от Аджита Сингха :: SSRN
Скачать эту статью
Открыть PDF в браузере
Добавить бумагу в мою библиотеку
Делиться:
10 страниц Опубликовано: 7 апр 2022 г.
Просмотреть все статьи Аджита Сингха
Университет Патны; INSTITUT de DIPLOMATIE PUBLIQUE, United Kingdom
Дата написания: 25 февраля 2022 г.
Abstract
Большинство реальных задач линейного программирования имеют более двух переменных и поэтому слишком сложны для графического решения.
Процедура, называемая симплекс-методом, может использоваться для поиска оптимального решения многомерных задач. Симплекс-метод на самом деле представляет собой алгоритм (или набор инструкций), с помощью которого мы методично исследуем угловые точки, пока не придем к лучшему решению — максимальной прибыли или минимальным затратам. Компьютерные программы и электронные таблицы доступны для обработки симплексных вычислений. Но вам нужно знать, что происходит за кулисами, чтобы лучше понять их ценные результаты.
Симплекс-метод — это подход к ручному решению моделей линейного программирования с использованием резервных переменных, таблиц и сводных переменных в качестве средства поиска оптимального решения задачи оптимизации. Линейная программа — это метод достижения наилучшего результата при максимальном или минимальном уравнении с линейными ограничениями. Большинство линейных программ можно решить с помощью онлайн-решателя, такого как MatLab, но симплекс-метод — это метод решения линейных программ вручную.
Ключевые слова: Линейное программирование, Симплекс-метод, LPP, Решение задач
Рекомендуемое цитирование: Рекомендуемая ссылка
Сингх, Аджит, Симплексный метод решения задач линейного программирования (25 февраля 2022 г.). Доступно на SSRN: https://ssrn.com/abstract=4043703 или http://dx.doi.org/10.2139/ssrn.4043703
У вас есть вакансия, которую вы хотели бы рекламировать в SSRN?
Связанные электронные журналы
Обратная связь
Обратная связь с SSRN
Обратная связь (обязательный)
Электронное письмо (обязательный)
Если вам нужна немедленная помощь, позвоните по номеру 877-SSRNHelp (877 777 6435) в США или +1 212 448 2500 за пределами США с 8:30 до 18:00 по восточному поясному времени США, с понедельника по пятницу.
Главы 3 и 4
Ресурсы
Линейная программа Шаблон геометрического решения для главы 3
Лаборатория линейного программирования Глава 4
Скорее всего, мы проведем лабораторную работу по линейному программированию на компьютере в лаборатории (или на iPad) в классе) один день во время работы над главой 4. Дополнительная информация будет опубликована здесь о лаборатории, месте, рабочем листе и сроке выполнения (или в Студии курса на MyPortal) в подходящее время.
Бесплатный онлайн-решатель линейных программ
Первая ссылка для симплексного метода для нескольких переменных, а вторая ссылка для
графическая линейная программа для задач с двумя переменными. Вы можете использовать их для проверки
Домашнее задание по главам 3 и 4, но вам нужно знать, как решать задачи самостоятельно для
викторины и экзамены.
Это полезные инструменты, но они не заменяют обучения тому, как делать
процедуры графически или на вашем калькуляторе.
- Линейный программный решатель для симплекс-метода с несколькими переменными
- Linear Program Grapher для задач с двумя переменными
Глава 3 Геометрический метод
Может оказаться полезным использовать шаблон таблицы решений, размещенный в Интернете, чтобы помочь запомнить шаги. В конце концов вам нужно запомнить все шаги самостоятельно без шаблона.
Домашнее задание Раздел 3.1- Выполнение задач 1, 2, 3, 5, 6
2 - Выполнение задач 1, 2, 3, 4
Чтобы проверить окончательные ответы на ВСЕ назначенные домашние задания в разделах 3.1 и 3.2 нажмите ЗДЕСЬ. Он откроется в новом окне или вкладке.
Если вам нужна дополнительная практика в главе 3, решите задачи обзора главы в разделе 3.3: 1-11
Шаблон для задач геометрического линейного программирования
Видео-примеры к главе 3
Видео: базовый пример решения линейной задачи MAXimum с использованием графического
метод
https://www.youtube.com/watch?v=M4K6HYLHREQ PatrickJMT
Видео: базовый пример решения линейной программы MAXimum с использованием графического
метод
https://www.youtube.
com/watch?v=YPn4yHM1YsU Общественный колледж Говарда
Видео: базовый пример решения задачи MINimum линейной программы с использованием графического
метод
https://www.youtube.com/watch?v=2ACJ9ewUC6U PatrickJMT
Глава 4 Симплексный метод
Вам нужна программа-калькулятор APIVOT для главы 4 , чтобы ускорить и упростить процедуры расчета симплексным методом. Эта программа автоматизирует все процедуры работы со строками, необходимые для выполнения симплексного метода для главы 4. Преподаватель загрузит программу-калькулятор для учащихся в классе. Эта программа работает только на калькуляторах семейств ТИ-83 и ТИ-84 . Его нельзя загрузить на другие модели или марки калькуляторов.
ИСПОЛЬЗУЙТЕ APIVOT программы TI-83+ или TI-84+ для выполнения симплекс-метода.
НЕ выполняйте операции со строками отдельно для опорных точек, если только вы не получили
эту программу скачал на свой калькулятор у инструктора.
Вы немного узнали о том, как компьютеры используют процедуры, называемые алгоритмами , для решения задач, так что когда/если вы используете компьютер для решения подобной задачи в будущем это не совсем «волшебство» для вас в том, как это решается.
Видеопример для раздела 4.2 Симплексный метод (Стандарт Макс): Если вам нужна ВИДЕО помощь: Видео: базовый пример решения стандартной задачи максимума линейной программы с использованием
симплексный метод
Две вещи здесь выполняются иначе, чем в нашем классе
1) он использует букву s в качестве символа для слабых переменных, но наша книга и класс
используйте букву y в качестве символа для переменных резерва
2) он показывает операции со строками для поворотного шага.
На нашем уроке мы используем калькулятор
программа АПИВОТ для автоматизации работы по этим рядовым операциям
https://www.youtube.com/watch?v=M5szdUhYxFI Кевин Пинегар
- ПРОЧИТАЙТЕ этот раздел, чтобы узнать, как линейное программирование используется в реальных Мир.
- Домашнее задание по разделу 4.1 не задано
Напишите эти текстовые задачи в форме линейной программы, указав, минимизируете ли вы или максимизация, сформулируйте целевую функцию и укажите все ограничения.
Раздел 4.
2. Задачи 3, 4, 5
Раздел 4.4. Повторите задачи 9 и 10
симплексный метод.
Для Задания Часть А просто напишите линейную программу в стандартной форме.
2 Практические задачи по настройке линейных программ с 2 или 3 переменными, СМЕШАННЫЕ ограничения
Откроется в новой вкладке или окне в виде файла PDF. Решения находятся на второй странице,
чтобы проверить свои ответы.
Запишите эти задачи в форме линейной программы, указав, минимизируете ли вы или
максимизация, сформулируйте целевую функцию и укажите все ограничения.
НЕ решайте эти проблемы. (Если вы действительно хотите их решить, используйте линейную программу.
Ссылка Simplex Tool в верхней части этой страницы для решения с использованием технологии.)
Раздел 4.
2 Метод простого для стандартных максимальных задач
- Должны 1, 3, 4, 5 и раздел 4.4 Проблемы 9 и 10
- Если вам нужна дополнительная практика:
- Раздел 4.2 Задача 2 для механиков
- Раздел 4.4 Повторение задач: 1, 2, 3, 4, 5 для механики
- Раздел 4.4 Обзор задачи 10 для проблем с прикладными словами
Настоятельно рекомендуется решать как можно больше практических задач!
*** Глава 4 Задание, часть CРаздел 4.3. Настройка моделей линейного программирования как целевой функции и ограничений
НЕ выполняйте задание, часть D ниже.