На головну

лінійне програмування

  1.  V1: Лінійне програмування
  2.  Алгоритмізація і програмування
  3.  В.3.04. ПАРАЛЕЛЬНЕ програмування
  4.  візуальне програмування
  5.  Вплив перша: вербальне програмування
  6.  Питання Об'єктно-орієнтоване програмування.
  7.  Питання Етапи розвитку мов програмування

1. Завдання лінійного програмування і їх властивості

У багатьох областях практики виникають своєрідні завдання дослідження операцій зазначеними особливостями:

· Показник ефективності W є лінійна функція від елементарного рішення ;

· Обмежувальне умова, яку належить мати елементарні рішення мають вигляд лінійних рівностей або нерівностей. Такі завдання є завданнями лінійного програмування.

Запишемо формулювання основних завдань лінійного програмування.

Завдання про харчовому раціоні:

Сільгосп підприємства виробляє відгодівлю худоби з комерційною метою. Бути 4 види продуктів харчування  . Вартість од. продукту відповідно дорівнює  . Потрібно скласти харчовий раціон, який повинен містити:

· Білків, не менше  одиниць;

· Вуглеводів, не менше  одиниць;

· Жирів, не менше  одиниць.

для продуктів  вміст жирів, білків, вуглеводів наведені в таблиці:

 продукти  елементи
 білки  вуглеводи  жири

Харчовий раціон складається таким чином що б його вартість була мінімальною.

Рішення:

1. Скласти математичну модель:

нехай  - Кількість продуктів  , Що входять в раціон. Тоді вартість раціонального харчування (показник ефективності) дорівнює:

Запишемо обмеження по білків, вуглеводів і жирів

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

Завдання про завантаження обладнання

Кожна ткацька фабрика має в наявності 2 види верстатів; серед них  - Верстатів типу І,  - Верстатів II типу. Верстати виробляють 3 типи тканин  , Але з різною продуктивністю. Верстат типу І виробляє в місяць  метрів тканини ,  метрів тканини ,  метрів тканини  . Можна скласти таблицю для и

 верстат  Тип тканини
 прибуток

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

рішення:

Математична модель такого завдання:

нехай  - Число верстатів типу  зайнятих виробництвом тканини  . Таким чином отримуємо 6 змінних  (Необхідно вибрати таким чином, що б прибуток була максимальної)

Верстати не повинні простоювати, тому

Крім того, повинні бути виконано завдання по асортименту з урахуванням продуктивності верстатів

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

Завдання про перевезення

Є 4 пункту відправлення:  в яких зосереджені запаси певного виду вантажу в кількостях  Крім того, є 3 пункту призначення  Пункти подали заявки на  одиниць вантажу. Сума заявок дорівнює сумі наявних запасів,  . Відома вартість перевезення вантажу з пункту А в пункт В. Вартість кожного перевезення буде нараховуватися: ;

Потрібно скласти такий план перевезень (яка кількість вантажу звідки і куди відправити) при якому сумарні перевезення звертаються в мінімум.

Математична модель задачі:

нехай  - Кількість одиниць вантажу, що відправляється з  пункту в  пункт призначення.

 Запишемо обмеження налягаемие на елементи рішення. Обмеження записуємо з урахуванням того, що всі заявки повинні бути виконані.

Так, як всі запаси повинні бути вичерпані, то:

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

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

Формула записи завдання ЛП, яка обмежена тільки равенствами називається стандартною формою, а сама задача називається задачею ЛП (ОЗЛП).

 




 Двоїстість і аналіз чутливості |  нелінійне програмування |  Метод множників Лагранжа |  Елементи теорії графів |  метод графів |

© um.co.ua - учбові матеріали та реферати