Модель линейного программирования в торговле. Теоретические аспекты линейного программирования. Математическое описание модели линейного программирования

Математическое программирование ("планирование") – это раздел математики, занимающийся разработкой методов отыскания экстремальных значений функции, на аргументы которой наложены ограничения. Идея линейного программирования возникла в 1939г., когда была напечатана брошюра Леонида Витальевича Канторовича "Математические методы организации и планирования производства". Американский математик А. Данциг в 1947 году разработал весьма эффективный конкретный метод численного решения задач линейного программирования (он получил название симплекс метода ).

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

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

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

Идея линейного программирования представлена в формате презентаций, электронная версия которых размещена в файле «Идея - линейное программирование».

Геометрическая интерпретация и графический метод решения

Графически способ решения задач линейного программирования целесообразно использовать:

1. Для решения задач с двумя переменными, когда ограничения выражены неравенствами.

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

Геометрический метод решения задач линейного программирования представлен в формате презентации - файл «Геометрический метод ЛП»

2.2. Симплекс-метод, общая характеристика, критерий оптимальности допустимого базисного плана

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

Переход от геометрического способа решения задачи линейного программирования к симплекс-методу лежит через алгебраическое описание крайних точек пространства решений. Для реализации этого перехода сначала надо привести задачу линейного программирования к стандартной (канонической) форме:

· преобразовать неравенства ограничений в равенства путем введения дополнительных переменных;

· преобразовать свободные переменные в неотрицательные;

· преобразовать задачу максимизации в задачу минимизации.

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

Восстановить знания по решению задач симплекс-методом можно с помощью презентации «Симплекс метод».

Двойственные задачи

Любая задача линейного программирования имеет двойственную природу. Правило построения двойственной задачи:

Если исходная задача на max, то двойственная на min и наоборот.

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

Коэффициентами целевой функции двойственной задачи являются правые части ограничений исходной задачи.

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

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

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

Теорема 1: Если исходная задача имеет оптимальный план x*, то двойственная задача также имеет оптимальный план y*, причем значения функций на этих планах равны: f(x*)=g(y*).

Теорема 2: Если исходная и двойственная задачи имеют планы, то они имеют и оптимальные планы, причем f(x*)=g(y*).

Признаки оптимальности для двойственных задач:

Признак 1: Если исходная и двойственная задачи имеют планы X и Y, причем f(X)=g(Y), то эти планы оптимальные.

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

Признак 2: Для того, чтобы планы X и Y исходной и двойственной задач были оптимальны, необходимо и достаточно чтобы на этих планах хотя бы одно из каждой пары сопряженных ограничений являлось равенством.

Второй признак позволяет, зная оптимальный план одной из задач, найти оптимальный план другой задачи.

Основные положения двойственной задачи изложены в презентациях «Теория двойственности» и «Двойственная задача».

Транспортные задачи

Транспортная задача является одной из наиболее распространенных специальных задач линейного программирования. Первая строгая постановка транспортной задачи принадлежит Ф. Хичкоку, а первый точный метод решения разработан Л. В. Канторовичем и М. К. Гавуриным.

Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

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

Наиболее часто встречаются следующие задачи, относящиеся к транспортным:

· прикрепление потребителей ресурса к производителям;

· привязка пунктов отправления к пунктам назначения;

· взаимная привязка грузопотоков прямого и обратного направлений;

· отдельные задачи оптимальной загрузки промышленного оборудования;

· оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями и др.

Постановки задач транспортного типа, алгоритмы их решения и примеры практического использования представлены в трех презентациях:

1. «Обобщенная транспортная задача (λ-задача)».

2. «Закрытая транспортная задача. Метод потенциалов».

3. «Усложнённые постановки транспортной задачи».

Экономические приложения

Многообразие экономических приложений математического моделирования методами линейного программирования рассмотрим на примерах формулирования конкретных постановок прикладных задач (заимствовано из курса лекций Диязитдиновой А.П.).

Задача 1

Для сохранения нормальной жизнедеятельности человек должен в сутки потреблять белков не менее 120 условных единиц (усл. ед.), жиров – не менее 70 и витаминов – не менее 10 усл. ед. Содержание их в каждой единице продуктов П 1 и П 2 равно соответственно (0,2; 0,075; 0) и (0,1; 0,1; 0,1) усл. ед.

Стоимость 1 ед. продукта П 1 – 2 руб., П 2 –3 руб.

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

Задача 2

Из пункта А в пункт В ежедневно отправляются пассажирские и скорые поезда. Данные об организации перевозок следующие:

Сколько должно быть сформировано скорых и пассажирских поездов, чтобы перевезти наибольшее количество пассажиров?

Задача 3

Четыре овощехранилища каждый день обеспечивают картофелем три магазина. Магазины подали заявки соответственно на 17, 12 и 32 тонны. Овощехранилища имеют соответственно 20, 20 ,15 и 25 тонн. Тарифы (в д.е. за 1 тонну) указаны в следующей таблице:

Задача 4

Имеются два склада готовой продукции: А 1 и А 2 с запасами однородного груза 200 и 300 тонн. Этот груз необходимо доставить трем потребителям В 1 , В 2 и В 3 в количестве 100, 150 и 250 тонн соответственно. Стоимость перевозки 1 тонны груза из склада А 1 потребителям В 1 , В 2 и В 3 равна 5, 3 ,6 д.е., а из склада А 2 тем же потребителям – 3, 4, 2 д.е. соответственно.

Составьте план перевозок, минимизирующий суммарные транспортные расходы.

Задача 5

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

Стоимость 1 кг корма первого вида – 4 д.е., второго – 6 д.е.

Составьте дневной рацион питательности, имеющий минимальную стоимость.

Задача 6

Хозяйство располагает следующими ресурсами: площадь – 100 ед., труд – 120 ед., тяга – 80 ед. Хозяйство производит четыре вида продукции: П 1 , П 2 , П 3 и П 4 . Организация производства характеризуется следующей таблицей:

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

Задача 7.

Цех выпускает трансформаторы двух видов. Для изготовления трансформаторов обоих видов используются железо и проволока. Общий запас железа – 3 тонны, проволоки – 18 тонн. На один трансформатор первого вида расходуются 5 кг железа и 3 кг проволоки, а на один трансформатор второго вида расходуются 3 кг железа и 2 кг проволоки. За каждый реализованный трансформатор первого вида завод получает прибыль 3 д.е., второго – 4 д.е.

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

Задача 8

Совхоз отвел три земельный массива размером 5000, 8000 и 9000 га на посевы ржи, пшеницы, кукурузы. Средняя урожайность в центнерах на 1 га по массивам указана в следующей таблице:

Посевы	Массивы
I	II	III
рожь
пшеница
кукуруза

За 1 центнер ржи совхоз получает 2 д.е., за 1 центнер пшеницы – 2,8 д.е., за 1 центнер кукурузы – 1,4 д.е. Сколько гектаров и на каких массивах совхоз должен отвести на каждую культуру, чтобы получить максимальную выручку, если по плану он обязан сдать не менее 1900 тонны ржи, 158 000 тонны пшеницы и 30 000 тонн кукурузы?

Задача 9

Из трех продуктов – I, II, III составляется смесь. В состав смеси должно входить не менее 6 ед. химического вещества А, 8 ед. – вещества В и не менее 12 ед. вещества С. Структура химических веществ приведена в следующей таблице:

Продукт	Содержание химического вещества в 1 ед. продукции	Стоимость 1 ед. продукции
А	В	С
I
II
III		1,5		2,5

Составьте наиболее дешевую смесь.

Задача 10

В школе проводится конкурс на лучшую стенгазету. Одному школьнику дано следующее поручение:

купить акварельной краски по цене 30 д.е. за коробку, цветные карандаши по цене 20 д.е. за коробку, линейки по цене 12 д.е., блокноты по цене 10 д.е.;

красок нужно купить не менее трех коробок, блокнотов – столько, сколько коробок карандашей и красок вместе, линеек не более пяти. На покупки выделяется не менее 300 д.е.

В каком количестве школьник должен купить указанные предметы, чтобы общее число предметов было наименьшим?

Задача 11

Имеются три специализированные мастерские по ремонту двигателей. Их производственные мощности равны соответственно 100, 700, 980 ремонтов в год. В пяти районах, обслуживаемых этими мастерскими, потребность в ремонте равна соответственно 90, 180, 150, 120, 80 двигателей в год. Затраты на перевозу одного двигателя из районов к мастерским следующие:

Районы	Мастерские
	4,5	3,7	8,3
	2,1	4,3	2,4
	7,5	7,1	4,2
	5,3	1,2	6,2
	4,1	6,7	3,1

Спланируйте количество ремонтов каждой мастерской для каждого из районов, минимизирующее суммарные транспортные расходы.

Задача 12

Нефтеперерабатывающий завод получает четыре полуфабриката: 400 тыс. л алкилата, 250 тыс. л крекинг-бензина, 350 тыс. л бензина прямой перегонки и 100 тыс. л изопентона. В результате смешивания этих четырех компонентов в разных пропорциях образуются три сорта авиационного бензина: бензин А-2:3:5:2, бензин В-3:1:2:1, бензин С-2:2:1:3. Стоимость 1 тыс. л указанных сортов бензина характеризуется числами 120 д.е., 100 д.е., 150 д.е.

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

Задача 13

Для участия в соревнованиях спортклуб должен выставить команду, состоящую из спортсменов I и II разрядов. Соревнования проводятся по Буге, пряжкам в высоту, прыжкам в длину. В беге должны участвовать 5 спортсменов, в прыжках в длину – 8 спортсменов, а в прыжках в высоту – не более 10. количество очков, гарантируемых спортсмену каждого разряда по каждому виду, указано в таблице:

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

Задача 14

Звероферма выращивает черно-бурых лисиц и песцов. На звероферме имеется 10 000 клеток. В одной клетке могут быть либо 2 лисицы, либо 1 песец. По плану на ферме должно быть не менее 3000 лис и 6000 песцов. В одни сутки необходимо выдавать каждой лисе корма – 4 ед., а каждому песцу – 5 ед. Ферма ежедневно может иметь не более 200 000 единиц корма. От реализации одной шкурки лисы ферма получает прибыль 10 д.е., а от реализации одной шкурки песца – 5 д.е.

Какое количество лисиц и песцов нужно держать не ферме, чтобы получить наибольшую прибыль?

Задача 15

Имеются два элеватора, в которых сосредоточено соответственно 4200 и 1200 тонн зерна. Зерна необходимо перевезти трем хлебозаводам в количестве 1000, 2000 и 1600 тонн каждому. Расстояние от элеватора до хлебозавода указано в следующей таблице:

Затраты на перевозку 1 тонны продукта на 1 км составляют 25 д.е. Спланируйте перевозки зерна из условия минимизации транспортных расходов.

Задача 16

Из двух сортов бензина образуются две смеси – А и В. Смесь А содержит Бензина 60% 1-го сорта и 40% 2-го сорта; смесь В – 80% 1-го сорта и 20% 2-го сорта. Цена 1 кг смеси А – 10 д.е., а смеси В – 12 д.е.

Составьте план образования смесей, при котором будет получен максимальный доход, если в наличии имеется бензин 50 т 1-госорта и 30 т второго сорта.

Задача 17

Имеются две почвенно-климатические зоны, площади которых соответственно равны 0,8 и 0,6 млн. га. Данные об урожайности зерновых культур приведены в таблице:

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

