Тема 4. Геометрическое решение задач математического программирования

Рассмотрим ЗМП с двумя неизвестными:

- целевая функция - система ограничений

1) Строим ОДР задачи.

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

Если ОДР – пустое множество, задача не имеет решения в силу несовместности системы ограничений.

Если ОДР – непустое множество, задача имеет одно или бесконечное множество решений.

2) Строим линии уровня целевой функции (линии, в которых значение функции постоянно).

=С –уравнения линий уровня.

Если Z – линейная функция, то её линии уровня – семейство прямых, перпендикулярных вектору градиенту этой функции.

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

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

Опорная кривая _ такая линия уровня, которая имеет хотя бы одну общую точку с ОДР, и, при этом, не разделяет её на части.

4) Находим оптимальное решение задачи – общие точки ОДР и опорной кривой.

тема 5. Модель поведения потребителя.

Пусть = - набор из n товаров потребления ( - количество i -го товара, ).

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

Тогда предельная полезность i-го товара - .

Свойства функции полезности:

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

2) Закон Госсена. <0. предельная полезность любого товара уменьшается с ростом его потребления.

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

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

Задача потребительского выбора.

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

, , , где -вектор цен на набор продуктов .

I – доход индивида, предназначенный для покупки набора .

- стоимость набора продуктов.

Множество наборов, стоимость которых меньше I, образуют бюджетное множество.

Оптимальное решение задачи – точка локального рыночного равновесия - лежит на границе бюджетного множества.

В точке локального рыночного равновесия предельная норма замены i -го товара j -ым равна отношению рыночных цен на эти продукты.

тема 7. Метод искусственного базиса и основы теории двойственности.

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

«Искусственные» переменные объявляют базисными и включают в целевую функцию с коэффициентами М, если решается задача на минимум и (-М), если задача на максимум. М – число гораздо большее единицы.

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

Поэтапно выводим все «искусственные» переменные из базиса и из ЗЛП, затем поиск решения осущетвляем обычным симплекс – методом.

Свойства двойственных задач.

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

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

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

Первая теорема двойственности:

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

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

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

Вторая теорема двойственности:

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

ТЕМА 8. Постановка и основные понятия транспортной задачи.

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

Дано: Несколько (m) поставщиков однородного товара хотят передать этот товар нескольким (n) потребителям. Мощность i го поставщика - равна запасам товара у этого поставщика. Мощности поставщиков заносятся в первый столбец таблицы поставок. Мощность j -го потребителя - - определяется количеством необходимого ему товара. Мощности потребителей равны их запросам. Известна стоимость перевозки единицы товара от каждого из поставщиков к каждому потребителю - .

Задача: Для каждой пары «поставщик-потребитель» определить объём перевозки , то есть составить оптимальныйплан перевозок товара.

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

1) суммарные затраты на перевозку минимальны;

(Сумма затрат на перевозку равна сумме произведений объёмов перевозок товара на их стоимости )

2) мощности всех поставщиков реализованы; 3) запросы всех потребителей удовлетворены

В транспортной задаче n+m уравнений ограничений, n.m переменных; из них n+m+1 линейно независимых уравнений и n+m+1 базисных переменных (заполненных клеток в таблице поставок). Число свободных клеток n.m – (n+m+1) равно числу свободных переменных задачи.