Мітки: система обмежень

Знаходження розв’язку задачі дробово-лінійного програмування шляхом зведення її до задачі лінійного програмування

Нехай, знову-таки, розглядається задача математичного програмування, яка полягає у відшуканні екстремального (мінімального чи максимального) значення функції мети:

при наступних обмеженнях:

Крім того, передбачається, що в області невід’ємних розв’язків системи рівнянь (2) має місце нерівність .

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

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

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

при наступних обмеженнях:

Щоб знайти рішення задачі (1) – (3), спочатку, як і у випадку задачі лінійного програмування, знаходимо багатокутник рішень, який визначається обмеженнями (2) і (3). Припускаючи, що цей багатокутник не порожній, покладаємо значення функції (1) рівним деякому числу :

Задача дробово-лінійного програмування. Математична модель задачі дробово-лінійного програмування

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

Розв’язок задачі лінійного програмування двоїстим симплекс методом в середовищі програмування delphi

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

Далі, перейдемо до детального розгляу кожного з елементів головної форми проекту, після чого, з його допомогою, знайдемо розв’язок конкретної задачі лінійного програмування. Отже, головне вікно програми ділиться на три частини:

Розв’язок задачі цілочисельного програмування графічним методом в середовищі Delphi

Графічний метод розв’язання задач цілочисельного програмування, як і для випадку задачі лінійного програмування, має обмежену область застосування, бо зазвичай використовується для задач з двома змінними. Тобто, кожна з нерівностей в системі обмежень задач такого типу, визначає на координатній площині деяку півплощину, а система нерівностей в цілому – перетин відповідних півплощин. Сукупність точок перетину даних півплощин називається областю допустимих рішень або багатокутником розв’язків. Даний багатокутник завжди являє собою опуклу фігуру, тобто має наступну властивість: якщо дві точки і належать цій фігурі, то і весь відрізок належить їй.

Розглянемо задачу цілочисельного програмування, та спробуємо розв’язати її використовуючи delphi-програму, яка реалізує даний метод. Норми витрат сировини на виробництво одного товару кожного виду, ціна одиниці товару а також загальна кількість сировини наведені в наступній таблиці: