Информатика
Математика
Чертежи
Физика
Инженерка
Интегралы
Термех
Решение задач

Черчение

Матанализ
Сопромат
ТОЭ
Энергетика
Курсовая
Искусство
Электроника

Математика решение матриц

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

Постановка задачи. Графический метод

Рассмотрим сначала несколько задач, которые привели к развитию целой отрасли математики – линейного программирования. Разумеется, в реальных задачах количество неизвестных и ограничений гораздо больше, но для понимания сути задачи и методов ее решения нам будет достаточно рассмотреть модельные ситуации с небольшим количеством неизвестных.

Пример 1 (транспортная задача)

На две товарные станции привезли по 30 комплектов мебели. Мебель необходимо развести по трем магазинам (по 20 комплектов в каждый). Известна стоимость перевозок с каждой станции в каждый магазин:

 

Магазин 1

Магазин 2

Магазин 3

Станция 1

7

5

8

Станция 2

3

9

6

Требуется составить оптимальный (с наименьшими затратами) план перевозок.

Математическая постановка задачи:

Пусть х1, х2,...,х6- количество комплектов, которые надо перевезти со станций в магазины. Учитывая ограничения, получим для xi³0 систему:

Получили систему из четырех уравнений с шестью неизвестными, у которой бесконечно много решений. Среди них надо выбрать такое, на котором целевая функция: f=7х1 + 3х2 + 5х3 + 9х4 + 8х5 + 6х6 достигает минимума.

Пример 2 (расчет рациона)

Имеются две питательные смеси, про которые известно, сколько белков, жиров и углеводов содержит одна единица каждой из них:

 

Жиры

Белки

Углеводы

Цена

1-я смесь

22

15

7

7

2-я смесь

16

11

9

6

Каждая корова должна получать не меньше 200 единиц жиров, 130 единиц белков и 75 единиц углеводов. Требуется подешевле накормить коров с учетом этих данных.

Математическая постановка задачи:

Пусть надо дать корове 1-ой смеси х1 единиц, 2-ой смеси- х2 единиц. Тогда

Среди решений данной системы надо выбрать такое, на котором достигается минимум целевой функции f=7x1+6x2.

Пример 3 (распределение ресурсов) Предприятие производит два вида продукции из двух видов сырья, причем известны запасы обоих видов сырья, расход сырья на каждый вид продукции и доход с одной единицы каждой продукции:

Двойственная задача В матричном виде задача, двойственная к задаче линейного программирования в общем виде, имеет вид: АtY ³ C, Y ³ 0, V=(b,y) -> max.

Сиплекс-метод Будем исследовать задачу линейного программирования в канонической форме:АХ = В, Х³ 0, f = (с, х) -> min.

Описание симплекс-метода. Выразим целевую функцию через свободные переменные и допишем к задаче:f = a0 -ar+1хr+1 - ... -anхn.

Алгоритм симплекс-метода: 1. Заполняем исходную таблицу (считается, что исходный базис найден).


Электротехника

Расчеты
Прочность
На главную
Лабы
Задачи
Реакторы