| dbo:abstract
|
- برمجة الأعداد الصحيحة هي عبارة عن مسألة أمثَلة رياضية أو برنامج لدراسة الجدوى، الذي فيه بعض أو كل المتغيرات لابد ان تكون أعداد صحيحة. في كثير من الحالات هذا المصطلح يُعبِر عن البرمجة الخطية الصحيحة، التي فيها دالة الهدف والقيود تكون خطية.البرمجة الصحيحة هي مسألة غير حتمية متعددة الحدود مسائل NP صعبة.حالة خاصة: البرمجة الخطية الصحيحة تكون فيها المتغيرات المجهولة رقمية (0-1) هي مسألة حاسوبية وتُعتَبر من المسائل الحتمية متعددة الحدود. (ar)
- La programació lineal entera serveix per resoldre els problemes de programació lineal en què les variables han de prendre valor enters. Quan representem un problema de programació lineal ens podem trobar que només tenen sentit aquelles solucions de la regió factible, que les seves variables són nombres enters. Llavors estem davant d'un problema de programació lineal entera. Un problema de programació lineal entera es formula de la mateixa manera que un problema de programació lineal convencional, però amb la diferència que el resultat d'aquest es trobarà dins d'una regió factible, en aquesta trobarem diversos punts, però només són vàlids els que tenen unes coordenades enteres. Aquests problemes són a vegades fàcils de resoldre i a vegades impossibles, perquè no trobem cap punt dins de la regió factible que tingui coordenades enteres. Per resoldre aquests problemes s'utilitza el mètode gràfic. Aquest consisteix a representar la regió factible, dibuixar la funció objectiu i buscar en quin punt assoleix el màxim o el mínim. Una vegada buscat el màxim o el mínim, si aquests punts no tenen coordenades enteres s'ha de buscar quins punts amb coordenades enteres són pròxims aquests i en quins d'aquests s'obté el màxim o el mínim. (ca)
- Celočíselné programování je odvětví optimalizace, první úloha celočíselného programování byla řešena v roce 1958. (cs)
- Die ganzzahlige lineare Optimierung (auch ganzzahlige Optimierung) ist ein Teilgebiet der angewandten Mathematik. Wie die lineare Optimierung beschäftigt sie sich mit der Optimierung linearer Zielfunktionen über einer Menge, die durch lineare Gleichungen und Ungleichungen eingeschränkt ist. Der Unterschied liegt darin, dass in der ganzzahligen Optimierung einige oder alle Variablen nur ganzzahlige Werte annehmen dürfen und nicht beliebige reelle Werte wie in der linearen Optimierung. Die ganzzahlige Optimierung lässt sich geometrisch als Optimierung über einem konvexen Polyeder (einem höherdimensionalen Vieleck) auffassen und ist damit ein Spezialfall der konvexen Optimierung. Im Unterschied zur linearen Programmierung ist allerdings das zugrundeliegende Polyeder meist nicht genau bekannt, was das Problem aus komplexitätstheoretischer Sicht NP-schwer macht. Da mindestens eine Variable diskret, also nicht kontinuierlich ist, ist auch der Begriff diskrete Optimierung gebräuchlich. Eine weitere häufige Bezeichnung ist ganzzahlige (lineare) Programmierung (von engl. integer (linear) programming), wobei der Begriff Programm im Sinne von Planung zu verstehen ist und nicht im Sinne eines Computerprogramms. Er wurde schon in den 1940er Jahren von George Dantzig geprägt, bevor Computer zur Lösung von Optimierungsproblemen eingesetzt wurden. Noch stärker als die lineare hat sich die ganzzahlige Optimierung seit ihren Anfängen in den 1950er Jahren zu einem Modellierungs- und Optimierungswerkzeug für viele praktische Probleme entwickelt, für die keine speziellen Algorithmen bekannt sind. Durch bedeutende Fortschritte in der Entwicklung der Lösungsverfahren in den 1980er und 1990er Jahren hat die ganzzahlige Optimierung heute viele Anwendungen, beispielsweise in der Produktion, in der Planung von Telekommunikations- und Nahverkehrsnetzen und in der Tourenplanung. Zur Lösung ganzzahliger Optimierungsprobleme gibt es einerseits exakte Lösungsverfahren wie beispielsweise Branch-and-Bound und Schnittebenenverfahren, die auf der Lösung vieler ähnlicher linearer Programme basieren, und andererseits eine Vielzahl von Heuristiken. Trotzdem ist die Lösung ganzzahliger linearer Programme in der Praxis immer noch eine schwere Aufgabe, die je nach Größe und Struktur des zu lösenden Problems eine geschickte Modellierung und mehr oder weniger speziell entwickelte oder angepasste Algorithmen erfordert. Oft werden daher mehrere Lösungsverfahren kombiniert. (de)
- Un problema de programación en enteros es un programa de optimización o factibilidad matemática en el cual algunas o todas las variables tienen que ser enteras. En muchos escenarios el término se refiere a programación lineal en enteros (PLE), en el cual la función objetivo y las restricciones (aparte de las restricciones enteras) son lineales. La programación en enteros es NP-duro. Un caso especial, la programación lineal en enteros 0-1, en el cual las incógnitas son binarias, es uno de los 21 problemas NP-completo de Karp. (es)
- An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints (other than the integer constraints) are linear. Integer programming is NP-complete. In particular, the special case of 0-1 integer linear programming, in which unknowns are binary, and only the restrictions must be satisfied, is one of Karp's 21 NP-complete problems. If some decision variables are not discrete, the problem is known as a mixed-integer programming problem. (en)
- L'optimisation linéaire en nombres entiers (OLNE) (ou programmation linéaire en nombres entiers (PLNE) ou integer programming (IP) ou Integer Linear Programming (ILP)) est un domaine des mathématiques et de l'informatique théorique dans lequel on considère des problèmes d'optimisation d'une forme particulière. Ces problèmes sont décrits par une fonction de coût et des contraintes linéaires, et par des variables entières. La contrainte d'intégralité sur les variables, qui différencie l'OLNE de l'optimisation linéaire classique est nécessaire pour modéliser certains problèmes, en particulier des problèmes algorithmiques. Mais cette contrainte supplémentaire rend le problème plus complexe et demande des techniques particulières. (fr)
- 整数計画問題（せいすうけいかくもんだい）は、線型計画問題において、解ベクトルxの各要素を整数に限定した問題をいう。これはNP困難な問題に該当する。線型計画問題には多項式時間アルゴリズムが存在するのに対し、整数計画問題には存在しない。 解ベクトルxの各要素を0または1のみに限定したものを、特に0-1整数計画問題という。 (ja)
- 수학에서 정수 계획법(整數計劃法, 영어: Integer programming 인티저 프로그래밍[*])은 최적화 문제의 일종으로 주어진 정수 조건을 만족시키면서 목적 함수를 최적화하는 문제이다. (ko)
- Een geheeltallig programmering probleem is een wiskundig optimalisatie- of haalbaarheidsprogramma, waarin sommige of alle van de variabelen zich beperken tot de gehele getallen. In veel settings verwijst de term naar geheeltallige lineaire programmering, dat ook bekendstaat als gemengde geheeltallige programmering. Geheeltallige programmering is NP-moeilijk. Een speciaal geval is de 0-1 geheeltallige lineaire programmering, waarbij de onbekenden binair zijn, is een van de 21 NP-compleet problemen van Karp. (nl)
- Um Problema de Programação Inteira é um modelo de programação linear no qual algumas ou todas as variáveis do problema pertencem ao conjunto dos números inteiros. Quando todas as variáveis são inteira o modelo é denominado programação inteira pura; caso contrário, é denominado programação inteira mista. A solução de um Problema Linear Inteiro (PLI) aparenta ser fácil, no entanto produzir soluções para programas inteiros é um problema NP-difícil. (pt)
- Задача целочисленного программирования — это задача математической оптимизации или выполнимости, в которой некоторые или все переменные должны быть целыми числами. Часто термин адресуется к целочисленному линейному программированию (ЦЛП), в котором целевая функция и ограничения (за исключением требования целочисленности) линейны. Целочисленное программирование является NP-трудной задачей. Специальный случай, 0-1 целочисленное линейное программирование, в которой переменные принимают значения 0 или 1, является одной из 21 NP-полных задач Карпа. (ru)
- Цілочисельне програмування — різновид математичного програмування, що припускає, що шукані значення повинні бути цілими числами. Розділ математичного програмування, у якому вивчаються методи знаходження екстремумів функцій у просторі параметрів, де всі або деякі змінні є цілими числами. Найпростіший метод розв'язання задачі цілочисельного програмування — зведення її до задачі лінійного програмування з перевіркою результату на цілочисельність. (uk)
|
| rdfs:comment
|
- برمجة الأعداد الصحيحة هي عبارة عن مسألة أمثَلة رياضية أو برنامج لدراسة الجدوى، الذي فيه بعض أو كل المتغيرات لابد ان تكون أعداد صحيحة. في كثير من الحالات هذا المصطلح يُعبِر عن البرمجة الخطية الصحيحة، التي فيها دالة الهدف والقيود تكون خطية.البرمجة الصحيحة هي مسألة غير حتمية متعددة الحدود مسائل NP صعبة.حالة خاصة: البرمجة الخطية الصحيحة تكون فيها المتغيرات المجهولة رقمية (0-1) هي مسألة حاسوبية وتُعتَبر من المسائل الحتمية متعددة الحدود. (ar)
- Celočíselné programování je odvětví optimalizace, první úloha celočíselného programování byla řešena v roce 1958. (cs)
- Un problema de programación en enteros es un programa de optimización o factibilidad matemática en el cual algunas o todas las variables tienen que ser enteras. En muchos escenarios el término se refiere a programación lineal en enteros (PLE), en el cual la función objetivo y las restricciones (aparte de las restricciones enteras) son lineales. La programación en enteros es NP-duro. Un caso especial, la programación lineal en enteros 0-1, en el cual las incógnitas son binarias, es uno de los 21 problemas NP-completo de Karp. (es)
- 整数計画問題（せいすうけいかくもんだい）は、線型計画問題において、解ベクトルxの各要素を整数に限定した問題をいう。これはNP困難な問題に該当する。線型計画問題には多項式時間アルゴリズムが存在するのに対し、整数計画問題には存在しない。 解ベクトルxの各要素を0または1のみに限定したものを、特に0-1整数計画問題という。 (ja)
- 수학에서 정수 계획법(整數計劃法, 영어: Integer programming 인티저 프로그래밍[*])은 최적화 문제의 일종으로 주어진 정수 조건을 만족시키면서 목적 함수를 최적화하는 문제이다. (ko)
- Een geheeltallig programmering probleem is een wiskundig optimalisatie- of haalbaarheidsprogramma, waarin sommige of alle van de variabelen zich beperken tot de gehele getallen. In veel settings verwijst de term naar geheeltallige lineaire programmering, dat ook bekendstaat als gemengde geheeltallige programmering. Geheeltallige programmering is NP-moeilijk. Een speciaal geval is de 0-1 geheeltallige lineaire programmering, waarbij de onbekenden binair zijn, is een van de 21 NP-compleet problemen van Karp. (nl)
- Um Problema de Programação Inteira é um modelo de programação linear no qual algumas ou todas as variáveis do problema pertencem ao conjunto dos números inteiros. Quando todas as variáveis são inteira o modelo é denominado programação inteira pura; caso contrário, é denominado programação inteira mista. A solução de um Problema Linear Inteiro (PLI) aparenta ser fácil, no entanto produzir soluções para programas inteiros é um problema NP-difícil. (pt)
- Задача целочисленного программирования — это задача математической оптимизации или выполнимости, в которой некоторые или все переменные должны быть целыми числами. Часто термин адресуется к целочисленному линейному программированию (ЦЛП), в котором целевая функция и ограничения (за исключением требования целочисленности) линейны. Целочисленное программирование является NP-трудной задачей. Специальный случай, 0-1 целочисленное линейное программирование, в которой переменные принимают значения 0 или 1, является одной из 21 NP-полных задач Карпа. (ru)
- Цілочисельне програмування — різновид математичного програмування, що припускає, що шукані значення повинні бути цілими числами. Розділ математичного програмування, у якому вивчаються методи знаходження екстремумів функцій у просторі параметрів, де всі або деякі змінні є цілими числами. Найпростіший метод розв'язання задачі цілочисельного програмування — зведення її до задачі лінійного програмування з перевіркою результату на цілочисельність. (uk)
- La programació lineal entera serveix per resoldre els problemes de programació lineal en què les variables han de prendre valor enters. Quan representem un problema de programació lineal ens podem trobar que només tenen sentit aquelles solucions de la regió factible, que les seves variables són nombres enters. Llavors estem davant d'un problema de programació lineal entera. Per resoldre aquests problemes s'utilitza el mètode gràfic. Aquest consisteix a representar la regió factible, dibuixar la funció objectiu i buscar en quin punt assoleix el màxim o el mínim. (ca)
- Die ganzzahlige lineare Optimierung (auch ganzzahlige Optimierung) ist ein Teilgebiet der angewandten Mathematik. Wie die lineare Optimierung beschäftigt sie sich mit der Optimierung linearer Zielfunktionen über einer Menge, die durch lineare Gleichungen und Ungleichungen eingeschränkt ist. Der Unterschied liegt darin, dass in der ganzzahligen Optimierung einige oder alle Variablen nur ganzzahlige Werte annehmen dürfen und nicht beliebige reelle Werte wie in der linearen Optimierung. Die ganzzahlige Optimierung lässt sich geometrisch als Optimierung über einem konvexen Polyeder (einem höherdimensionalen Vieleck) auffassen und ist damit ein Spezialfall der konvexen Optimierung. Im Unterschied zur linearen Programmierung ist allerdings das zugrundeliegende Polyeder meist nicht genau bekannt, (de)
- An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints (other than the integer constraints) are linear. Integer programming is NP-complete. In particular, the special case of 0-1 integer linear programming, in which unknowns are binary, and only the restrictions must be satisfied, is one of Karp's 21 NP-complete problems. (en)
- L'optimisation linéaire en nombres entiers (OLNE) (ou programmation linéaire en nombres entiers (PLNE) ou integer programming (IP) ou Integer Linear Programming (ILP)) est un domaine des mathématiques et de l'informatique théorique dans lequel on considère des problèmes d'optimisation d'une forme particulière. Ces problèmes sont décrits par une fonction de coût et des contraintes linéaires, et par des variables entières. (fr)
|