Задача 18

На заводе выпускают изделия четырех типов. От реализации 1 ед. каждого изделия завод получает прибыль соответственно 2, 1, 3, 5 д.е. На изготовление изделий расходуются ресурсы трех видов: энергия, материалы, труд.

Данные о технологическом процессе приведены в следующей таблице:

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

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

Пример 3.10
Рассмотрим химическую фирму, производящую полиуретан. Производитель имеет заказы на поставку полиуретана в количестве d i тонн в месяц на ближайшие четыре месяца (i=1,2,…,4). Пусть затраты на производство одной тонны полиуретана составляют C i тыс. рублей, а максимальный объем производства полиуретана по месяцам ограничен и равен K i тонн в месяц. Производственная фирма имеет возможность хранить продукцию на складе, причем стоимость хранения одной тонны продукции за месяц составляет n i тыс. рублей. На начальный период времени запас полиуретана на складе составлял L 0 тонн. Менеджеру компании требуется составить план производства полиуретана по месяцам, который бы обеспечил выполнение заказов при минимальной стоимости производства и хранения продукта.
Решение
Заметим, что если бы не было возможности хранить продукцию на складе, то задача разбилась бы на четыре независимые статические задачи и потеряла бы для нас всякий смысл.
Составим уравнение материального баланса, позволяющего вычислить количество продукции, хранящееся на складе в течение i-го месяца. Пусть x i – количество полиуретана, произведенного в i-й временной период. Тогда в течение первого месяца товарный запас на складе будет равен L 1 =L 0 +x 1 -d 1 . Товарный запас второго месяца

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

. (3.24)
После того как мы вывели уравнение (3.24), описывающее поведение товарных запасов, легко записать математическую модель задачи:

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

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

Табличная модель задачи управления запасами
Табличная модель задачи после нахождения оптимального решения приведена на рис. 21.

Рис. 21. Табличная модель задачи динамического программирования

Следует сказать несколько слов и об отчете по устойчивости для этой модели, приведенном на рис. 22.

Рис. 22. Отчет по устойчивости для динамической модели

Если используется простое ограничение на значение оптимизируемых переменных (x i ≤K i в нашем случае), то в отчете по устойчивости теневые цены для этих ограничений помещаются в столбце нормированная стоимость, а информация о допустимом диапазоне теневых цен для этих ограничений не выводится. Таким образом, если увеличить на одну тонну производственные мощности в январе, то общие затраты уменьшатся на 1,7 тыс. рублей.
Требует дополнительных пояснений и столбец Целевой коэффициент отчета по устойчивости. Приведенные здесь значения Excel вычисляет самостоятельно. Смысл целевого коэффициента при переменной состоит в том, что он показывает, насколько увеличится значение целевой функции при увеличении оптимального значения переменной на единицу.
В этом легко убедиться на практике. Оптимальное значение производства полиуретана в январе – 60 тонн, а суммарные затраты равны 4 776,45 тыс. рублей. Если в качестве оптимального значения за январь подставить число 61 и пересчитать суммарные затраты, то получим новое значение – 4 805,50. Разность этих чисел как раз и равна 29,05 – целевому коэффициенту при переменной объема производства в январе.
Широко известны и другие постановки задач динамического программирования. Некоторые из них (модель замены оборудования и модель инвестиций) будут рассмотрены на практических занятиях. Модель линейного программирования – модель, включающаяя линейную функцию цели, определяемую линейной зависимостью от нескольких переменных, и линейные ограничения на указанные переменные.

Экстремальные задачи

Напомним, что латинское слово extremum означает "крайнее". Оно в математике имеет два конкретных значения: maximum (сокращенно max ) - наибольшее и minimum (сокращенно min ) - наименьшее. В таком понимании extremum имеет более узкий смысл, чем optimum , переводимый от латинского как "наилучшее".
Задача нахождения максимального или минимального значения заданной функции на заданном множестве называется экстремальной задачей .
Имеется два вида экстремальных задач - задача на максимум и задача на минимум. Символически они записываются так:

