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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

 

 

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

Математическое моделирование — это процесс построения и изучения математических моделей.

Математические методы — научное направление, посвящённое исследованию систем и процессов с помощью математических моделей.

Цель: решение задачи  линейного программирования графическим методом. Рассмотрение решения транспортной задачи с помощью составление опорных планов методами: северо-западного угла, наименьшего элемент, методом Фогеля. Оптимизация плана полученного методом наименьшего элемента.

 

1 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

 

 

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

 

Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах  -мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

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

В 1939 году Леонид Витальевич Канторович опубликовал работу «Математические методы организации и планирования производства», в которой сформулировал новый класс экстремальных задач с ограничениями и разработал эффективный метод их решения, таким образом были заложены основы линейного программирования.

Основной (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы) вида:

(1) [1]

при условиях

(2) [1]

 

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

(3) [1]

Основную задачу можно свести к канонической путём введения дополнительных переменных.

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

 

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

 

Транспортная задача (задача Монжа — Канторовича) — математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение. Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача является по теории сложности вычислений NP - сложной и входит в класс сложности NP. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).

Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

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

Классическую транспортную задачу можно решить симплекс-методом, но в силу ряда особенностей её можно решить проще (для задач малой размерности).

Условия задачи располагают в таблице, вписывая в ячейки количество перевозимого груза из  в  груза, а в маленькие клетки — соответствующие тарифы.

Требуется определить опорный план и путём последовательных операций найти оптимальное решение. Опорный план можно найти следующими методами: «северо-западного угла», «наименьшего элемента» и «аппроксимации Фогеля».

 

1.3 Методы нахождения  опорного плана

 

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

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

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

Метод аппроксимации Фогеля состоит в вычислении для каждой строки транспортной таблицы разницы между двумя наименьшими тарифами. Аналогичное действие выполняют для каждого столбца этой таблицы. Наибольшая разница между двумя минимальными тарифами соответствует наиболее предпочтительной строке или столбцу (если есть несколько строк или столбцов с одинаковой разницей, то выбор между ними произволен). В пределах этой строки или столбца отыскивают ячейку с минимальным тарифом, куда пишут отгрузку. Строки поставщиков или столбцы потребителей, которые полностью исчерпали свои возможности по отгрузке или потребности которых в товаре были удовлетворены, вычеркиваются из таблицы, и вычисление повторяются до полного удовлетворения спроса и исчерпания отгрузок без учета вычеркнутых ячеек.

 

 

 

 

 

 

 

 

2. ПРАКТИЧЕСКАЯ ЧАСТЬ

 

 

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

 

Задача 1

Предприятие должно выпускать два вида трансформаторов – А и В, используя при этом последовательно три станка. Данные о технологическом процессе указаны в следующей таблице

 

Таблица 1 - Исходные данные

Станок	Трудоемкость на 1 ед. продукции		Фонд времени, час
	А	В
1	0,1	0,6	42
2	0,3	0,2	30
3	0,3	0,1	27

 

Прибыль от продажи единицы продукции вида А и В составляет 30 руб. Составьте план выпуска трансформаторов, обеспечивающий предприятию наибольшую прибыль.

 

Решение

Введем переменные:

 х1 – оббьем выпуска трансформаторов вида А,

 х2 – оббьем выпуска трансформаторов вида B.

Тогда математическая модель имеет вид:

 

+ ≤ 18   (1)

+   ≤ 20  (2)

  ≤ 16  (3)

х1 ≥ 0,  х2 ≥ 0

 

Z(x) = 30×( х1+ х2)→max

Строим область допустимых решений задачи.

Нумеруем ограничения задачи. В прямоугольной декартовой системе координат строим прямую + =18 (L1),соответствующую ограничению (1).

1. 2х1 +3х2=108 (L1)

х1 = 0,  3х2=108 и х2=0,  2х1=108

х2=36 х1=54

  (0;36) (54;0)

Находим, какая из двух полуплоскостей, на которые эта прямая делит координатную плоскость, является областью решений неравенства (1).

Для этого достаточно координаты какой-либо точки, не лежащей на прямой L1, подставить в неравенство. Т.к. прямая L1 не проходит через начало координат, подставляем координаты  т.0(0;0) в первое ограничение 0+0 ≤ 18. Получаем строгое неравенство 0 < 18. Следовательно т. 0 лежит в полуплоскости решений. Таким образом, стрелки на концах прямой L1 должны быть направлены в полуплоскость, содержащую т.0. Аналогично строим прямые

 L2 (+ 20)  и  L3 (   и области решений (2) и (3).

3.  

2х1 + х2= 80 х2 = 64

х1=0,

х2=80,

(0;80)

х1=40,

х2=0

(40;0)

Находим общую часть полуплоскостей, учитывая при этом условия неотрицательности.

Построим прямую уровня. Возьмем произвольную точку, принадлежащую области допустимых решений, М(10;40) и подставим в целевую функцию

30×(10+40)=30×50=1500

30×(х1+х2)=1500

х1+х2=50

х1=0, х2=50 (0;50)   и  х1=50, х2=0 (50;0)

По координатам 2 точек, строим прямую уровня. Найдем координаты точек Х1 и Х2. Для этого решим системны уравнений:

2х1+3х2=108 и 2) 2х1+ х2=80

2х1+х2=80

х2=64

2х2=28

2х2=16, Х1=8

х2=14

х2(8;64)

х1=33

х1(33;14)

Вычисляем Z(х1)=30×(33+14)=1410

Z(х2)=30×(8+64)=2160

Значит трансформаторов вида А надо выпускать 8, а вида В – 64.

 

Рисунок 1 – Область допустимых решений

 

2.2 Решение транспортной  задачи

 

Задача 2

Составьте опорные планы методами:

1. северо-западного угла;

2. наименьших затрат;

3. аппроксимации Фогеля.

Методом потенциалов оптимизируйте план, полученный методом наименьших затрат.

 

 

 

Таблица 2 - Исходные данные

База	Магазин					Запас продукции
	В1	В2	В3	В4	В5
А1	13	14	15	5	9	220
А2	7	19	17	10	12	280
А3	9	12	10	13	7	500
Спрос на продукцию	230	170	260	190	150