Метод ветвей и границ онлайн калькулятор: Метод ветвей и границ онлайн

alexxlab / / Разное

Метод ветвей и границ онлайн

Назначение сервиса. Сервис предназначен для решения задач целочисленного линейного программирования в онлайн режиме методом ветвей и границ. Другое название метода — метод Ленд и Дойг. При двух переменных (x1, x2) применяется графическое решение, при большем количестве переменных — симплексный метод. В ходе решения формируется Дерево решения задачи.
  • Шаг №1
  • Шаг №2
  • Видеоинструкция
  • Оформление Word

Инструкция. Укажите количество переменных и число ограничений. Полученное решение сохраняется в формате MS Word с проверкой решения в MS Excel. Выберите количество переменных 2345678910
Выберите количество строк (количество ограничений) 12345678910
При этом ограничения типа xi ≥ 0 не учитывайте.

Суть метода ветвей и границ состоит в последовательном переборе вариантов, рассмотрении лишь тех из них, которые по определенным признакам оказываются перспективными, и отбрасывании бесперспективных вариантов.
При использовании метода ветвей и границ область допустимых решений (ОДР) исходной задачи определенным способом разбивается на непересекающиеся подмножества, и решаются подзадачи, т.е. задачи на этих подмножествах с той же ЦФ и без учета условия целочисленности (как задачи ЛП). Если в результате получено оптимальное нецелочисленное решение, ОДР подзадачи снова разбивается на части и этот процесс продолжается до тех пор, пока не будет найдено оптимальное целочисленное решение исходной задачи.
Если в задаче на максимум при решении подзадач получаются оптимальные целочисленные решения, то запоминаются те из них, которым соответствуют возрастающие значения ЦФ. Если полученное «непрерывное» решение подзадачи оказывается не лучше сохраненного целочисленного решения, то такая подзадача исключается из списка задач. Название этого метода объясняется тем, что в процессе решения задача последовательно «ветвится», разбиваясь на более простые подзадачи.

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

Пример №1. В задаче методом Гомори (или методом ветвей и границ) найти оптимальные решения задач целочисленного линейного программирования. Дать геометрическую интерпретацию процесса решений задач.
Z=3x1 + 2x2 → max
при ограничениях:
x1 + x2 ≤ 13
x1 — x2 ≤ 6
-3x1 + x2 ≤ 9
x1≥0, x2 ≥0
x1, x2 – целые числа.

Пример №2.
5x1 + 2x2 ≤ 14
2x1

+ 5x2 ≤ 16
x1 , x2 – целые числа
Z = 3x1 + 5x2 → max
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).


Оптимальное значение переменной x1=1. 81 оказалось нецелочисленным.
Разбиваем задачу 1 на две подзадачи 11 и 12.
В первой из них к условиям задачи 11 добавляется условие х1 ≥ 2, а к задаче 12 — условие х1 ≤ 1.
Эта процедура называется ветвлением по переменной х1.
Решим графически задачу 11 как задачу ЛП.
5x1+2x2≤14 (1)
2x1+5x2≤16 (2)
x1≥2 (3)
x
1≥0 (4)
x2≥0 (5)

Область допустимых решений представляет собой треугольник.
Прямая F(x) = const пересекает область в точке B. Так как точка B получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых:
5x1+2x2≤14
x1≥2

Решив систему уравнений, получим: x1 = 2, x2 = 2
Откуда найдем максимальное значение целевой функции:
F(X) = 3*2 + 5*2 = 16


Решение задачи получилось целочисленным.
Новое значение текущего рекорда будет равно F(X) = 16.
Так как найденная точка является первым целочисленным решением, то ее и соответствующее ей значение ЦФ следует запомнить. Сама точка называется текущим целочисленным рекордом или просто рекордом, а оптимальное значение целочисленной задачи —
текущим значением рекорда. Это значение является нижней границей оптимального значения исходной задачи Z*.

Решим графически задачу 12 как задачу ЛП.
5x1+2x2≤14 (1)
2x1+5x2≤16 (2)
x1≤1 (3)
x1≥0 (4)
x2≥0 (5)

Область допустимых решений представляет собой многоугольник
Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:
2x1+5x2≤16
x1≤1

Решив систему уравнений, получим: x1 = 1, x2 = 2. 8
Откуда найдем максимальное значение целевой функции:

F(X) = 3*1 + 5*2.8 = 17


Оптимальное значение переменной x2=2.8 оказалось нецелочисленным.
Разбиваем задачу 12 на две подзадачи 121 и 122.
В первой из них к условиям задачи 121 добавляется условие х2 ≥ 3, а к задаче 122 — условие х2 ≤ 2.

Решим графически задачу 121 как задачу ЛП.
5x1+2x2≤14 (1)
2x1+5x2≤16 (2)
x1≤1 (3)
x2≥3 (4)
x1≥0 (5)
x2≥0 (6)

Решим графически задачу 122 как задачу ЛП.
5x1+2x2≤14 (1)
2x1+5x2≤16 (2)
x1≤1 (3)
x2≤2 (4)
x1≥0 (5)
x2≥0 (6)


Текущий рекорд Z=16≥13, поэтому прекращаем ветвление из этой вершины
Оптимальное значение переменной x
1=0. 5 оказалось нецелочисленным.
Разбиваем задачу 121 на две подзадачи 1211 и 1212.
В первой из них к условиям задачи 1211 добавляется условие х1 ≥ 1, а к задаче 1212 — условие х1 = 0.

Решим графически задачу 1211 как задачу ЛП.
5x1+2x2≤14 (1)
2x1+5x2≤16 (2)
x1≤1 (3)
x2≥3 (4)
x1≥1 (5)
x1≥0 (6)
x2≥0 (7)
Сведем систему ограничений к следующему виду:
5x1+2x2≤14 (1)
2x1+5x2≤16 (2)
x1=1 (3)
x2≥3 (4)
x1≥0 (5)
x2≥0 (6)
Задача не имеет допустимых решений. ОДР представляет собой пустое множество.


Задача 1211 не имеет решения, поэтому для нее процесс ветвления прерываем.

Решим графически задачу 1212 как задачу ЛП.
5x1+2x2≤14 (1)
2x1+5x2≤16 (2)
x1≤1 (3)
x2≥3 (4)
x1=0 (5)
x1≥0 (6)
x2≥0 (7)


Текущий рекорд Z=16≥16, поэтому прекращаем ветвление из этой вершины
Оптимальное значение переменной x2=2.48 оказалось нецелочисленным. Разбиваем задачу 1 на две подзадачи 11 и 12.
В первой из них к условиям задачи 11 добавляется условие х2 ≥ 3, а к задаче 12 — условие х2 ≤ 2.
Эта процедура называется ветвлением по переменной х2.

Решим графически задачу 11 как задачу ЛП.

5x1+2x2≤14 (1)
2x1+5x2≤16 (2)
x2≥3 (3)
x1≥0 (4)
x2≥0 (5)


Решим графически задачу 12 как задачу ЛП.
5x1+2x2≤14 (1)
2x1+5x2≤16 (2)
x2≤2 (3)
x1≥0 (4)
x2≥0 (5)
Текущий рекорд Z=16≥16, поэтому прекращаем ветвление из этой вершины
Оптимальное значение переменной x1=0. 5 оказалось нецелочисленным. Разбиваем задачу 11 на две подзадачи 111 и 112. В первой из них к условиям задачи 111 добавляется условие х1 ≥ 1, а к задаче 112 — условие х1 = 0.

Решим графически задачу 111 как задачу ЛП.
5x1+2x2

≤14 (1)
2x1+5x2≤16 (2)
x2≥3 (3)
x1≥1 (4)
x1≥0 (5)
x2≥0 (6) Задача не имеет допустимых решений. ОДР представляет собой пустое множество


Задача 111 не имеет решения, поэтому для нее процесс ветвления прерываем.

Решим графически задачу 112 как задачу ЛП.
5x1+2x2≤14 (1)
2x1+5x2≤16 (2)
x2≥3 (3)
x1=0 (4)
x1≥0 (5)
x2≥0 (6)


Текущий рекорд Z=16≥16, поэтому прекращаем ветвление из этой вершины
F(X) = 16
x1 = 2
x2 = 2

Дерево решения задачи

Калькуляторы по целочисленному программированию

Задачи математического программирования, в которых наряду с обычными ограничениями накладывается требование целочисленности всех или некоторых компонент решения, изучает раздел математического программирования, который называется
целочисленным программированием.
  1. Графический метод решения задач целочисленного программирования (на основе графического метода решения задач линейного программирования)
  2. Метод Гомори (метод отсечений)
  3. Графический метод ветвей и границ
  4. Решение задачи коммивояжера
  5. Задача о назначении
  6. Задача о рюкзаке

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

При решении задач линейного программирования графическим методом присутствуют система ограничений с двумя неизвестными X1, X2 и целевая функция F(x).

Если заданы 3 и более переменных, то сначала необходимо исключить все X2+i (т.е. в системе уравнений должны остаться только две переменные). Исключение переменных обычно проводится методом Гаусса. Сначала выражается x3 и подставляется во все уравнения (и в целевую функцию тоже), затем x4 и так далее, пока в системе не останется две переменные x1 и x2. Второй способ решения — привести ЗЛП к СЗЛП (см. сервис Решение задач линейного программирования).

В сервисе необходимо сначала задать количество ограничений, а затем заполнить коэффициенты при неизвестных. Например,
0.1x1+0.2x2≤1100
0.05x1-0.02x2≤120

Здесь количество строк k = 2.

Коэффициент при неизвестных:
0.1;0.2
0.05;-0.02

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

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

Наименование показателя Нормы на одно изделие Прибыль на одно изделие
Ресурс 1 Ресурс 2 Ресурс 3
Изделие 1 2.2 8.4 4.2 35
Изделие 2 8.2 4.6 2.0 50
Наличие ресурсов 500 720 300  
необходимо привести к другому виду:
Нормы на одно изделие Изделие 1 Изделие 2 Наличие ресурсов
Ресурс 1 2. 2 8.2 500
Ресурс 2 8.4 4.6 720
Ресурс 3 4.2 2.0 300
Прибыль на одно изделие 35 50  

Целочисленное программирование: методы ветвей и границ

  • Андерсен Э.Д., Гондзио Дж., Месарош С., Сюй Х (1996) Реализация методов внутренних точек для крупномасштабного линейного программирования. В: Терлаки Т. (ред.) Методы внутренних точек в математическом программировании. Kluwer, Дордрехт, ftp://ftp.sztaki.hu/pub/oplab/PAPERS/kluwer.ps.Z

    Google ученый

  • Эпплгейт Д., Биксби Р.Э., Хватал В., Кук В. (1998) О решении задач коммивояжера. Документа по математике нет. Дополнительный том. проц. ИКМ III: 645–656

    Google ученый

  • Бейкер Э. К. (1981) Эффективные эвристические алгоритмы для решения задачи взвешенного покрытия множеств. Comput Oper Res 8:303–310

    CrossRef Google ученый

  • Бейкер Э.К., Фишер М.Л. (1981) Результаты вычислений для очень больших задач планирования экипажей. OMEGA Internat J Management Sci 19:613–618

    CrossRef Google ученый

  • Балас Э., Мартин Ч. (1980) Свод и дополнение: эвристика для программирования 0/1. Managem Sci 26: 86–96

    MathSciNet МАТЕМАТИКА Google ученый

  • Болдик Р. (1992) Рандомизированная эвристика для программирования смешанных целых чисел с ограничениями неравенства. Технический отчет Отдел электротехники и компьютеров Engin Worcester Polytechnic Inst

    Google ученый

  • Beale EML (1979) Методы ветвей и границ для систем математического программирования. Ann Discret Math 5: 201–219

    CrossRef MathSciNet МАТЕМАТИКА Google ученый

  • Beale EML, Tomlin JA (1970) Специальные средства в общей системе математического программирования для невыпуклых задачи с использованием упорядоченных наборов переменных. В: Lawerence J (ed) Proc. Пятый междунар. конф. Опер. Res., Tavistock Publ., стр. 447–454

    Google ученый

  • Бизли Дж. Э., Чу П. С. (1996) Генетический алгоритм для задачи покрытия множества. Europ J Oper Res 194:392–404

    CrossRef Google ученый

  • Бенишу М., Готье Ж.М., Жироде П., Хентгес Г., Рибьер Г., Винсент О. (1971) Эксперименты по смешанному целочисленному линейному программированию. Математическая программа 1:76–94

    CrossRef МАТЕМАТИКА Google ученый

  • Benichou M, Gauthier JM, Hehntges G, Ribiere G (1977) Эффективное решение крупномасштабных задач линейного программирования — некоторые алгоритмические методы и результаты вычислений. Программа по математике 13:280–322

    CrossRef МАТЕМАТИКА Google ученый

  • Bixby RE, Cook W, Cox A, Lee EK (1995) Параллельное смешанное целочисленное программирование. Центр технических отчетов Res Parallel Computation, Rice Univ CRPC-TR95554

    Google ученый

  • Биксби Р.Е., Кук В., Кокс А., Ли Э.К. (1999) Опыт вычислений с параллельным смешанным целочисленным программированием в распределенной среде. Ann Oper Res 90:19–43

    CrossRef MathSciNet МАТЕМАТИКА Google ученый

  • Биксби Р.Е., Ли Э.К. (1998) Решение задачи планирования отправки грузовых автомобилей с использованием метода ответвлений и разрезов. Оперативное разрешение 46:355–367

    МАТЕМАТИКА Google ученый

  • Биксби Р. Е., Вагнер Д.К. (1987) Замечание по обнаружению простых избыточностей в линейных системах. Oper Res Lett 6:15–18

    CrossRef MathSciNet МАТЕМАТИКА Google ученый

  • Bonomi E, Lutton JL (1984) Задача коммивояжера N-города: статистическая механика и алгоритм мегаполиса. SIAM Rev 26:551–568

    CrossRef MathSciNet МАТЕМАТИКА Google ученый

  • Борчерс Б., Митчелл Дж. Э. (март 1991 г.) Использование метода внутренних точек в алгоритме ветвей и границ для целочисленного программирования. Технический отчет Math Sci Rensselaer Polytech Inst 195

    Google ученый

  • Брэдли Г.Х., Хаммер П.Л., Уолси Л. (1975) Сокращение коэффициента в 0–1 переменных. Математическая программа 7: 263–282

    CrossRef MathSciNet Google ученый

  • Бреарли А. Л., Митра Г., Уильямс Х.П. (1975) Анализ задач математического программирования перед применением симплекс-метода. Программа по математике 5:54–83

    CrossRef MathSciNet Google ученый

  • Breu R, Burdet CA (1974) Эксперименты с ветвями и границами в программировании с нулевой единицей. Математическая программа 2:1–50

    MathSciNet Google ученый

  • Conn AR, Cornuejols G (1987) Проекционный метод для задачи о местоположении недееспособного объекта. Технический отчет Высшая школа Industr Admin Carnegie-Mellon Univ 26-86-87

    Google ученый

  • Краудер Х., Джонсон Э.Л., Падберг М. (1983) Решение крупномасштабной задачи линейного программирования ноль-единица. Оперативное разрешение 31:803–834

    МАТЕМАТИКА Google ученый

  • Дакин Р. Дж. (1965) Алгоритм поиска по дереву для задач смешанного целочисленного программирования. Вычисление J 8: 250–255

    Перекрёстная ссылка MathSciNet МАТЕМАТИКА Google ученый

  • Дитрих Б., Эскудеро Л. (1990) Сокращение коэффициентов для ограничений типа рюкзака в программах 0/1 с переменными верхними границами. Oper Res Lett 9:9–14

    CrossRef MathSciNet МАТЕМАТИКА Google ученый

  • Driebeek NJ (1966) Алгоритм решения задач смешанного целочисленного программирования. Менеджмент науки 21: 576–587

    Google ученый

  • Эрленкоттер Д. (1978 г.) Двойная процедура определения местонахождения нетрудоспособного объекта. Оперативное разрешение 26: 992–1009

    MathSciNet МАТЕМАТИКА Google ученый

  • Фенелон М. (1991) Стратегии ветвления для MIP. КПЛЕКС

    Google ученый

  • Fisher ML, Jaikumer R (1981) Обобщенная эвристика назначения для маршрута транспорта. Сети 11:109–124

    Перекрестная ссылка MathSciNet Google ученый

  • Форрест Дж.Дж., Херст Дж.П.Х., Томлин Дж.А. (1974) Практическое решение больших задач программирования смешанных целых чисел с помощью UMPIRE. Managem Sci 20: 736–773

    MathSciNet МАТЕМАТИКА Google ученый

  • Гэри М.Р., Джонсон Д.С. (1979) Компьютеры и неразрешимость — Руководство по теории NP-полноты. Фриман, Нью-Йорк

    МАТЕМАТИКА Google ученый

  • Gauthier JM, Ribiere G (1977) Эксперименты по смешанному целочисленному программированию с использованием псевдостоимости. Программа по математике 12:26–47

    CrossRef MathSciNet МАТЕМАТИКА Google ученый

  • Голдберг Д.Е. (1989)Генетические алгоритмы в поиске, оптимизации и машинном обучении. Аддисон-Уэсли, Рединг, Массачусетс

    МАТЕМАТИКА Google ученый

  • Гиньяр М., Спилберг К. (1981) Методы логической редукции в программировании с нулевой единицей. Оперативное разрешение 29:49–74

    MathSciNet МАТЕМАТИКА Google ученый

  • Хоффман К.Л., Падберг М. (1991) Улучшение LP-представлений линейных программ ноль-единица для ветвления и вырезания. ORSA J Comput 3:121–134

    МАТЕМАТИКА Google ученый

  • Хоффман К.Л., Падберг М. (1992) Решение проблем с расписанием экипажей авиакомпаний методом ветвления и сокращения. Менеджмент науки 39: 657–682

    Google ученый

  • Ибарра О.Х., Ким К.Э. (1975) Алгоритмы быстрой аппроксимации для задач о рюкзаке и сумме подмножеств. J ACM 22:463–468

    CrossRef MathSciNet МАТЕМАТИКА Google ученый

  • Крускал Дж. Б. (1956) О кратчайшем остовном поддереве графа и задаче коммивояжера. Proc Amer Math Soc 7: 48–50

    Перекрёстная ссылка MathSciNet Google ученый

  • Kuehn AA, Hamburger MJ (1963) Эвристическая программа для поиска складов. Менеджмент науки 19: 643–666

    Google ученый

  • Лэнд А.Х., Дойг А.Г. (1960) Автоматический метод решения задач дискретного программирования. Econometrica 28:497–520

    CrossRef MathSciNet МАТЕМАТИКА Google ученый

  • Лэнд А. Х., Пауэлл С. (1979) Компьютерные коды для задач целочисленного программирования. Ann Discret Math 5: 221–269

    CrossRef MathSciNet МАТЕМАТИКА Google ученый

  • Лоулер Э.Л. (1979) Алгоритмы быстрой аппроксимации для задач о рюкзаке. Math Oper Res 4: 339–356

    MathSciNet МАТЕМАТИКА Google ученый

  • Ли Э.К., Митчелл Дж.Э. (1996) Вычислительный опыт в нелинейном смешанном целочисленном программировании. В: Опер. Рез. проц. 1996. Springer, Берлин, стр. 95–100

    . Google ученый

  • Lee EK, Mitchell JE (2000) Опыт вычислений алгоритма SQP с внутренней точкой в ​​​​параллельной структуре ветвей и границ. В: Френк Х. и др. (ред.) Оптимизация высокой производительности. Клювер, Дордрехт, стр. 329–347 (глава 13).

    Google ученый

  • Лин С. , Керниган Б.В. (1973) Эффективный эвристический алгоритм для задачи коммивояжера. Оперативное разрешение 21: 498–516

    MathSciNet МАТЕМАТИКА Google ученый

  • Люстиг И.Дж., Марстен Р.Е., Шанно Д.Ф. (1994) Методы внутренних точек для линейного программирования: современный уровень вычислительной техники. ORSA J Comput 6 (1): 1–14. см. также следующие комментарии и ответ

    MathSciNet МАТЕМАТИКА Google ученый

  • Манне А.С. (1964) Размещение завода в условиях экономии за счет масштаба – децентрализации и вычислений. Менеджмент науки 11:213–235

    Google ученый

  • Митра Г. (1973) Исследование некоторых стратегий ветвей и границ для решения смешанных целочисленных линейных программ. Программа по математике 4:155–170

    CrossRef МАТЕМАТИКА Google ученый

  • Nemhauser GL, Wolsey LA (1988) Целочисленная и комбинаторная оптимизация. Wiley, Нью-Йорк

    МАТЕМАТИКА Google ученый

  • Падберг М., Ринальди Г. (1989) Подход к задаче коммивояжёра с боковыми ограничениями на основе ветвей и разрезов. Managem Sci 35: 1393–1412

    MathSciNet МАТЕМАТИКА Google ученый

  • Падберг М., Ринальди Г. (1991) Алгоритм ветвления и разреза для решения крупномасштабных симметричных задач коммивояжера. СИАМ Откр. 33:60–100

    Перекрёстная ссылка MathSciNet МАТЕМАТИКА Google ученый

  • Паркер Р.Г., Рардин Р.Л. (1988) Дискретная оптимизация. акад. Press, Нью-Йорк

    МАТЕМАТИКА Google ученый

  • Rosenkrantz DJ, Stearns RE, Lewis PM (1977) Анализ нескольких эвристик для задачи коммивояжера. SIAM J Comput 6: 563–581

    CrossRef MathSciNet МАТЕМАТИКА Google ученый

  • Сахни С. (1975) Приближенные алгоритмы для задачи о рюкзаке 0–1. J ACM 22:115–124

    CrossRef MathSciNet МАТЕМАТИКА Google ученый

  • Savelsbergh MWP (1994) Предварительная обработка и исследование задач смешанного целочисленного программирования. ORSA J Comput 6: 445–454

    MathSciNet МАТЕМАТИКА Google ученый

  • де Сильва А., Абрамсон Д. (1998) Метод параллельных внутренних точек и его применение к задачам размещения объектов. Приложение Comput Optim 9:249–273

    CrossRef MathSciNet МАТЕМАТИКА Google ученый

  • Спилберг К. (1969) Алгоритмы решения простой задачи размещения объекта с некоторыми побочными условиями. Оперативное разрешение 17:85–111

    МАТЕМАТИКА Google ученый

  • Томлин Дж. А. (1971) Усовершенствованный метод ветвей и границ для целочисленного программирования. Опера Рез 19:1070–1075

    MathSciNet МАТЕМАТИКА Google ученый

    • линейное программирование. Как ввести переменную > переменное ограничение неравенства в калькулятор симплекс-метода?

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

    спросил

    Изменено 1 год, 11 месяцев назад

    Просмотрено 102 раза

    $\begingroup$

    В задачах линейного программирования с двумя переменными ограничения могут принимать форму либо $aX+bY < C$, либо $mX > nY$. График обеих линий образует линейные границы, поэтому применяется графическое решение. Но в задачах с 3+ переменными нужно использовать симплекс-метод, а калькуляторы для симплекс-метода, по-видимому, не принимают ограничений вида $mX > nY$.

    Я пытался преобразовать их алгебраически в $mX-nY > 0$, но в задаче с двумя переменными симплекс-калькулятор выдает «нет решения», когда графический метод находит решение. Есть ли другой способ ввести такие ограничения в симплексных калькуляторах?

    Вот проблема, которую я пробовал:

    Развернуть: $Z=5x+7y$

    $x+y≤30$

    $2x+y≤50$

    $4x+3y≥60$

    $2x ≥y$

    $x≥0,y≥0$

    Графическим методом найдено решение $x=10, y=20, Z=190$.

    Я ввел это в онлайн-калькулятор здесь как

    $F(x)=5X1+7X2$

    $1X1+1X2≤30$

    $2X1+1X2≤50$

    $4X1+3X2≤60$

    $2X1+-1X2≥0$

    И возвращает:

    «Ответ:

    Система не имеет решений или имеет много решений.»

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

    $\endgroup$

    5

    $\begingroup$

    Вы изменили $\ge 60$ на $\le 60$, и вам также необходимо указать границы $\ge 0$.

    No related posts.

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

    Ваш адрес email не будет опубликован. Обязательные поля помечены *