Похожие публикации

Особому вниманию претендента! К участию в тендере
Документ
К участию в тендере допускаются производители и поставщики оборудования, имеющие опыт аналогичной поставки. Дилеры должны представить документы от про...полностью>>

Конкурс по теоретической информатике 2010-2011 учебный год Задания очно-заочного конкурса по теоретической информатике
Конкурс
Высказывания A, B, C истины для всех точек, принадлежащих треугольнику, кругу и прямоугольнику соответственно. Для какого высказывания истинно выделен...полностью>>

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

Положение о районных соревнованиях
Документ
«Открытое Первенство учащихся Калининского района по парковому ориентированию», посвященных 15-летию спортивного ориентирования в Доме Детского Творче...полностью>>



Махмутова Г. С., Фирстов В. Е

Махмутова Г.С., Фирстов В.Е.

Задачи дробно-линейного программирования на уроках алгебры

в профильных классах средней школы

Введение. Задачи дробно-линейного программирования (ДЛП) относятся к классу задач нелинейной оптимизации, допускающему линеаризацию и последующее решение в рамках симплекс-метода [1-3]. Процесс линеаризации использует алгебраический аппарат, входящий в программу по математике в профильных классах. Этот материал особенно наглядно и эффективно проводится в рамках элективного курса при реализации междисциплинарных связей математики. Цель работы – разработать методику проведения таких интегрированных занятий по разделу ДЛП.

1. Постановка задачи ДЛП. Рассмотрим задачу в общей постановке: найти экстремум (max или min) дробно-линейной целевой функции:

→ extremum (1)

в области G, определяемой канонической системой линейных ограничений

(2)

c условием неотрицательности: . (3)

Без ограничения общности, можно считать, что знаменатель функции (1) в области G в нуль не обращается и сохраняет знак так, что в дальнейшем полагаем: в G (4)

Соотношения (1)-(4) – определяют задачу ДЛП.

2.Приведение задачи ДЛП к эквивалентной задаче ЛП [2]. Введем новые переменные:

у0 = ( )-1 ; yj= y0xj, j= (5)

и подставим (5) в (1) – (4). В результате получим:

→ extremum (6)

(7)

. (8)

Кроме того, из соотношений (5) получается еще одно уравнение:

(9)

Таким образом, от задачи ДЛП вида (1) – (4) с помощью преобразований (5) мы пришли к задаче (6) – (9), в которой целевая функция (6) и система ограничений (7) – (9) линейны, т.е. получили задачу ЛП вида (6) – (9), эквивалентную исходной нелинейной задаче ДЛП вида (1) - (4).

Отметим, что переход (5) от нелинейной задачи ДЛП (1) – (4), с n параметрами управления х1...хn, приводит к эквивалентной задаче ЛП (6) – (9), содержащей n+1 параметров управления у0, у1...уn, т.е. линеаризация задачи ДЛП достигается за счет увеличения ее размерности на 1.

3. Пример сведения задачи ДЛП к задаче ЛП. Пусть поставлена задача: найти максимальное значение функции при решений системе ограничений (10)

Решение: Введем обозначение Тогда Обозначим:

Целевая функция запишется так: Преобразуем систему ограничений (10), умножив обе части всех ограничений на:

(11)

и перейдем к переменным

(12)

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

4. Графо-аналитический метод решения задачи ДЛП [1]. Графо- аналитический метод позволяет решать задачи ДЛП размерности

Пусть на плоском выпуклом многоугольнике ограничений G требуется оптимизировать (по max или min) целевую функцию вида

(13)

где cx+dy0 в области G, a,b,c,d – числовые коэффициенты, которые в данном случае следует ограничить условием bc-ad0, т.к. в противном случае получается F=const и задача оптимизации теряет смысл. Выражение (13) преобразуем к виду (Fd-b)y=(a-Fc)x, где выражения в скобках в 0 не обращаются по тем же причинам, что и выше.

Поэтому имеем , где

Уравнения (14) на координатной плоскости определяет пучок прямых, проходящих через начало координат, т.к. угловой коэффициент k параметрически зависит от F (рис. 1) При фикси-рованном значении F коэффициент k также фиксирован, поэтому прямая (14) займет некоторое определенное положение относи-тельно G. Например, при F=F1, k=k1; при F=F2, k=k2, т.е. при изменении F прямая поворачивается относительно начала координат.

Установим, как ведет себя коэффициент k в зависимости от F. Для этого исследуем производную:

Отсюда видно, что зависимость k (F) монотонно возрастающая при bc-ad>0 и монотонно убывающая при bc-ad<0. Поэтому при вращении прямой (14) относительно начала координат в одном направлении функция F также будет или только возрастать, или только убывать. Установив направление вращения в сторону возрастания F, поворачивая прямую в нужном направлении, определим ее экстремальное расположение относительно области G и, таким образом, определим экстремальное значение F, т.е. находим решение задачи ДЛП.

