UCBL, MIM Mastery, Оперативно изследователско линейно програмиране

1.1 Какво е линейно програмиране

1.1.1 Пример: проблемът с диетата на Поли [1, стр.3]

• Ежедневни нужди: Енергия 2000 kcal Протеин 55g Калций 800 mg
• Налична храна

  Порция	Енергия (kcal)	Протеини (g)	Калций (mg)	Цена/порция
  Зърнени храни	28g	110	4	2	3
  Пиле	100гр	205	32	12	24
  Яйца	2 големи	160	13	54	13
  Пълномаслено мляко	237 куб. См	160	8	285	9
  Пай	170гр	420	4	22.	20.
  Свинско и боб	260гр	260	14.	80	19.

Какъв избор за Поли ?

• Ограничения: Зърнени храни най-много 4 порции на ден Пиле най-много 3 порции на ден Яйца най-много 2 порции на ден Мляко най-много 8 порции на ден Пай най-много 2 порции на ден Свинско и боб най-много 2 порции на ден

Как да формализираме проблема? (моделиране)

Какво прави проблема толкова специфичен ?

Знаете ли как да решавате подобни проблеми ?

1.1.2 Стандартна форма на задача за линейно програмиране

Под ограничения: 2 * x1 + 3 * x2 + x3

4 * x1 + x2 + 2 * x3

3 * x1 + 4 * x2 + 2 * x3

Минимизиране: 3 * x1 - x2

Под ограничения: - x1 + 6 * x2 - x3 + x4> = -3

7 * x2 + 2 * x4 = 5

Под ограничения:

Изборът на променливи (x 1, ..., x n) се нарича решение на проблема.

Решението е възможно, ако се проверят ограниченията.

z се нарича целева функция. С всяко решение той асоциира стойност.

Решението е оптимално, ако е осъществимо и максимизира целевата функция.

---