Лекция 2

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

Учебные вопросы:

1.Основныепонятия линейногопрограммирования.

2.Графическоерешение задачи о рационе(диете).

3.Решениезадачи о рационев надстройке «Поиск решения».

4.Решениезадачи о распределении ресурсов.

1

ЛИТЕРАТУРА

Линейное программирование. Оптимальное распределение ресурсов.

Методические указания для выполнения лабораторных работ для студентов направлений подготовки бакалавриата 120700, 080100 и 080200./НМСУ «Горный». Сост. В.В. Беляев, Т.Р. Косовцева. СПб, 2013.,62 с.

Исследование операций в экономике. Учебное пособие для ВУЗов./Под ред. проф. Н.Ш.Кремера. М.:Юнити, 2005 -407 с.

Мур, Уэдерфорд и др. Экономическое моделирование в Microsoft Excel, 6- е изд.пер. с англ. –М.: Издательский дом «Вильямс», 2004. -1024 с.

Шикин Е.В., Шикина Г.Е. Исследование операций. - М.: ТК Велби, 2006. -

280с.

Красс М.С., Чупрынов Б.П. Математика для экономистов. - СПб.: Питер,

2005. - 464 с.

2

ОСНОВНЫЕ ПОНЯТИЯ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Математическое программирование — область математики,

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

Функцию, котораяотражаеткачествопринимаемогорешения,

называют целевой или показателем эффективности или критерием оптимальности.

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

3

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

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

•Нелинейное программирование;

•Целочисленное программирование;

•Динамическое программирование.

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

которыхцелевая функция и ограничения выражаются линейными соотношениями.

4

ОБЛАСТИ ПРИМЕНЕНИЯ ЗАДАЧ ЛП

•Задачасоставления смесей (о диете, о рационе);

•Задачаоб использовании ресурсов (планирования производства);

•Задачаоб использовании мощностей (о загрузке оборудования);

•Задачаоптимизации производственной программы предприятий;

•Задачаоптимальногораскроя материала;

•Задачао назначениях;

•Задачасоставления оптимального плана перевозок;

•Задачауправления производственными запасами;

•… .

5

ПОСТАНОВКА ЗАДАЧИ О РАЦИОНЕ (ДИЕТЕ)

Дляоткормаживотныхиспользуютдва вида кормов.В составкаждого входятбелки, жирыи углеводы, которыеусловноназовем А, В и С. Суточныйрационпредусматривает не менее 255г. А, не менее 150г. В ине менее 180г. С.

Каждыйвид кормавсе триосновныхэлемента, но в разныхколичествах.

Вкилограммекорма 1-говида содержится5 г. А, 2,5 г. В и 1 г. С.

Вкилограммекорма 2-говида содержится3 г. А, 3 г. В и 3,3г. С.

Стоимостьодногокилограммакорма1-говида - 5 руб. стоимость килограммакорма 2-говида– 4 руб.

ВОПРОС:

Какое количество корма каждого виданеобходимо использоватьежедневно, чтобы общие затратыбыли минимальны?

Решитьзадачуграфическимспособоми при помощинадстройкиMS

EXCEL«Поискрешения».	6

ФОРМАЛИЗОВАННОЕ ОПИСАНИЕ ЗАДАЧИ

Обозначимчерез x1 и x2 количествокорма каждоговидасоответственно. С учетомстоимостикормов,целеваяфункциябудет иметьвид:

5x1 4x2 min

Ограниченияпо потребностив каждомэлементе выражены в следующейсистеме:

5x1 3x2 2552.5x1 3x2 150

x1 3.3x2 180

Крометого,очевидно,что количествокормакаждоговидане может бытьотрицательнойвеличиной:

x1 0, x2 0

7

РАСЧЕТЫ ДЛЯ СОЗДАНИЯ ГРАФИКОВ ОГРАНИЧЕНИЙ И ЦЕЛЕВОЙ ФУНКЦИИ

	5x 3x			255	x			(255 5*x )/3
	1	2					2	1
2.5x1		3x2 150			x2		(150 2.5*x1)/3
x 3.3x			2	180		x		(180 x )/3.3
	1						2	1
5x1 4x2				min		x2		(min 5* x1)/4

8

РЕШЕНИЕЗАДАЧИ ЛП ГРАФИЧЕСКИМ СПОСОБОМ

Область

Допустимых

решений

9

РЕШЕНИЕЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Любаякомбинация значений (x1, x2, … xn), удовлетворяющая

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

Если допустимых решений не существует, говорят,чтосистема ограничений несовместна.

Областью допустимых решений (ОДР) называется множество,

включающее все допустимые решения данной задачи ЛП.

Допустимоерешение (x1, x2, … xn)*, обеспечивающее наибольшее (наименьшее) значение целевой функции среди всехдопустимых решений данной задачи ЛП, называется

оптимальным решением.

10