Програмна реалізація методу штучного базису в середовищі delphi

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

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

Читати повністю

Побудова оптимального плану транспортної задачі розподільчим методом в середовищі програмування delphi

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

Читати повністю

Розв'язок транспортної задачі розподільчим методом

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

Читати повністю

Рішення транспортної задачі методом диференціальних рент в середовищі програмування delphi

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

Головне вікно розглядуваного delphi-проекту ділиться на три частини: панелі інструментів (складається з двох компонентів типу TSpinEdit та двох кнопок типу TButton), робочої області (містить транспортну таблицю) та статусного рядка, основним призначенням якого є вивід загальної вартості перевезень згідно побудованого оптимального плану. Розглянемо призначення кожного з цих елементів більш детально:

Читати повністю

Використання методу диференціальних рент для знаходження оптимального плану транспортної задачі

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

  1. У кожному стовпчику транспортної таблиці знаходимо мінімальний тариф. Знайдені тарифи позначаємо колами, що їх оточують, і заповнюємо відповідні комірки максимально можливими перевезеннями. Таким чином, отримуємо розподіл, що в загальному може не задовільняти обмеженням транспортної задачі (якщо отриманий таким чином розподіл задовільняє обмеженням задачі, то він вважається оптимальним, і алгоритм методу диференціальних рент на цьому закінчується).
  2. Скорочуємо нерозподілені поставки продукту так, щоб при цьому загальна вартість перевезень залишалась мінімальною. Для цього виконуємо наступні кроки:
    1. визначаємо надлишкові та недостатні рядки (рядок є недостатнім (від'ємним), якщо запаси відповідного пункту відправлення розподілені повністю, а потреби пунктів призначення не задоволені; рядок є надлишковим (додатним), якщо потреби задоволені і при цьому залишився товар у відповідному пункті відправлення);
    2. для кожного стовпчика знаходимо різницю між тарифами у колі та найближчим до нього тарифом, який записаний в надлишковому рядку. Якщо тариф у колі знаходиться в позитивному (надлишковому) рядк, то  різницю не визначаємо; серед різниць знаходимо найменшу — проміжну ренту;
    3. переходимо до нової таблиці — додаємо до відповідних тарифів, які знаходяться у від'ємних (недостатніх) рядках, проміжну ренту. Інші елементи не змінюємо.

Читати повністю

Графічний метод. Приклад розв'язання задачі лінійного програмування графічним методом

Для виготовлення товару A і B підприємство використовує три види сировини I, II, III. Норми витрат сировини на виробництво одного товару кожного виду, ціна одиниці товару A, B а також загальна кількість сировини наведені в наступній таблиці:

510

Потрібно організувати випуск даної продукції таким чином, щоб прибуток від її реалізації був максимальним.

Позначимо через 28 — кількість товару виду А; 33 — кількість товару виду В. Тоді математична модель даної задачі полягає у визначенні максимального значення функції мети:

215

при обмеженнях:

68

46

Читати повністю

Графічний метод розв'язання задачі лінійного програмування

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

Розглянемо задачу лінійного програмування:

117при обмеженнях:

214

37

Читати повністю

Наступна сторінка »