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

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

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

При решении задач линейного программирования графическим методом присутствуют система ограничений с двумя неизвестными 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  

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

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