Функция f(x) называется целевой функцией , а Х - множеством допустимых решений . Оптимальным решением задач называется пара (x*,f(x*)) , где x* - точка максимума (минимума), а f(x*) , - значение функции f в этой точке, то есть ее максимальное (минимальное) значение на множестве Х .
Решить задачи это значит: либо найти оптимальное решение; либо убедиться, что оптимальное решение не существует.
Решение задачи требует разрешения трех проблем: 1) проблему существования оптимального решения; 2) проблему установления необходимых и достаточных признаков оптимальности (то есть характерных свойств, присущих точкам максимума и минимума); 3) проблему численного вычисления оптимальных решений.

Пример №1 . Построить математическую модель следующей задачи экономической деятельности. Для этого:

1. Выявить проблему и сформулировать цель исследования.
2. Провести описание переменных экономического процесса или объекта.
3. Записать математическую формулировку функции цели.
4. Сформулировать ограничения накладываемые условиями задачи и записать систему ограничений.
5. Предложить метод решения.

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

Характеристики	Материалы
	Металл	Стекло	Пластмасса
Стоимость (тыс. руб./м 2)	25	20	40
Масса (кг/м 2)	10	15	3

Общая поверхность кузова (вместе с дверьми и окнами) должна составлять 14 м 2: из них не менее 3,5 м 2 и не более 5 м 2 следует отвести под стекло. Масса кузова не должна превышать 150 кг, а масса пластмассы не должна превышать 20% от массы кузова. Металлическая составляющая поверхности кузова должна превышать стеклянную поверхность не менее, чем в два раза. Сколько металла, стекла и пластмассы должен использовать наилучший проект.

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

Описание переменных.
x 1 - количество металла, м 2
x 2 - количество стекла, м 2
x 3 - количество пластмассы, м 2

Функция цели.

Ограничения:

• Общая поверхность кузова
  x 1 + x 2 + x 3 ≥ 14
• Требования по стеклу
  x 2 ≥ 3,5
  x 2 ≤ 5
• Ограничения по массе
  10x 1 + 15x 2 + 3x 3 ≤ 150
• Требования по массе пластмассы
  3x 3 ≤ (10x 1 + 15x 2 + 3x 3)*20%
• Ограничения по поверхности
  x 1 ≥ 2x 2

Система ограничений.
x 1 + x 2 + x 3 ≥ 14
10x 1 + 15x 2 + 3x 3 ≤ 150
2x 1 + 3x 2 - 2,4x 3 ≥ 0
x 1 - 2x 2 ≥ 0
x 2 ≥ 3,5
x 2 ≤ 5
x 1 , x 2 , x 2 ≥ 0
F(x) = 25x 1 + 20x 2 + 40x 3 → min

Пример №2 . На фабрике производится ткань двух артикулов. Каждая из этих тканей проходит последовательную обработку на станках их трех типов. Ниже указаны: производительность станка каждого типа при изготовлении тканей артикулов 1 и 2; суммарные мощности станочного парка фабрики в расчете на одну рабочую неделю; трудовые затраты по обслуживанию станков в минутах рабочего времени на 1 час работы станка; цена метра ткани каждого артикула. Известно также, что недельный ресурс трудозатрат на обслуживание станков равен 14800 ч.

Тип станков	Мощность (тыс. ч)	Трудозатраты (мин/ч)	Производительность, м/ч
			Артикул 1	Артикула2
1	22	10	20	15
2	40	6	12	6
3	75	6	6	4
Цена 1 м ткани (тыс.руб.)			18	25

Требуется составить недельный план выпуска тканей с целью максимизации прибыли изготовленной продукции, если 1 час оплачивается в размере 5400 рублей, а 1 час простоя станка 1-го типа составляет 1800 рублей, 2-го типа составляет 2000 рублей, 3-го типа составляет 1400 рублей. Стоимость сырья в расчет не принимать. При решении задачи следует учесть, что выпуск ткани артикула 1 должен не мене чем в 2 раза превышать выпуск ткани артикула 2.

Описание переменных.
x 1 - выпуск тканей артикула 1, м
x 2 - выпуск тканей артикула 2, м

y 1 - время работы 1-го станка, час.
y 2 - время работы 2-го станка, час.
y 3 - время работы 3-го станка, час.

y 1 =x 1 /20 + x 2 /15
y 2 =x 1 /12 + x 2 /6
y 3 =x 1 /6 + x 2 /4
x 1, x 2 , y 1 , y 2 , y 3 ≥ 0

Ограничения:

• по структуре выпуска
  x 1 ≥ 2x 2
• по трудозатратам
  10/60y 1 + 6/60y 2 +6/60y 3 ≤ 14800
  или
  1/6y 1 + 1/10y 2 +1/10y 3 ≤ 14800
• по имеющимся мощностям:
  y 1 ≤ 22000
  y 2 ≤ 40000
  y 3 ≤ 75000

Функция цели.
Прибыль = Выручка - Затраты = Цена*Количество - Затраты на простой станков - Трудозатраты
Выручка = 18x 1 + 25x 2
Затраты на простой станков =1,8y 1 + 2y 1 + 1,4y 3
Трудозатраты = 5,4(1/6y 1 + 1/10y 2 +1/10y 3)

F(x) = 18x 1 + 25x 2 - 1,8y 1 - 2y 2 - 1,4y 3 - 5,4(1/6y 1 + 1/10y 2 +1/10y 3)→ max
или
F(x) = 1/50 (900x 1 +1250x 2 -135y 1 -127y 2 -97y 3) → max

С учетом
y 1 =x 1 /20 + x 2 /15
y 2 =x 1 /12 + x 2 /6
y 3 =x 1 /6 + x 2 /4

имеем:

Система ограничений.
x 1 ≥ 2x 2
1/6(x 1 /20 + x 2 /15) + 1/10(x 1 /12 + x 2 /6) +1/10(x 1 /6 + x 2 /4) ≤ 14800
x 1 /20 + x 2 /15≤ 22000
x 1 /12 + x 2 /6 ≤ 40000
x 1 /6 + x 2 /4 ≤ 75000

x 1 ≥ 2x 2
x 1 /30+19x 2 /360 ≤ 14800
x 1 /20 + x 2 /15≤ 22000
x 1 /12 + x 2 /6 ≤ 40000
x 1 /6 + x 2 /4 ≤ 75000

F(x) = 17.33x 1 +23.91x 2 → max

Пример №3 . На предприятии имеется два цеха. В первом цеху работают 50 рабочих, из них 20 имеют 6 разряд и 30 - третий разряд. Во втором цеху, из 100 рабочих 50 имеют 6 разряд и остальные - третий. Требуется выполнить заказ на изготовление 2 типов деталей. На изготовление одной детали первого типа рабочий 6 разряда тратит 10 мин., а рабочий 3 разряда - 15 мин. На изготовление одной детали второго типа рабочий 6 разряда тратит 25 мин., а рабочий третьего - 30 мин.
13) составить план выпуска продукции для каждого из цехов на неделю, исходя из стандартной продолжительности рабочей недели, максимизирующий общий объем выпуска продукции с учетом того, что потребность в детали второго типа в два раза меньше потребности в деталях первого типа.
14) Определить план выпуска продукции для каждого из цехов на неделю, исходя из стандартной продолжительности рабочей недели, максимизируя прибыль, с учетом того, что рабочий 6 разряда получает 300 руб./мес., а рабочий 3 разряда - 200 руб./мес., притом, что цена реализации детали 1 типа равна 20 руб./шт, а второго типа - 34 руб./шт.

