Формы задач линейного программирования

Решение задач линейного программирования

Види галузей системи міжнародного права

Види галузей МІГ, їх місце в системі МП та взаємодія обумовлені як об'єктивними, так і суб'єктивними факторами.

В систему МП, яка має об'єктивний характер входять основні принципи та галузі МП. Єдиного офіційного переліку таких галузей не існує, але можна запропонувати перелік галузей права, що визнається більшістю юристів-міжнародників:

1. Населення в міжнародному праві.

2. Правовий режим території в МП.

3. Право міжнародних договорів.

4. Міжнародне морське право.

5. Міжнародне повітряне право.

6. Міжнародне космічне право.

7. Дипломатичне та консульське право.

8. Право міжнародних організацій.

9. Право міжнародної безпеки.

10. Гуманітарне право.

11. Міжнародна боротьба зі злочинністю.

12. Міжнародно-правова відповідальність.

Компонентами галузей міжнародного права є інститути права. Інститут регулює певний вид міжнародних відносин відповідної галузі. Інколи інститути регулюють міжгалузеву сферу відносин. В таких випадках вони функціонують як міжгалузеві інститути.

Елементарний поділ системи міжнародного права здійснюється на рівні норми права

Система МП є системою відкритого типу. Постійно розширюється коло суб'єктів, а також об'єктів регулювання. Це пов'язано із розвитком вже існуючих галузей права, а також з появою нових. Серед відносно нових галузей права необхідно назвати:

міжнародне право захисту прав людини; міжнародне економічне право; міжнародне екологічне право; міжнародне атомне право тощо.

бб

Стандартная задача линейного программирования:

,

, (3.1)

.

Стандартная задача имеет важное значение ввиду того, что большое число прикладных моделей сводится именно к этому классу задач линейного программирования.

Каноническая задача линейного программирования:

,

, (3.2)

.

Основные вычислительные методы (симплекс-метод и его модификации) решения задач линейного программирования разработаны именно для канонической задачи.

Общая задача линейного программирования:

,

, (3.3)

.

Все три перечисленные задачи эквивалентны в том смысле, что каждую из них можно простыми преобразованиями привести к любой из двух остальных. Поэтому если есть способ решения одной из этих трех задач, то тем самым может быть решена и любая другая из двух остальных. Покажем, например, как можно привести стандартную задачу к канонической форме. Для этого введем в рассмотрение новые переменные , количество которых совпадает с числом ограничений в стандартной задаче, и рассмотрим следующую каноническую задачу:

,

,

, (3.4)

...

,

, ,

, .

Пусть решение сформулированной выше канонической задачи (3.4). Тогда решением исходной стандартной задачи является вектор . Без доказательства.

3.2. Система линейных уравнений с переменными

Рассмотрим систему уравнений ():

,

, (3.5)

...

.

Эта система может быть записана в виде: или в матричном виде: .

В задачах линейного программирования рассматриваются системы, в которых ранг матрицы , , меньше числа переменных, т.е. . Это означает, что наибольшее число независимых переменных уравнений системы равно . Далее будем полагать, что в системе (3.5) число независимых уравнений равно , т.е. .

Любые переменных системы линейных уравнений с неизвестными называются основными, или базисными, если определитель матрицы коэффициентов при них не равен нулю. Тогда остальные переменных называются небазисными. Учитывая, что максимально возможное число сочетаний из столбцов по равно , общее число комбинаций базисных переменных не превосходит .

Рассмотрим пример. Найти все возможные группы базисных переменных в системе

Общее число комбинаций базисных переменных не превосходит числа . Найти возможные комбинации базисных переменных! Выясним, например, являются ли базисными переменные .

Рассмотрим определитель из столбцов матрицы при переменных :

.

Следовательно, переменные являются базисными. Также можно выяснить, что базисными являются комбинации переменных , . Комбинации , , не являются базисными.

Базисным решением системы линейных уравнений с переменными называются решения, в котором все не основных переменных равны нулю.

В задачах линейного программирования особый интерес представляют допустимые базисные решения, или т.н. опорные планы.

Пример. Найти все базисные решения следующей системы:

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

откуда , , следовательно, первое базисное решение допустимое. Если взять за основные переменные и приравнять нулю остальные не основные переменные , получим второе базисное решение . Аналогично, можно найти и третье базисное решение , которое в силу отрицательности последней компоненты не является допустимым.

Дата добавления: 2014-01-05