Линейное программирование

1. Тема: Линейное программирование

• Математической моделью задачи называется совокупность
математических соотношений, описывающих суть задачи.
• Составление математической модели включает:
• выбор переменных задачи
• составление системы ограничений
• выбор целевой функции
• Переменными задачи называются величины Х1, Х2, Хn,
которые полностью характеризуют экономический процесс.
Обычно их записывают в виде вектора: X=(X1, X2,...,Xn).
• Системой ограничений задачи называют совокупность
уравнений и неравенств, описывающих ограниченность
ресурсов в рассматриваемой задаче.
• Целевой функцией задачи называют функцию переменных
задачи, которая характеризует качество выполнения задачи и
экстремум которой требуется найти.

2.

3. Тема Линейное программирование

• В общем случае задача линейного
программирования может быть записана в
таком виде:
• Данная запись означает следующее: найти
экстремум целевой функции (1) и
соответствующие ему переменные X=(X1,
X2,...,Xn) при условии, что эти переменные
удовлетворяют системе ограничений (2) и
условиям неотрицательности (3).

4. Тема Линейное программирование

5. Тема Линейное программирование

• Данная запись означает следующее: найти экстремум целевой
функции (1) и соответствующие ему переменные X=(X1,
X2,...,Xn) при условии, что эти переменные удовлетворяют
системе ограничений (2) и условиям неотрицательности (3).
• Допустимым решением (планом) задачи линейного
программирования называется любой n-мерный вектор X=(X1,
X2,...,Xn), удовлетворяющий системе ограничений и условиям
неотрицательности.
• Множество допустимых решений (планов) задачи
образует область допустимых решений(ОДР).
• Оптимальным решением (планом) задачи линейного
программирования называется такое допустимое решение
(план) задачи, при котором целевая функция достигает
экстремума.

6. Тема Линейное программирование

• Каноническая форма задачи линейного
программирования
• В общем случае задача линейного
программирования записывается так, что
ограничениями являются как уравнения, так и
неравенства, а переменные могут быть как
неотрицательными, так и произвольно
изменяющимися.
• В том случае, когда все ограничения являются
уравнениями и все переменные удовлетворяют
условию неотрицательности, задачу линейного
программирования называют канонической.
• Она может быть представлена в координатной,
векторной и матричной записи.
• Каноническая задача линейного программирования в
координатной записи имеет вид:

7. Тема2 Линейное программирование

8. Тема 2 Линейное программирование

• Каноническая задача линейного
программирования в матричной записи
имеет вид:

9. Тема Линейное программирование

• Здесь:
• А — матрица коэффициентов системы
уравнений
• Х — матрица-столбец переменных
задачи
• Ао — матрица-столбец правых частей
системы ограничений

10. Тема Линейное программирование

• Нередко используются задачи
линейного программирования,
называемые симметричными, которые в
матричной записи имеют вид:

11. Пример ЗЛП

• Пример составления математической модели
• Задача использования ресурсов (сырья)
• Условие: Для изготовления n видов продукции используется m
видов ресурсов. Составить математическую модель.
• Известны:
• bi ( i = 1,2,3,...,m) — запасы каждого i-го вида ресурса;
• aij ( i = 1,2,3,...,m; j=1,2,3,...,n) — затраты каждого i-го вида
ресурса на производство единицы объема j-го вида продукции;
• cj ( j = 1,2,3,...,n) — прибыль от реализации единицы объема j-го
вида продукции.
• Требуется составить план производства продукции, который
обеспечивает максимум прибыли при заданных ограничениях
на ресурсы (сырье).

12. Пример ЗЛП

• Решение:
• Введем вектор переменных X=(X1, X2,...,Xn), где xj ( j
= 1,2,...,n) — объем производства j-го вида
продукции.
• Затраты i-го вида ресурса на изготовление данного
объема xj продукции равны aijxj, поэтому
ограничение на использование ресурсов на
производство всех видов продукции имеет вид:
Прибыль от реализации j-го вида продукции равна
cjxj , поэтому целевая функция равна: Ответ —
Математическая модель имеет вид:

13. Пример ЗЛП

14. Задача линейного программирования

15. Пример задачи линейного программирования

• Предприятие производит 3 вида деталей. Имеется 2
группы станков-токарные и сверлильные. Нормы
времени работы станков на производственный цикл
35 и 20 час.
• Прибыль от реализации единицы проукции
составляет 7,6,18 руб.Затраты времени токарных
станков на единицу каждой продукции равны 1,2,5
часов соответственно. Затраты времени
сверлильных станков на единицу каждой продукции
равны 2,1,2 час. Составить оптимальны план
производства деталей.

16. Пример задачи линейного программирования

• Х1 + Х2 + 5Х3 ≤ 35
• 2Х1 + Х2 + 2Х3 ≤ 20
• Х1 ≥0 Х2≥0 Х3≥0
• C = 7Х1 + 6Х2 + 18Х3 ® max