Лекции по "Геополитике"

Лекція 4

Розглянемо другий тип задач, які можливо розв’язати за допомогою графічного методу.

До цього типу відноситься задача лінійного програмування, система обмежень якої містить n невідомих і m лінійно незалежних рівнянь, причому n – m = 2.

Використовуючи метод повного виключення, виконуємо m виключень (робимо m кроків), в результаті чого отримуємо загальний розв’язок системи обмежень. Базисних змінних m, вільних змінних n – m = 2. Таким чином, всі змінні виражаються через дві вільні змінні. Функцію цілі Z = с1х1 + с2х2 +...+ сnxn також виражаємо через ці дві вільні змінні, використовуючи Хобщ.

Після цього можемо записати задачу першого типу, еквівалентну вихідній. Вирішуємо цю задачу графічним методом. В результаті отримуємо екстремальне значення Z і відповідні значення вільних змінних. За допомогою спільного рішення знаходимо значення базисних змінних і записуємо Хопт.

Лекція 5

Двоїсті задачі

Кожній ЗЛП може бути поставлена у відповідність за певними правилами інша ЗЛП, яка називається двоїстою задачею. В цьому випадку вихідна ЗЛП називається прямою задачею.

Формальні правила побудови двоїстих задач

1) якщо вихідна задача є задачею максимізації, то двоїста буде задачею мінімізації і навпаки;

2) число змінних двоїстої задачі дорівнює числу основних обмежень вихідної задачі, а число основних обмежень двоїстої задачі дорівнює числу змінних вихідної задачі;

3) коефіцієнти цільової функції вихідної задачі стають правими частинами обмежень двоїстої задачі, а праві частини обмежень вихідної задачі стають коефіцієнтами цільової функції двоїстої задачі;

4) матриця системи основних обмежень двоїстої задачі будується за допомогою транспонування матриці системи основних обмежень вихідної задачі;

5) в системі обмежень задачі максимізації нерівності записуємо зі знаком меньше дорівнює, а в системі обмежень задачі мінімізації зі знаком більше дорівнює.

В несиметричних задачах система обмежень прямої задачі задається у вигляді рівностей, тому всі yi – вільні змінні, отже, можуть бути і від’ємними.

Перша теорема двоїстості.

Ця теорема складається з трьох тверджень.

1. Якщо задача I має розв’язок X*, то і задача II має розв’язок Y*. При цьому сХ* = Y* b*.

2. Якщо у однієї з пари двоїстих задач цільова функція не обмежена, то друга задача не має допустимих розв’язків.

3. Якщо одна з пари двоїстих задач не має припустимих розв’язків, то друга задача або також не має припустимих розв’язків, або має необмежену цільову функцію.

Зауважимо, що для неоптимальних (але допустимих) векторів X і Y завжди виконується співвідношення сХ <Yb.

Теорема існування. Якщо задачі I і II мають хоча б по одному допустимому вектору, то обидві задачі мають розв’язки.

Друга теорема двоїстості (теорема про доповнювальну нежорсткість).

Лекція 10

Поняття про цілочислове і нелінійне програмування

ЗАДАЧІ цілочислового програмування і сфери їх застосування

В задачах цілочислового програмування змінні є цілими неподільними величинами.

Класичні оптимізаційні цілочислові задачі

 задача про призначення

 задача про рюкзак

 задача про розкрой

Сфери застосування задач цілочислового програмування

 календарне планування,

 матеріально-технічне постачання,

 розміщення підприємств,

