Загальна задача лінійного програмування і деякі з методів її розвязування (стр. 1 из 2)

Реферат на тему:

Загальна задача лінійного програмування і деякі з методів її розв’язування.

План.

1. Модифікований симплекс-метод розв’язування задач лінійного програмування.

2. Література

Модифікований симплекс метод.

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

де - номера базисних векторів, а коефіцієнти розкладу векторів , по векторах даного базису.

Усі вказані коефіцієнти потрібно визначати на кожній із ітерацій вичислю вального процесу. Ця необхідність відпадає при розв’язуванні задач лінійного програмування модифікованим симплекс - методом. В цьому випадку на кожній із ітерацій обчислюють вектор

де

- матриця обернена до матриці В, складеній із компонентів векторів даного базису, а потім знаходять числа за формулою

Знайдемо компоненти вектора W і чисел

у випадку розв’язування основної задачі лінійного програмування модифікованим симплекс-методом.

Нехай дана задача лінійного програмування записана у формі основної задачі і нехай для неї знайдений опорний план який визначається базисом утвореним векторами

Отже, відома матриця В, для якої можна знайти обернену матрицю . Подальші обчислення зручніше робити, якщо їх результати , як і при розв’язуванні задачі симплексним методом оформлювти у виді таблиць. У цьому випадку, при переході від однієї так званої головної таблиці до другої, використовується допоміжна таблиця. Допоміжна таблиця (1.1) відрізняється від звичайної симплекс-таблиці тим, що в ній знаходяться доповнюючі стовпці та рядки в яких відповідно записують координати векторів і значення , які отримуємо в процесі розв’язування задачі.

Створена таблиця (1.2) відрізняється від звичайної симплекс-таблиці: по-перше тим, що замість стовпців векторів

із відповідними числами записують стовпці векторів , координатами яких являються відповідні стовбці матриці ; по-друге в (т+1)-му рядку записують компоненти векторів W, а не числа ; по –третє табл. 1.2 має один доповнюючий стовпець у перших т рядках якого записують координати вектора у базисі і який було б доцільно ввести в базис у наступній ітерації.

Щоб визначити вектор

спочатку знаходять вектор . Його компоненти визначають як скалярний добуток вектора на відповідні вектори по формулі (1). Знайдені компоненти вектора записують у останньому рядку таблиці (1.2) і у рядку таблиці (1.1). Після цього по формулі (2) знаходять елементи (т+1) – го рядка допоміжної таблиці. Якщо серед знайдених чисел (т+1)-го рядка допоміжної таблиці немає від’ємних, то вихідний опорний план виявляється оптимальним. Якщо таке є , то або задача не має розв‘язків, або можна перейти до нового опорного плану, при якому значення цільової функції не зменшиться. Для визначення цього вибирають серед від‘ємних чисел (т+1)-го рядка таблиці (1.1) найбільше по абсолютній величині. В такому випадку, коли таких чисел декілька, одне. Нехай таким числом буде . Тоді останній рядок таблиці (1.2) відводять для вектора . У перших т рядках цього стовпця записують компоненти вектора у базисі . Вони отримуються у результаті множення матриці , записаної у таблиці (1.2) на вектор компоненти якого вказані у таблиці (1.2). Після знаходження чисел виясняють, є серед них додатні чи ні. Якщо таких чисел має, то задача не має розв‘язку. Якщо є додатні числа переходять до нового опорного плану задачі. Для цього знаходять .

Нехай

. Тоді новий опорний план визначається базисом , отриманим із попереднього виключенням із нього вектора і введенням замість нього вектора . Вважаючи елемент дозвільним, а r-ий рядок і стовпець направляючим, переходять до нової основної таблиці. Перший т стовпець векторів нової таблиці знаходять по відомим правилам переходу від однієї симплекс – таблиці до другої, розглянутим вище. Після того як ці елементи знайдені, знаходять вектор . Компоненти цього вектора записують як і в новій основній таблиці так і в допоміжній таблиці (1.1). Потім вираховують числа і перевіряють новий опорний план на оптимальність. Якщо план не оптимальний, то або встановлюють незакінченість попередньої задачі, або переходять до нового опорного плану. Продовжуючи інтеграційний процес, після скінченого числа кроків або знаходять оптимальний план задачі, або встановлюють її нерозв’язність.

Таким чином, процес знаходження розв‘язку задачі модифікованим симплекс – методом включає наступні етапи:

1. Знаходять опорний план задачі.

2. Обчислюють матрицю

, обернену матриці В , складену із компонентів векторів вихідного базису.

3. Знаходять вектор

4. Обчислюють числа

.Якщо усі не від’ємні , то опорний план який ми шукаємо є оптимальним. Якщо серед чисел є від’ємні , то вибирають серед них найбільше по абсолютній величині. Нехай це .

5. Обчислюють компоненти вектора

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