Калькуляторы по целочисленному программированию
Задачи математического программирования, в которых наряду с обычными ограничениями накладывается требование целочисленности всех или некоторых компонент решения, изучает раздел математического программирования, который называется целочисленным программированием.- Графический метод решения задач целочисленного программирования (на основе графического метода решения задач линейного программирования)
- Метод Гомори (метод отсечений)
- Графический метод ветвей и границ
- Решение задачи коммивояжера
- Задача о назначении
- Задача о рюкзаке
Онлайн-калькуляторы по линейному программированию
С принципиальной точки зрения задача целочисленного программирования достаточно проста: для ее решения достаточно пронумеровать все целочисленные элементы множества допустимых решений и затем последовательно вычислять значения целевой функции в этих точках, запоминая на каждом шаге тот из уже проверенных элементов, для которого значение целевой функции было наибольшим (или наименьшим). Однако часто, особенно в экономических задачах, такая процедура практически нереализуема из-за очень большого или бесконечного числа элементов множества допустимых решений. Другой подход к решению этой задачи позволяет отбрасывать не отдельные точки, а достаточно большие подмножества заведомо неоптимальных элементов множества допустимых решений. Эта идея положена в основу алгоритмов, которые принято относить к методу ветвей и границ.
При решении задач линейного программирования графическим методом присутствуют система ограничений с двумя неизвестными 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 |
