Xreferat.com » Рефераты по информатике и программированию » Практикум по решению линейных задач математического программирования

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

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

Эти требования можно записать в виде следующей ЗЛП:


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

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

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


Или в краткой форме записи:


Практикум по решению линейных задач математического программирования (4)

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

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


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

Задачи (1) – (3) и (4) – (6) называют парой взаимно двойственных симметричных задач, т. к. они обладают следующими свойствами:

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

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

В каждой задаче система ограничений задается в виде неравенств, причем все они одного смысла: если задача на max, то все неравенства содержат знаки «Практикум по решению линейных задач математического программирования», если на min, то все неравенства содержат знаки «Практикум по решению линейных задач математического программирования».

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

Число неравенств в системе ограничений одной задачи равно числу переменных другой задачи.

Условие неотрицательности переменных сохраняется в обеих задачах.

Примечание: Понятие «прямой» и «двойственной» задач условно.

2) Построение модели двойственной задачи

Используя свойства (1–6), покажем на конкретном примере построение двойственной задачи.

Пример. Пусть исходная задача имеет вид:


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

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

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


Нужно составить к ней двойственную.

Решение. Запишем расширенную матрицу системы ограничений и транспонируем ее.



1 –1 2 2

1 2 5 11 2

2 1 –3 4
АТ= –1 1 –1 1 3
А = 5 –1 1 3

2 –3 1 2 1

11 1 2 1

2 4 3 1 min

2 3 1 max







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


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

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

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


Пример. К заданной задаче записать двойственную:

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


Решение. Так как задача на min, то все неравенства должны иметь знаки «Практикум по решению линейных задач математического программирования». С этой целью второе ограничение умножим на (–1); при этом знак неравенства изменится на противоположный. Теперь задача будет иметь вид:


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

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

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


Запишем матрицы А и АТ.



1 1 1

1 –2 5
А = –2 –3 –5
АТ= 1 –3 2

5 2 min

1 –5 max

Двойственная задача:


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

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

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


3) Применение теорем двойственности к анализу оптимальных решений пары симметричных двойственных задач

Рассмотрим следующую задачу. Предприятие планирует выпускать 3 вида продукции – П1, П2, П3. Для этого оно располагает объемами ресурсов 3-х видов Р1, Р2, Р3. Затраты каждого ресурса на изготовление единицы продукции и цена единицы продукции приведены в таблице:


Пj

Рi

П1 П2 П3

Объем

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

Р1 4 2 1 180
Р2 3 1 1 210
Р3 1 2 5 244

Цена

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

10 14 12

Требуется:

построить модель исходной и двойственной задач;

решить исходную задачу симплексным методом;

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

дать экономический анализ основным и дополнительным переменным оптимальных решений обеих задач;

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

Решение. 1. Построим модель исходной задачи


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

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

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


Здесь х1, х 2, х3 – план выпуска продукции.

Составим математическую модель двойственной задачи:

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

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

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


2. Решим исходную задачу симплексным методом.

Запишем ее канонический вид:


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

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

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


Практикум по решению линейных задач математического программированиях4, х5, х6 – дополнительные и они же базисные переменные. Начальный опорный план Практикум по решению линейных задач математического программирования(0; 0; 0; 180; 210; 244).


Базис

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

В 10 14 12 0 0 0

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




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

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

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

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

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

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


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

0 180 4 2 1 1 0 0 90

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

0 210 3 1 1 0 1 0 210

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

0 244 1 2 5 0 0 1 122

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

0 –10 –14 –12 0 0 0 таб. 1

Базис

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

В 10 14 12 0 0 0

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




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

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

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

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

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

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


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

14 90 2 1 0,5 0,5 0 0 180

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

0 120 1 0 0,5 –0,5 1 0 240

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

0 64 –3 0 4 –1 0 1 16

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

1260 18 0 –5 7 0 0 таб. 2

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

14 82 2,375 1 0 0,625 0 –0,125

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

0 80 1,375 0 0 0,125 1 –0,625

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

12 16 –0,75 0 1 –0,25 0 0,25

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

1340 14,25 0 0 5,75 0 1,25 таб. 3



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

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

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

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

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

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



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

Практикум по решению линейных задач математического программирования= (0; 82; 16; 0; 80; 0); Практикум по решению линейных задач математического программирования= 1340.

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


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

дополнительные переменные

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

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

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

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

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

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







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

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

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

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

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

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

дополнительные переменные основные переменные

Откуда: Практикум по решению линейных задач математического программирования5,75; Практикум по решению линейных задач математического программирования0; Практикум по решению линейных задач математического программирования1,25; Практикум по решению линейных задач математического программирования14,25; Практикум по решению линейных задач математического программирования0; Практикум по решению линейных задач математического программирования0.

Практикум по решению линейных задач математического программирования= (5,75; 0; 1,25; 14,25; 0; 0); Практикум по решению линейных задач математического программирования1340.

Таким образом получили Практикум по решению линейных задач математического программирования=Практикум по решению линейных задач математического программирования1340.

4. Проанализируем основные и дополнительные переменные оптимальных решений обеих задач. Основные переменные исходной задачи – это планируемый выпуск продукции.

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

Продукцию І-го вида к выпуску не планируют, ІІ-го вида – в количестве 82 ед. и ІІІ-го вида – в количестве 16 ед.

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

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

Сырье І и ІІІ видов израсходовано полностью. А сырье ІІ вида осталось в количестве 80 ед.

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

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

Таким образом, сырье І и ІІІ видов дефицитное, причем наиболее дефицитное сырье І-го вида. Сырье ІІ вида недефицитное.

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

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

По этому соотношению видно, что продукция І вида нерентабельна, а ІІ и ІІІ – рентабельна.

Ответ: Практикум по решению линейных задач математического программирования= (0; 82; 16; 0; 80; 0); Практикум по решению линейных задач математического программирования= 1340;

Практикум по решению линейных задач математического программирования= (5,75; 0; 1,25; 14,25; 0; 0); Практикум
    <div class=

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: