Задача придбання устаткування

Постановка задачі.

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

Задано вектор ресурсів (гроші, загальна площа, чисельність працівників і т.п).

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

Уведемо змінні - кількість одиниць відповідного виду устаткування. Складемо модель.

Обмеження:

Умова невід’ємності:

Додаткова умова:

- цілі

Це лінійна задача цілочисельного програмування, розв’язується за допомогою методу Гоморі.

Приклад.

Виділено 20 тисяч гривень на придбання устаткування для нової ділянки, м². Розглядається два види устаткування. Машина типу коштує 5 тис. грн., займає 8м² і має продуктивність 7 тис.од. продукції за зміну. Машина типу коштує 2 тис. грн., займає 4м², і забезпечує виробництво 3 тис. од. продукції за зміну. Розрахувати оптимальний план придбання устаткування, що забезпечить за даних обмежень максимальну продуктивність ділянки.

Уведемо змінні і – плановану кількість машин. Складемо цільову функцію.

Обмеження:

, цілі

Розв’язання:

 

Складемо початковий план

 

Базис	Сб.		A1	A2	A3	A4
x3 x4
Fj - Cj		-7	-3
x1 x2		7,5			-2	-0,5 1,5
Fj - Cj	29,5				0,5

 

План оптимальний: , але – неціле.

Метод Гоморі: .

Обмеження: .

Новий план майже припустимий, застосовується двоїстий симплекс-метод. Одержуємо рішення:

 

– план оптимальний.

=29 .

Рекомендується придбання 2 машин типу і 5 машин типу , загальна продуктивність ділянки 29 тис. од. за зміну. Гроші використовуються повністю, невикористаними залишилося м² площі приміщення.

 

 

Контрольні запитання

1. Якою є постановка задачі цілочисельного програмування?

2. Яким є алгоритм методу Гоморі для ЗЦП?

3. Які недоліки методу Гоморі?

Лекція 5

Транспортна задача

Побудова опорного плану

 

1. Економічна постановка транспортної задачі (ТЗ)
2. Математична модель ТЗ
3. Побудова початкового опорного плану для закритої моделі ТЗ: метод північно-західного кута
4. Методи мінімальної вартості і подвійної переваги

 

1. Маємо деякий продукт (товар), що знаходиться в декількох постачальників (виробників), відомі обсяги цього продукту. Маються замовники (споживачі) товару з відомими обсягами потреб.

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

 

2. Уведемо наступні позначення:

- постачальники, - обсяг (кількість) товару в кожного з них; .

- споживачі, - обсяг потреб кожного з них; .

- матриця цін (питомих витрат), де - ціна перевезення товару за маршрутом від до .

Позначимо через - кількість продукту (обсяг перевезень) за маршрутом від до .

Тоді загальні витрати за всіма маршрутами

Одержали наступну лінійну модель

цільова функція (5.1)

 

i = 1, 2,...m (5.2)

j = 1, 2,...n (5.3)

(5.4)

 

 

Економічний зміст обмежень:

(5.2) – весь товар постачальників вивезений

(5.3) – усі потреби споживачів задоволені

(5.4) – товар за кожним маршрутом або планується до перевезення (х_ij >0) або не планується (х_ij = 0).

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

Для викладення методів додамо умову:

(5.5)

Зміст умови (5.5); загальний обсяг запасів товару дорівнює загальному обсягу потреб.

Модель (5.1)-(5.4) з додатковою умовою (5.5) називається закритою, без неї – відкритою.

Теорема. Будь-яка закрита модель транспортної задачі має розв’язок.

 

3. Побудова початкового опорного плану для закритої моделі

Будемо заповнювати таблицю з m рядками і n стовпчиками. Клітину таблиці назвемо зайнятою, якщо в неї поміщене перевезення x_ij>0. Інші клітини називаються вільними, x_ij = 0 у них не ставляться.

У системі рівнянь (5.2), (5.3) і (5.5) усього m+n-1 незалежних рівнянь, тому опорний план задачі повинен містити не більш m+n-1 зайнятих клітин. Якщо N = m+n-1 - план називається не виродженим, якщо N<m+n-1 – виродженим.

Циклом у заповненій таблиці називається замкнута ламана лінія з вершинами в зайнятих клітинах.

Приклади циклів:

Опорний план не повинен містити циклів.

 

4. Розглянемо кілька методів побудови опорного плану транспортної задачі.