Решение.
x 11 - количество деталей 1 типа, изготовленные рабочими 6 разряда за неделю,
x 12 - количество деталей 2 типа, изготовленные рабочими 6 разряда за неделю,
x 21 - количество деталей 1 типа, изготовленные рабочими 3 разряда за неделю,
x 22 - количество деталей 2 типа, изготовленные рабочими 3 разряда за неделю,

13) Целевая функция
20x 11 + 50x 21 + 30x 12 + 50x 22 = max

Ограничения:
2(x 12 +x 22) ≤ x 11 +x 21

14) Целевая функция: Прибыль = Доход - Затраты = Количество деталей * Цена реализации - ЗП работников
Затраты на заработную плату рабочим приведем к недельным, т.е разделим месячный заработок на 4.
F(x) = 20(20x 11 + 50x 21) + 23(30x 12 + 50x 22) - [(20+50)*300 + (30+50)*200]/4 = max

Ограничения:
2(x 12 +x 22) ≤ x 11 +x 21
10/60x 11 + 15/60x 21 + 25/60x 11 + 30/60x 21 ≤ N
N - недельный фонд времени в часах.

Линейное программирование - один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и др. задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми.

Итак, линейное программирование возникло после Второй Мировой Войны и стал быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а так же математической «стройности».

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

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

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

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

Так, по оценкам американских экспертов, около 75% от общего числа применяемых оптимизационных методов приходится на линейное программирование. Около четверти машинного времени, затраченного в последние годы на проведение научных исследований, было отведено решению задач линейного программирования и их многочисленных модификаций.

Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например:

• · количество продукции - расход сырья
• · количество продукции - качество продукции

Выбор компромиcного варианта для указанных свойств и представляет собой процедуру решения оптимизационной задачи.

При постановке задачи оптимизации необходимо:

1. Наличие объекта оптимизации и цели оптимизации. При этом формулировка каждой задачи оптимизации должна требовать экстремального значения лишь одной величины, т.е. одновременно системе не должно приписываться два и более критериев оптимизации, т.к. практически всегда экстремум одного критерия не соответствует экстремуму другого. Приведем примеры.

Типичный пример неправильной постановки задачи оптимизации:

«Получить максимальную производительность при минимальной себестоимости».

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

Правильная постановка задачи могла быть следующая:

• а) получить максимальную производительность при заданной себестоимости;
• б) получить минимальную себестоимость при заданной производительности;

В первом случае критерий оптимизации - производительность, а во втором - себестоимость.

• 2. Наличие ресурсов оптимизации, под которыми понимают возможность выбора значений некоторых параметров оптимизируемого объекта.
• 3. Возможность количественной оценки оптимизируемой величины, поскольку только в этом случае можно сравнивать эффекты от выбора тех или иных управляющих воздействий.
• 4. Учет ограничений.

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

Критерием оптимальности называется количественная оценка оптимизируемого качества объекта.

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

Таким образом, задача оптимизации сводится к нахождению экстремума целевой функции.

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

Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных.

В общем виде модель записывается следующим образом:

Целевая функция:

При этом aij, bi, cj () - заданные постоянные величины.

Задача состоит в нахождении оптимального значения функции (1.1) при соблюдении ограничений (1.2) и (1.3).

Систему ограничений (1.2) называют функциональными ограничениями задачи, а ограничения (1.3) - прямыми.

Вектор, удовлетворяющий ограничениям (1.2) и (1.3), называется допустимым решением (планом) задачи линейного программирования. План, при котором функция (1.1) достигает своего максимального (минимального) значения, называется оптимальным.

МАТЕМАТИЧЕСКОЕ ОПИСАНИЕ МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

МОДЕЛЬ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

1 Математическое описание модели линейного программирования

2 Методы реализации моделей линейного программирования

3 Двойственная задача линейного программирования

Модель линейного программирования (ЛП) имеет место, если в исследуемой системе (объекте) ограничения на переменные и целевая функция линейны .

Модели ЛП используются для решения двух основных типов прикладных задач:

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

2) транспортной задачи (нахождение оптимального плана различного рода перевозок, оптимального плана распределения разных средств по объектам различного назначения и т. п.)

МАТЕМАТИЧЕСКОЕ ОПИСАНИЕ МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Требуется найти неотрицательные значения переменных

удовлетворяющих линейным ограничениям в виде равенств и неравенств

,

где – заданные числа,

и обеспечивающих экстремум линейной целевой функции

,

где – заданные числа, что записывается в виде

Допустимым решением называется любая совокупность , удовлетворяющих условиям.

Область допустимых решений – множество всех допустимых решений.

Оптимальное решение
, для которого .

Замечания

1. Приведенная модель ЛП является общей . Различают также стандартные и канонические формы моделей ЛП.

2. Условия существования реализации модели ЛП:

– множество допустимых решений – не пустое;

– целевая функция ограничена на (хотя бы сверху при поиске максимума и снизу при поиске минимума).

3.ЛП основывается на двух теоремах

Теорема 1. Множество G , определяемое системой ограничений вида, есть выпуклое замкнутое множество (выпуклый многогранник в с угловыми точками - вершинами .)

Теорема 2. Линейная форма , определенная на выпуклом многограннике

j =1,2,…,s

i=s +1,s+2,…,m ,

достигает экстремума в одной из вершин этого многогранника.

Данная теорема получила название теоремы об экстремуме линейной формы.

В соответствии с теоремой Вейерштрасса оптимальное решение единственно и является глобальным экстремумом.

Существует общий аналитический подход к реализации модели ЛП – симплекс-метод. При решении задач линейного программирования достаточно часто решения нет. Это происходит по следующим причинам.

Первую причину проиллюстрируем примером

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

Вторая причина комментируется следующим примером:

В данном случае, область допустимых решений не ограничена сверху. Область допустимых решений не ограничена.

Следуя традициям линейного программирования, дадим задаче ЛП экономическую интерпретацию. Пусть в нашем распоряжении имеется m типов ресурсов. Количество ресурса типа j равно . Эти ресурсы необходимы для производства n типов товаров. Обозначим количество этих товаров символами соответственно. Единица товара типа i стоит . Производство товаров типа i должно быть ограничено величинами соответственно. На производство единицы товара типа i расходуется ресурса типа j . Необходимо определить такой план производства товаров (), чтобы их суммарная стоимость была минимальной.

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

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

Алгебраические методы решения задачи ЛП начинаются с приведения ее к стандартной (канонической) форме :

,

,

i =1,..,n ; j =1,..,m .

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

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

Предполагается, что правая часть неравенств неотрицательна. В противном случае, этого можно добиться умножением обеих частей неравенства на «-1» и сменой его знака на противоположный.

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

Важной особенностью переменных является то, что при любом допустимом решении только одна из них может принимать положительное значение. Это означает, что если , то и наоборот. Следовательно, может рассматриваться как остаточная, а - как избыточная переменные.

Пример Пусть дана задача линейного программирования:

,

.

Необходимо привести ее к стандартной форме. Заметим, что первое неравенство исходной задачи имеет знак , следовательно, в него необходимо ввести остаточную переменную . В результате получим .

Второе неравенство имеет знак и для преобразования к стандартной форме требует введения избыточной переменной , выполнив эту операцию, получим .

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

.

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

Пусть ранг матрицы системы ограничений равен m . Это значит, что матрица имеет хоть один минор m -го порядка не равный нулю. Не нарушая общности, можно предположить, что минор расположен в левом верхнем углу матрицы. Этого всегда можно добиться, изменив нумерацию переменных. Этот не равный нулю минор ранга m принято называть базисным. Составим систему из первых m уравнений системы, записав ее следующим образом:

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .