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

Формулировка общего задания линейного программирования. Особенность применения графического метода при решении транспортной задачи. Реализация алгоритма симплекс-метода на языке паскаль. Сущность модульно-рейтинговой системы контроля успеваемости.

Рубрика Программирование, компьютеры и кибернетика
Вид учебное пособие
Язык русский
Дата добавления 22.10.2015
Размер файла 2,3 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Рассмотрим на плоскости множество М. Пусть Р -- произвольная точка этого множества. Возможно ли во множестве М перемещение точки Р в близкую ей точку так, чтобы при этом увеличились обе ее координаты? Если Р -- внутренняя точка, то такое перемещение возможно. Если Р -- граничная точка, то такое перемещение не всегда возможно. Иллюстрацией служит рис. 65. Требуемое перемещение точек ,,, возможно, а ни одна из точек как отрезков и , так и дуги такому перемещению подвергнута быть не может. Действительно, при перемещении любой точки

· вертикального отрезка может увеличиваться лишь координата этой точки (координата при этом останется неизменной);

· горизонтального отрезка может увеличиваться лишь координата (координата при этом останется неизменной);

· дуги увеличение одной координаты влечет уменьшение другой.

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

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

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

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

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

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

Указанная задача является частным случаем многокритериальной задачи в случае p = 2. Сформулируем ее. Пусть на плоскости задано множество (Рис. 66) и в каждой точке этого множества определены две непрерывные функции =и =. Необходимо найти значения переменных, при которых указанные функции принимают наибольшие значения. Формулировку задачи максимизации с двумя целевыми функциями можно записать более компактно:

> max;

> max

при ограничениях:

.

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

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

1. Метод (последовательных) уступок.

2. Метод идеальной точки.

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

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

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

Замечание 1. Задачу максимизации можно путем умножения целевой функции на (-1) преобразовать в задачу минимизации, решаемую при тех же самых ограничениях. Это связано с наличием следующего свойства: функция достигает наибольшего значения в тех точках, в которых функция f принимает наименьшее значение, и наоборот. Это означает, что условия [f > min] и [> max] равносильны. Следовательно, поменяв знак целевой функции на противоположный, любую двухкритериальную задачу можно свести к задаче максимизации с двумя целевыми функциями.

4. Применение метода идеальной точки

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

Пример 1. Найти значения переменных, при которых функции

=> max;

= > max

при ограничениях:

Решение. Введем на плоскости прямоугольную систему координат и построим множество -- область допустимых решений данной задачи в указанной системе координат. Ограничительные условия определяют на плоскости многоугольник ABCDE (Рис. 68), вершины которого имеют соответственно координаты: (0; 0), (0; 3), (2; 3), (6; 1), (6; 0). Следовательно, представляет собою многоугольник ABCDE.

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

Подвергнем координаты каждой точки плоскости преобразованиям = и =. Получим плоскость . При этом в силу линейности проводимых преобразований прямоугольная система координат перейдет в прямоугольную систему координат , а многоугольник ABCDE в многоугольник A*B*C*D*E*, вершины которого имеют соответственно координаты: (1; 5), (4; 2), (8; 4), (14; 10), (13; 11) (рис. 69). Для наглядности укажем описанное соответствие вершин: A(0; 0) > A*(1; 5), B(0; 3) > B*(4; 2), C(2; 3) > C*(8; 4), D(6; 1) > D*(14; 10), E(6; 0) > E*(13; 11).

Таким образом, все точки, координаты которых удовлетворяют условиям =, = и , определяют на плоскости многоугольник A*B*C*D*E*. Следовательно, область допустимых решений данной задачи в системе координат (пространстве критериев) представляет собою многоугольник A*B*C*D*E*.

Рис. ОДР в пространстве критериев и множество Парето

Находим множество Парето. Это отрезок D*E*. В условии задачи
не сказано, что считать точкой утопии. Поэтому выбираем комбинацию наилучших значений всех критериев. В данном случае это точка U с координатами (14; 11).

Теперь необходимо найти во множестве Парето точку, расположенную ближе всех к точке утопии U. Из видно, что точка I(,), являющаяся основанием перпендикуляра, проведенного из точки U (14; 11) к прямой D*E*, принадлежит отрезку D*E*. Это означает, что точка I -- искомая. Найдем ее координаты.

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

,

где , и , -- координаты точек D* и E* соответственно. Подставляя сюда числовые значения для координат D* и E*, находим:

, или +=24.

Нормальным вектором прямой D*E* является вектор (1; 1), направляющим вектором для прямой UI. Следовательно, ее каноническое уравнение имеет вид:

,

где , -- координаты точки U. Подставляя сюда числовые значения для координат U, находим:

, или -=3.

Точка I принадлежит прямым D*E* и UI (рис. 70). Поэтому ее координаты удовлетворяют системе уравнений

Отсюда находим , .

Рис. Идеальная точка

Расстояние d между точками Iи U(14; 11) равно длине вектора = (=, которая, в свою очередь, равна корню квадратному из суммы квадратов его координат. Поэтому

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

Имеем

Таким образом, Парето-оптимальное решение достигается при а идеальная точка находится от точки утопии (14; 11) на расстоянии .

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

> min,

или, опуская знак квадратного корня,

> min,

где и -- неизвестные координаты искомой точки I, а и -- уже найденные координаты точки утопии U.

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

Пример 2. Найти значения переменных, при которых функции

=> max;

= > min

при тех же ограничениях, что и в примере 1.

Решение. Введем функцию = . Тогда, согласно замечанию 1, исходная задача преобразуется в задачу максимизации

=> max;

= > max.

Ограничительные условия те же, что и в примере 1. Они определяют на плоскости многоугольник ABCDE (рис. 68), который функции = и = переводят в многоугольник A*B*C*D*E*. Его вершины в плоскости (пространстве критериев) имеют соответственно координаты: (; ), (;), (;), (; ), (; ) (рис. 71).

Множество Парето образуют точки ломаной B*C*D*. Как и в примере 1, в условии не сказано, что считать точкой утопии. Поэтому снова выбираем комбинацию наилучших значений всех критериев. В данном случае это точка U с координатами (заметим, что в исходной задаче ей соответствует точка с координатами , и, следовательно, в исходной задаче точкой утопии является она). Из рис. 71 видно, что точка, принадлежащая ломаной B*C*D* и находящаяся на минимальном расстоянии от точки утопии, должна принадлежать отрезку C*D*. Обозначим ее через (;). Для отыскания ее координат воспользуемся способом, описанным в замечании 2. Согласно этому способу, нужно минимизировать функцию расстояния между точкой(;) и точкой U:

> min,

> min.

Составим уравнение прямой C*D* (подробности см. в примере 1). Имеем

, или +=4.

Точка принадлежит множеству точек отрезка C*D*. Следовательно, ее координаты удовлетворяют уравнению прямой C*D*: += 4, или Это означает, что минимизируется функция на отрезке. Вычисляем производную и находим стационарную точку: Легко видеть, что < 0 на промежутке и > 0 на промежутке . Следовательно, -- точка минимума функции на отрезке , а -- точка минимума функции = в замкнутой области, определяемой неравенствами и , при этом = = . Заметим, что в исходной задаче точке соответствует точка .

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

Имеем

Таким образом, Парето-оптимальное решение достигается при При этом идеальная точка находится от точки утопии на расстоянии .

5. Пример решения экономической задачи
с двумя критериями эффективности

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

Задача 1. ОАО «Мукомольный завод „Балашовский“» реализует хлебопекарную муку высшего сорта двумя способами: через сеть магазинов и через прямые поставки по договорам неторговым организациям. Известно, что ежемесячно магазины могут реализовать не более 50 тыс.,
а ежемесячные поставки неторговым организациям не должны превышать 35 тыс. т муки. Для продажи в каждом месяце выделяется не более 45 тыс. т муки. Предприятие выработало определенную политику в области ценообразования, которой собиралось следовать. Однако в связи
с сильно изменившейся экономической ситуацией, затраты на реализацию увеличились, а мука вошла в перечень продуктов, которые должны продаваться по ранее установленной цене, регулируемой местной властью. При продаже одной тонны муки через магазины расходы на реализацию стали составлять 7 тыс. руб., а цена осталась прежней -- 10 тыс. руб.; при втором способе реализации расходы и цена составили 4 и 6 тыс. руб. соответственно. Необходимо определить, сколько тонн муки следует продавать каждым способом, чтобы расходы были минимальными, а выручка от продажи -- максимальной.

Решение. Составим математическую модель задачи.

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

Тогда целевые функции имеют вид:

=> min;

=> max

при ограничениях:

Введем функцию = . Тогда исходная задача преобразуется в задачу максимизации

= > max;

= > max.

Ограничительные условия остаются прежними. Они определяют на плоскости многоугольник ABCD (рис. 72), который функции и переводят в многоугольник A*B*C*D* плоскости :

A(0; 0) > A*(0; 0), B(0; 35) > B*(-175; 280),

C(10; 35) > C*(-245; 380), D(45; 0) > D*(-315; 450) (Рис. 73).

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

Множество Парето образуют точки ломаной A*B*C*D*. Выбираем комбинацию наилучших значений всех критериев. В данном случае это точка U с координатами . Необходимо найти во множестве Парето точку, расположенную ближе всех к точке утопии U. Обозначим ее через (;). Для отыскания координат указанной точки минимизируем функцию расстояния между точкой(;) и точкой U:

> min,

> min.

Из рис. 73 видно, что искомая точка находится на отрезке B*C*.

Составим уравнение прямой B*C*. Имеем

, или .

Точка принадлежит множеству точек отрезка B*C*. Следовательно, ее координаты удовлетворяют уравнению прямой B*C*: += 210, или . Это означает, что на отрезке минимизируется функция . Вычисляем производную и находим стационарную точку: . Из того, что < 0 на промежутке [-245; ) и > 0 на промежутке (; -175], следует: -- точка минимума функции на отрезке . Тогда -- искомая точка, что соответствует точке в исходной задаче.

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

Имеем

Таким образом, объемы реализации хлебопекарной муки высшего сорта ОАО «Мукомольный завод „Балашовский“» должны составить: 3,19 тыс. т через сеть магазинов и 35 тыс. т через прямые поставки по договорам неторговым организациям. При таких способах и объемах реализации расходы будут минимальными (составят 197,32 тыс. руб.), а выручка -- максимальной (составит 311,88 тыс. руб.).

6. Применение симплексного метода при решении многокритериальных задач

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

Сначала сформулируем задачу:

L1(X) =max,

L2(X) =min

при ограничениях:

Bi,

xj0 для i = , j = .

Теперь опишем один из возможных методов ее решения.

Решают задачу

L1(X) =max,

при тех же ограничениях, что и у исходной задачи.

Решают задачу

L2(X) =min,

оставляя ограничения неизменными.

Решают задачу

L=xn+1min

при ограничениях:

xj 0 для i = , j = .

На каждом из этапов применяют симплексный метод.

Алгоритм нахождения эффективного решения задач, имеющих более двух целевых функций, аналогичен.

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

Задача 2. АООТ «Прицеп» выпускает 4,5-тонные прицепы и кормораздатчики «Ванюша» по цене 40,3 и 74,3 тыс. руб. соответственно. По результатам маркетинговых испытаний спрос на изделия первого вида не менее 1 200 шт. в год. Для производства прицепов используются сталь
и чугун, запасы которых на предприятии составляют 25 000 и 4 500 т соответственно. Для изготовления одной тысячи прицепов норма расхода стали составляет 1 615 т, а чугуна -- 385 т. Для изготовления одной тысячи кормораздатчиков расходуется: стали -- 2 022 т, чугуна -- 478 т. Себестоимость прицепов -- 34,66, а кормораздатчиков -- 63,9 тыс. руб. Составить годовой план производства прицепов и кормораздатчиков, такой, чтобы количество выпускаемых изделий и выручка от их реализации
были максимальными, а себестоимость -- минимальной.

Решение. Обозначим через x1 количество прицепов (тыс. шт.); x2 -- количество кормораздатчиков (тыс. шт.), выпускаемых АООТ «Прицеп» в год.

Математическая модель задачи будет иметь вид:

L1 = x1 + x2max,

L2 = 40,3x1 + 74,3x2max,

L3 = 34,66x1 + 63,9x2min

при ограничениях:

x10, x20.

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

X1 опт = (11,688; 0), X2 опт = (1,2; 8,448), X3 опт = (1,2; 0),

L1 max = 11,688, L2 max = 676,0464, L3 min = 41,592.

Математическая модель задачи нахождения эффективного решения
в канонической форме имеет вид:

L= x3min

при ограничениях

xj0, j = .

Получим Xэффект = (1,2; 0,564). Таким образом, АООТ «Прицеп» целесообразно выпускать 1 200 прицепов и 564 кормораздатчика ежегодно. При таком плане производства количество изделий и выручка от их реализации будут максимальными (составят 1 764 единиц и 90,096 млн руб. соответственно), а себестоимость -- минимальной (составит 77,6316 млн руб.).

7. Упражнения

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

Ответ.

Ответы к упражнениям 1--6 сведены в таблицу 19:

Таблица 19

1

2

3

4

5

6

6,5

4,8

3

0

41

6,5

9,5

1,6

5

0

4

5,5

4

0

1

0

5

1,5

0,5

1,6

1

0

4

2

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

1. Модульно-рейтинговая система контроля успеваемости

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

Основными отличиями кредитно-модульной системы обучения от действующей являются:

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

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

Исходя из рекомендаций по введению Европейской переводной и накопительной системы кредитов (ECTS), авторами были разработаны оценочные средства для текущего контроля успеваемости и промежуточной аттестации студентов по материалу учебного модуля «Введение в линейное программирование». В качестве таких средств предлагаются: домашняя контрольная работа, выполненная с использованием вычислительной техники, и две аудиторные самостоятельные работы.

Начисление зачетных единиц (кредитов) 1 зачетная единица (кредит) = 36 академическим часам. осуществляется следующим образом. Пусть трудоемкость модуля внутри дисциплины составляет зачетных единиц (кредитов). Студент за полностью выполненные задания по материалу учебного модуля получает баллов. Пусть в результате проведения всех контрольных мероприятий студент получил
() баллов. Тогда количество , получаемых им за модуль кредитов, есть средневзвешенное значение: .

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

· если , то соответствующая оценка в четырехбалль-ной системе -- 2 (неудовлетворительно),

· если , то (удовлетворительно),

· если , то (хорошо),

· если , то (отлично).

Итоговый дисциплинарный рейтинг определяется по формуле:

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

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

2. Примеры оценочных средств

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

Домашняя работа на тему

«Введение в линейное программирование»

Задача. Фирма выпускает два вида продукции и, используя сырье трех видов: ,,. Каждый вид продукции (j = 1, 2) характеризуется технологией , где -- количество единиц сырья (i = 1, 2, 3), затрачиваемого на единицу продукции , -- розничная цена (в условных денежных единицах) каждой единицы продукции . Известны также объемы сырья каждого из трех видов: , располагаемых фирмой. Требуется составить такой план выпуска видов продукции P1 и P2, при котором доход от реализации всей продукции был бы максимальным. Значения параметров задачи приведены в таблице 20.

Содержание и оценка каждого этапа работы

1. Составить математическую модель планирования производства, записав соответствующую задачу линейного программирования (2 балла).

2. Изобразить графически множество допустимых решений задачи (3 балла).

3. Найти графическим методом оптимальный план выпуска продукции (3 балла).

4. Применяя графический метод, провести экономический анализ:

а) выяснить влияние изменения запасов исходного сырья на оптимальное решение (6 баллов);

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

5. Применяя алгоритм симплексного метода для расчетов вручную,

а) найти оптимальный план выпуска продукции (5 баллов) и

б) дать интерпретацию полученных результатов (3 балла).

6. Решить задачу линейного программирования на компьютере с использованием Microsoft Excel. Привести распечатку полученных решений, сравнить их с полученными вручную и сделать вывод (6 баллов).

Замечание 1. После выполнения домашней контрольной работы максимальное количество кредитов, которые может получить студент, равно

.

Таблица 20 Номер варианта и значения параметров условий задачи

В-т

З. п.

1

2

3

4

5

6

7

8

9

10

50

80

100

30

100

50

150

40

390

30

100

100

130

60

80

100

270

20

300

15

3

8

6

15

30

20

30

34

40

3

3

16

24

15

30

5

40

34

10

3

20

12

18

20

65

7

11

5

13

20

5

18

6

100

195

7

11

20

39

40

10

4

0

5

240

20

0

70

31

20

35

4

33

10

80

70

7

20

0

10

450

1 600

156

6 000

90

2 500

24 000

5 100

260

1 200

2 400

2 700

138

6 000

325

1 050

13 200

2 400

299

12 000

3 500

600

198

3 500

480

7 000

2 100

7 000

1 860

7 000

Демонстрационный вариант самостоятельной работы на тему «Применение графического метода при решении транспортной задачи»

1 (5 баллов). Найти значения переменных, при которых функция

L(X)= 4x11 + 9x12 + 6x13 + 4x21 + 9x22 + 7x23

принимает экстремальные значения при условии, что:

x11 + x12 + x13 =120,

x21 + x22 + x23 = 180,

x11 + x21 = 70,

x12 + x22 = 140,

x13 + x23 = 90,

x11 0, x120, x130, x210, x220, x230.

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

Демонстрационные варианты самостоятельной работы
на тему «Многокритериальная оптимизация»

Вариант 1

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

а критерии заданы соотношениями: =; =. Требуется:

1) изобразить множество допустимых решений и найти его вершины (1 балл);

2) найти и изобразить образ множества допустимых решений и образ его вершин в пространстве критериев (2 балла);

3) найти множество Парето и указать идеальную точку (3 балла);

4) найти расстояние от точки утопии до идеальной точки (1балл);

5) найти Парето-оптимальное решение (2 балла).

Вариант 2

В задаче двухкритериальной оптимизации

=> max; => min

множество допустимых решений задается системой неравенств

Точка утопии имеет координаты (2; -2). Требуется:

1) изобразить множество допустимых решений и найти его вершины (1 балл);

2) найти и изобразить образы множества допустимых решений и его вершин в пространстве критериев (2 балла);

3) найти множество Парето и указать идеальную точку (3 балла);

4) найти расстояние от точки утопии до идеальной точки (1 балл);

5) найти Парето-оптимальное решение (2 балла).

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

Список рекомендуемой литературы

Основная

Гантмахер, Ф. Р. Теория матриц / Ф. Р. Гантмахер. -- М. : Физматлит, 2010. -- 560 с.

Заварыкин, В. М. Численные методы : учеб. пособие для студентов физ.-мат. спец. пед. ин-тов / В. М. Заварыкин, В. Г. Житомирский, М. П. Лапчик. -- М. : Просвещение, 1990. -- 176 с.

Информатика : учеб. пособие для пед. спец. высш. учеб. заведений / А. Р. Есаян [и др.]. -- М. : Просвещение, 1991. -- 288 с.

Карманов, В. Г. Математическое программирование : учеб. пособие / В. Г. Карманов. -- М. : Физматлит, 2004. -- 264 с.

Карпелевич, Ф. И . Элементы линейной алгебры и линейного программирования / Ф. И. Карпелевич, Л. Е. Садовский. -- М. : Наука, 1967. --312 с.

Кострикин, А. И. Введение в алгебру. Ч. 2. Линейная алгебра : учеб. для вузов / А. И. Кострикин. -- М. : Физ.-мат. литература, 2009. -- 368 с.

Красс, М. С. Основы математики и ее приложения в экономическом образовании : учеб. / М. С. Красс, Б. П. Чупрынов. -- М. : Дело, 2008. -- 688 с.

Курс высшей математики для экономистов : учеб. / под ред. В. И. Ермакова. -- М. : Инфра-М, 2001. -- 656 с.

Леонтьев, В. Экономические эссе. Теория, исследования, факты и политика: пер. с анг. / В. Леонтьев. -- М. : Изд. полит. литературы, 1990. -- 415 с.

Солодовников, А. С. Математика в экономике : в 2 ч. Ч. 1 : учеб. / А. С. Солодовников, В. А. Бабайцев, А. В. Браилов. -- М. : Финансы и статистика, 2001. -- 224 с.

Шикин, Е. В. Математические методы и модели в управлении : учеб. пособие / Е. В. Шишкин, А. Г. Чхартишвили ; Академия народного хозяйства при правительстве Российской Федерации. -- М. : Дело, 2009. -- 440 с.

Дополнительная

Абчук, В. А. Экономико-математические методы: Элементарная математика и логика. Методы исследования операций / В. А. Абчук. -- СПб. : Союз, 1999. -- 320 с.

Вводные лекции по прикладной математике / А. Н. Тихонов, Д. П. Костомаров. -- М. : Наука, 1984. -- 192 с.

Капустин, В. Ф. Практические занятия по курсу математического программирования / В. Ф. Капустин. -- Л. : Изд-во Ленингр. ун-та, 1976. -- 192 с.

Кремер, Н. Ш. Высшая математика для экономистов / Н. Ш. Кремер,
Б. А. Путко, И. М. Тришин [и др.]. -- М. : Юнити, 2010. -- 479 с.

Ланкастер, П. Теория матриц / П. Ланкастер. -- М. : Наука, 1978. -- 280 с.

Матрицы и вычисления / В. В. Воеводин, Ю. А. Кузнецов. -- М. : Наука, 1984. -- 320 с.

Шелобаев, С. И. Математические методы и модели в экономике, финансах, бизнесе : учеб. пособие для вузов / С. И. Шелобаев. -- М. : ЮНИТИ-ДАНА, 2001. -- 367 с.

Размещено на Allbest.ru


Подобные документы

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

    курсовая работа [263,5 K], добавлен 27.03.2011

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

    курсовая работа [1,7 M], добавлен 05.01.2015

  • Общие задачи линейного программирования. Описание алгоритма симплекс-метода, записанного в канонической форме с односторонними ограничениями. Алгоритм построения начального опорного плана для решения задачи. Расширенный алгоритм искусственного базиса.

    курсовая работа [142,9 K], добавлен 24.10.2012

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

    курсовая работа [53,2 K], добавлен 30.09.2013

  • Решение базовых задач линейного программирования симплекс-методом, их реализация на языке программирования С++. Математическое обеспечение; разработка алгоритма программы, решающей задачу с помощью симплекс-таблиц с произвольными свободными членами.

    курсовая работа [217,8 K], добавлен 25.05.2014

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

    курсовая работа [88,9 K], добавлен 11.02.2011

  • Характеристика основных методов линейного программирования с n- переменными, в частности, графического и симплекс-метода. Способы решения задачи по определению оптимальной структуры товарооборота, обеспечивающей торговому предприятию максимум прибыли.

    курсовая работа [678,7 K], добавлен 03.04.2011

  • Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.

    курсовая работа [1,1 M], добавлен 21.03.2012

  • Сущность и описание симплекс-метода и улучшенного симплекс-метода (метода обратной матрицы), преимущества и недостатки их применения в линейном прогаммировании. Листинг и блок-схема программы на языке Turbo Pascal для решения математической задачи.

    курсовая работа [45,0 K], добавлен 30.03.2009

  • Приобретение теоретических и практических навыков программирования на языке Паскаль. Математическая формулировка задачи и выбор метода обработки информации. Разработка алгоритма и его описание. Описание программы. Форма представления исходных данных.

    курсовая работа [224,3 K], добавлен 11.02.2016

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.