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

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

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

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

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

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

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

Метод гілок та меж. Розв'язок задачі цілочисельного програмування методом гілок та меж

Метод гілок і меж — один з комбінаторних методів. На відміну від методу Гоморі застосовується як до повністю, так і частково цілочисельних задач. Його суть полягає в упорядкованому переборі варіантів і розгляді лише тих з них, які виявляються за певними ознаками корисними для знаходження оптимального рішення.

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

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

Метод Гоморі. Приклад розв'язку задачі цілочисельного програмування методом Гоморі

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

Таблиця даних задачі лінійного програмування

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

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

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

Знаходження найкоротшого маршруту для орієнтованого графі за алгоритмом Дейкстри в середовищі програмування Delphi(2)

Дана програма призначена для знаходження найкоротшого маршруту, за алгоритмом Дейкстри, від вершини №1 до всіх інших вершин орієнтованого графа, а також для підрахунку довжини даного маршруту.

Після запуску програми користувачу пропонується створити граф з допомогою кнопок панелі інструментів та області форми під назвою «Граф». Тобто для того, щоб намалювати вершини графа необхідно на панелі інструментів натиснути кнопку «Додати вершину» і з допомогою лівої кнопки миші розмістити її в області «Граф».

Створення вершин графа з допомогою програми Алгоритм Дейкстри

Створення вершин графа з допомогою програми Алгоритм Дейкстри

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

Знаходження найкоротшого маршруту для орієнтованого графі за алгоритмом Дейкстри в середовищі програмування Delphi(1)

Нехай потрібно визначити найкоротший маршрут в орієнтованому графі. Для цього будемо використовувати delphi-програму, яка будує необхідний маршрут, від вершини під номером один, до всіх інших вершин заданого графа і використовує для цього алгоритмом Дейкстри.

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

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

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

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

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

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

Графічний метод на Delphi

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

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