Содержание

Модели линейного программирования 3

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

Общая задача линейного программирования 10

Стандартная (симметричная) задача линейного программирования 11

Каноническая (основная) задача линейного программирования 11

Представление задачи линейного программирования в канонической форме 12

Геометрическая интерпретация задачи линейного программирования 14

Решение задач линейного программирования симплекс-методом 19

Транспортная задача 24

Нахождение первоначального плана 27

Циклы пересчета 30

Определение оптимального плана транспортных задач,имеющих дополнительные условия 35

Распределительный метод решения транспортной задачи 36

Метод потенциалов 39

Модель межотраслевого баланса 40

Характеристика основных разделов и схема межотраслевого баланса 42

Основные балансовые соотношения 44

Экономико-математическая модель межотраслевого баланса. Модель Леонтьева 45

Методы отыскания вектора валовых выпусков и вектора конечной продукции 46

Смешанная задача межотраслевого баланса 47

Элементы и теория игр 50

Игра два на два (2 х 2) 57

Литература 60

Модели линейного программирования

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

Общая задача математического программирования имеет вид

Определить экстремум функции f(x)  extremum (max, min)

при выполнении условий

g_i(x) = (, )b_i, (i = ),

x = (x₁, x₂,… x_j …x_n), x_j  0, (j = ),

где f(x) – целевая функция;

g_i(x) - функция ограничения;

b_i - действительное число, константа ограничения.

Если функции f(x) и g_i(x) представлены в виде линейных функций, то оптимизационная задача называется задачей линейного программирования.

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

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

1. Задача планирования производства

Фирма выпускает четыре вида персональных компьютеров

Цех	Затраты времени на единицу продукции, ч				Общий фонд времени, ч/мес
				
Узловой сборки	15	12	4,8	3	480
Сборочный	8,4	4,8	1,8	1,2	252
Испытательный	2,4	1,2	0,12	0,06	90
Доход, ден.ед.	6,5	6	1,5	0,75	__

Определить, сколько изделий и какого вида следует изготовить фирме, чтобы доход за месяц был бы максимальным. Построить экономико-матема-тическую модель задачи.

Решение. Обозначим через Х₁ – количество изделий вида , которое

должна выпустить фирма;

Х₂ – количество изделий вида ;

Х₃ – количество изделий вида ;

Х₄ – количество изделий вида .

Найдем затраты времени на производственный процесс в цехах (они не должны превышать располагаемый фонд времени)

15x₁ + 12x₂ + 4,8x₃ + 3x₄  480,

8,4x₁ + 4,8x₂ + 1,8x₃ + 1,2x₄  252, (1)

2,4x₁ + 1,2x₂ + 0,12x₃ + 0,06x₄  90.

Доход за месяц должен быть максимизирован:

f(x) = 6,5x₁ + 6x₂ + 1,5x₃ + 0,75x₄  max . (2)

Выпускается только выгодная продукция (в этом случае Х_i > 0), а невыгодная не производится (тогда Х_i = 0). Отсюда условие неотрицательности переменных

x₁  0, x₂  0, x₃  0, x₄  0. (3)