Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Общая и основная задачи ЛП

Графический метод | Алгоритм симплекс-метода решения общей задачи линейного программирования | Алгоритм симплекс-метода | Методы искусственного базиса | Двойственная задача ЛП. Экономическая интерпретация двойственной задачи ЛП | Экономическая интерпретация двойственной задачи | Постановка транспортной задачи | Метод потенциалов-метод решения транспортной задачи |


Читайте также:
  1. GR: основная цель, задачи и средства GR-менеджера
  2. I. ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
  3. I. Цели и задачи освоения учебной дисциплины
  4. II. 1. Общая характеристика отклоняющегося поведения несовершеннолетних
  5. II. Основные задачи и их реализация
  6. II. Цели и задачи.
  7. IV.!. Общая дифференциация и типология детско-подростковой дезадаптации

Содержание математического программирования. Постановка общей и основной задач линейного программирования

 
 

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

ЛП является основным разделом МП. К задачам ЛП относятся задачи, в которых требуется найти max или min значение некоторой линейной целевой функции на множестве, определяемом системой линейных равенств или неравенств. В ЛП существует класс задач, структура которого позволяет создать специальные методы их решения, выгодно отличающиеся от методов решения задач общего характера – раздел транспортных задач.

 
 

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

Общая схема формирования модели:

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

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

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

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

Примеры задач ЛП.

Задача 1. Использование сырья. Предприятие может выпускать два вида продукции (P1,P2). На их изготовление расходуется три вида сырья (S1,S2,S3). Запасы сырья, нормы их расхода на единицу изделия aij(i = 1,2,3; j = 1,2), себестоимость cj(j=1,2) и цены приведены в таблице:

Тип сырья Запас cырья Нормы расхода сырья на изделие
P1 P2
S1      
S2      
S3      
Себестоимость, $    
Цены, $    

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

Построим математическую модель: обозначим x 1и x 2– количество выпускаемой продукции P 1и P 2. На изготовление изделий P 1, P 2будет израсходовано 10 x 1+ 20 x 2единиц сырья S1. По условию имеем: 10 x 1+ 20 x 2£ 100.

Аналогичным образом получаем ограничения по другим видам сырья:

20 x 1+ 10 x 2£ 120,

20 x 1+ 20 x 2£ 140.

В результате реализации единицы изделия P1предприятие получит прибыль (7–5) = 2 усл. ед.; единицы изделия P2– прибыль (13–10) = 3 усл. ед. Общая прибыль составит:

f (x 1, x 2) = 2 x 1+ 3 x 2.

Итак, задача свелась к нахождению неотрицательных чисел x 1и x 2, удовлетворяющих линейным ограничениям и обращающих в максимум линейную целевую функцию f (x 1, x 2).


Задача 2. Транспортная задача. В двух пунктах отправления сосредоточен однородный груз в количестве 5 и 15 т. Груз необходимо доставить трем потребителям, потребности которых таковы: 1-й потребитель – 6 т, 2-й потребитель – 10 т, 3-й потребитель – 4 т. Известны также затраты на перевозку единицы груза из i-го пункта отправления в каждый j-й пункт потребления:

 

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

Математическая модель: обозначим x ij– объем перевозок груза из i-го пункта отправления в j-й пункт потребления (i = 1,2; j = 1,2,3). Тогда получим:

F(x) = x 11+ 9 x 12+ 7 x 13+ 8 x 21+ 5 x 22+ 4 x 23®min

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

 

 

Общая и основная задачи ЛП

Общая задача. Найти максимальное значение линейной целевой функции

(1.1)

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


(1.2)

где c j, a ij, b i– действительные числа,

x j– переменные.

Совокупность чисел , удовлетворяющих ограничениям (1.2), называется допустимым решением или планом.

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

Каноническая форма. Задачу ЛП будем считать приведенной к каноническому виду, если

1) требуется найти максимум целевой функции;

2) система ограничений (1.2) содержит только равенства;

3) правые части системы ограничений неотрицательны.

Переход от общей формы к канонической:

1) если в задаче требуется найти минимум целевой функции, то вводим новую целевую функцию , тогда ;

2) чтобы перейти от неравенства к равенству в системе ограничений, необходимо прибавить (вычесть) дополнительную неотрицательную переменную к левой части неравенства;

3) если в правой части системы ограничений имеются отрицательные числа, то необходимо умножить на "-1" обе части равенства, в котором в правой части стоит отрицательное число.

Задачу ЛП в канонической форме называют основной задачей.

 


Дата добавления: 2015-11-14; просмотров: 57 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Заявка на участие в XIV Международной научно-практической конференции 2 -4 апреля 2014 г.| Свойства задач линейного программирования. Графический метод решения задач линейного программирования

mybiblioteka.su - 2015-2024 год. (0.008 сек.)