5. Пример решения задачи ДЛП графо-аналитическим методом [4].

Задача минимизации себестоимости перевозки грузов подвижным составом железнодорожной станции. На некотором направлении ж.д. станция организует перевозку грузов А, Б, В, и Г, для чего снаряжаются два ж.д. состава. Исходя из условий наилучшего использования подвижного состава, и, учитывая совместимость и грузовую специализацию, каждый состав может иметь определенное количество грузов, указанное в табл. 1, Там же приведены эксплуатационные расходы на каждый состав за 1 рейс.

Таблица 1

Груз

Тоннаж перевозки, не менее, т.

Кол-во груза за 1 рейс, т

1-й состав

2-й состав

А

21000

3000

3000

Б

10000

1000

2000

В

4000

4000

Г

4000

2000

Эксплуатационные расходы

за 1 рейс, у.е.

12000

16000

Необходимо составить оптимальный план перевозок грузов, который бы обеспечивал минимальную себестоимость 1 т груза, если состав 1-го типа может сделать не более 5 рейсов, а состав 2-го типа - не более 9 рейсов.

1) Математическая модель задачи. Пусть х, у число рейсов, соответственно, 1-го и 2-го составов. Тогда 12000 х расходы на перевозку для 1-го состава, 16000 у то же для 2-го состава и Р=12000х+16000у общие эксплуатационные расходы по перевозке грузов А,Б,В,Г,Д (в у.е.). При этом, 6000х тоннаж перевозок 1-м составом, 9000у то же для 2-го состава (табл. 4) и Т=6000х+9000у общий тоннаж перевозок. Составим целевую функцию задачи, которая представляет себестоимость перевозки 1т груза:

(16)

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

(17)

По условию, требуется минимизировать дробно-линейную функцию (16) в области ограничений G, определенной системой линейных неравенств (17). Соотношения (16), (17) определяют математическую модель данной задачи, которая представляет задачу ДЛП с двумя параметрами управления х и у, т.е.рассматриваемая задача имеет графическое решение.

2).Графическое решение задачи. Для этого строим многоугольник ограничений G, исходя из системы (17) (рис. 2). Выражая из (16) переменную у, получаем: y=kx, где k = . (18)

Определим производную: . (19)

Из неравенства (19) видно, что с увеличением S коэффициент k уменьшается. Поэтому для уменьшения S прямую (18) следует поворачивать против часовой стрелки (рис. 2). Поворачивая прямую (18) против часовой стрелки относительно начала координат, находим ее крайнее положение, когда она проходит через вершину А(2;9) (рис. 2).

Уравнение прямой (18) через точки 0 и А имеет вид у = 9x/2 и,

Рис.2

следовательно, значение углового коэффициента k = 9/2 соответствует минимуму себестоимости S. Тогда из соотношения для k из (18) имеем

S = Smin= 56/311,81 у.е./т. и минимум себестоимости перевозки грузов А, Б, В, Г достигается, если 1-й состав сделает х=2 рейса, а 2-й состав сделает у=9 рейсов.

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

Литература

  1. Беляева Э. С., Экстремальные задачи. Пособие для учащихся 8 -10 классов / Э. С. Беляева, В. М. Монахов, - М., «Просвещение», 1977.

  2. Вуколов Э. А. Сборник задач по математике для втузов. Ч. 4. Методы оптимизации. Уравнения в частных производных. Интегральные уравнения: Учеб. пособ. / Э. А. Вуколов, А. В. Ефимов, В. Н. Земсков и др.; Под ред. А. В. Ефимова. – 2-е изд., перераб. – М.: Наука, 1990.

  3. Габасов Р. Методы оптимизации / Р. Габасов, Ф. М. Кириллова, - Мн., Изд-во БГУ, 1975.

4. Фирстов В.Е. Кибернетическая концепция и математические модели управления дидактическими процессами при обучении математике в школе и вузе / В.Е. Фирстов. – Саратов: Издательский Центр «Наука», 2010. – 511 с.

Сведения об авторах

Махмутова Галия Сяитовнамагистрант гр. 218 механико-математического ф-та СГУ им. Н.Г. Чернышевского.

Контакты: E-mail: galia 1951@

Phone: 8 927 125 76 48

Фирстов Виктор Егорович – профессор кафедры компьютерной алгебры и теории чисел, механико-математического ф-та СГУ им. Н.Г. Чернышевского, доктор педагогических наук.

Контакты: E-mail: firstov1951@

Phone: 8 927 622 55 95