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

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

Таблиця 1.

Робітники	Продуктивність праці, грн./год, на обладнанні

Початковий розподіл можна виконувати довільним способом. Оптимальний розподіл призначень має вигляд

.

6. Розподільчи задачі загального типу.

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

Типовим прикладом такої задачі є організація випуску різнорідної продукції на устаткуванні різних типів.

Початкові параметри моделі розподільчої задачі:

· n – кількість виконавців;

· m – кількість видів виконуваних робіт;

· a_i – запас робочого ресурсу виконавця /од. ресурсу/;

· b_j – план по виконанню роботи /од. робіт/;

· c_ij – вартість виконання B_j роботи A_i виконавцем /грн./од. робіт/;

· λ_ij – інтенсивність виконання B_j роботи A_i виконавцем /од.робіт/од.ресурсу/.

Шукані параметри моделі розподільчої задачі:

· x_ij – планове завантаження виконавця A_i при виконанні B_j робіт /до.ресурсу/;

· - кількість робіт, які повинен буде провести виконавець A_i /од.робіт/;

· L(X) – загальні витрати на виконання всього запланованого об’єму робіт /грн../.

ЕТАПИ ПОБУДОВИ МОДЕЛІ

I.Визначення змінних.

II. Побудова розподільчої матриці (таблиця1).

III.Задання цільової функції.

IV. Задання обмежень.

Таблиця 1.

Виконавці	Роботи	Запас ресурсу од. ресурсу
B1	B2	…	Bm
A1	λ11		λ12		…		λ1m		a1
	c11		c12		…		c1m
A2	λ21		λ22		…		λ2m		a2
	c21		c22		…		c2m
…	…	…	…	…	…
An	λn1		λn2				λnm		an
	cn1		cn2				cnm
План, од. роботи	b1	b2	…	bm

Модель розподільчої задачі

(7)

де - це кількість робіт j – го виду, i – м виконавцем.

Етапи розв’язання розподільчої задачі

І. Перетворення розподільчої задачі в транпортну задачу:

1. вибір базового ресурсу і розрахунок нормованих продуктивностей ресурсів α_i:

2. перерахунок запасу робочого ресурсу виконавців :

[од. ресурсу];

3. перерахунок планового завдання :

4. перерахунок собівартості робіт:

ІІ. Перевірка балансу перерахованих параметрів і побудова транспортної матриці.

ІІІ. Пошук оптимального розв’язку транспортної задачі .

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

[од. ресурсу],

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

V. Визначення кількості робіт, відповідно оптимальному розв’язку розподільчої задачі Х^*:

VI. Визначення цільової функції розподільчої задачі Z згідно з (7).

7. Приклад вирішення задачі типу ТЗ.

На фабриці працюють три типи ткацьких верстатів, які можуть випускати чотири види тканин. Відомі наступні дані про виробничій процес:

· продуктивність верстатів по кожному виду тканин, м/год

· собівартість тканини, грн./м

· ресурси робочого часу верстатів (a_i): 90, 220, 180 год;

· запланований об’єм випуску тканин (b_j): 1200, 900, 1800, 840 м.

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

Питання для самоконтролю.

· Чому транспортну задачу вирішують іншими методами, якщо це задача лінійного програмування?

· Яка транспортна задача називається закритою?

· Що робити якщо транспортна задача відкрита?

· Дайте означення опорного плану транспортної задачі.

· Коли опорний план транспортної задачі не вироджений?

· Що робити, якщо опорний план транспортної задачі вироджений?

· Дайте означення оптимального опорного плану транспортної задачі.

· Сформулюйте необхідні і достатні умови існування розв’язку транспортної задачі.

· Як построїти потенціали строк і стовпців?

· В чому полягає метод північно-західного кута?

· В чому полягає метод найменших витрат?

· Як визначити, що опорний план оптимальний?

· Дайте означення циклу перерозподілу поставок.

Тема 4. Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач.

Лекція 10.

Тема лекції: Двоїста задача лінійного програмування

Мета: ознайомити студентів з методами розв’язання двоїстих задач лінійного програмування, показати взаємозв’язок прямої та двоїстої задач.

План лекції

1. Математичні моделі двоїстих задач.

2. Основні теореми теорії двоістості.

3. Взаємозв’язок розв’язків прямої та двоїстої задач.

Література:

1. Лавріненко Н.М., Латинін С.М., Фортуна В.В., Безкровний О.І. Основи економіко-метематичного моделювання: Навч. Посіб. - Львів: «Магнолія 2006», 2010.- 540с.

2. Іванюта І. Д. Практикум з математичного програмування: Навчальний посібник / І. Д. Іванюта, В. І. Рибалка, І. А. Рудоміно-Дусятська. – К.: «Слово», 2008. - 296 с.

3. Кучма М. І. Математичне програмування: приклади і задачі: Навчальний посібник / М.І. Кучма. – Львів: «Новий Світ - 2000», 2006. - 344 с.

4. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1993. – 336 с.

1 Математичні моделі двоїстих задач.

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

Початкова задача називається прямою задачею ЛП. Ці дві задачі тісно пов’язані між собою і утворюють єдину пару двоїстих задач.

Якщо пряма задача ЛП має вигляд:

Z=∑c_ix_i →max (1)

за умов

∑a_ijx_j ≤b_i, (i=1,2…..m) (2)

x_j ≥0 (j=1,2…..n) (3)

то двоїста задача записується так:

F=∑b_iy_i →min (1*)

за умов

∑a_ijy_i≥ c_j, (j=1,2…..n) (2*)

y_i≥0 (i=1,2…..m) (3*)

В матричному вигляді їх можна представити таким чином: