LP : forme primale (exercices – solutions)

Forme primale

Ce TD propose divers exercices corrigés sur la modélisation en forme primale de programmation linéaire.

Tutoriel

Производитель фрезерного инструмента производит два типа фрез: A и B. Фрезы типа A продаются по 300 штук каждая и изготавливаются из 1 единицы стали, 2 единиц съемного твердого сплава и 1 единицы алмазного синтетического материала. Резцы типа B продаются по 200 штук каждая и состоят из 2 единиц стали, 1 единицы съемного твердого сплава и 1 единицы синтетического алмаза. 

Запасы составляют 5 единиц стали, 5 единиц карбида и 2 единицы алмаза. Изготовитель хочет построить не менее 5 резаков типа А и 5 резаков типа В. Стоимость содержания фабрики составляет 2500. Как производитель должен распределять свою продукцию, чтобы максимизировать свою прибыль, выгодно ли это?

Коррекция

Во-первых, необходимо создать линейную программу:

  • Целевая функция: z = 300A+200B-2500
  • Ограничения:
    • А+2В ≤ 5
    • 2А+В ≤ 5
    • А+В ≤ 2
    • А ≥ 5
    • В ≥ 5

Программа не в каноническом виде, ее нужно отрендерить в таком виде перед ее решением.

Давайте установим х1 = А-5 и х2 = В-5. Линейная программа становится следующей:

programmation linéaire forme primale exercices corrigés

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

programmation linéaire forme primale exercices corrigés

Градиент целевой функции равен (3,2), что дает конечную точку пересечения второго и третьего ограничений. Итак, нам нужно решить систему:

programmation linéaire forme primale exercices corrigés

Решением которой является вектор (10, 2). Что дает в исходной задаче вектор (15, 7) и для целевой функции равно 900. Операция положительна и, следовательно, прибыльна для предприятия.

Упражняться

Упражнение 1

Брокеру необходимо для своих клиентов 108 МВтч электроэнергии для города 1 и 96 МВтч электроэнергии для города 2. Однако законы Кирхгофа не позволяют дистрибьютору нацеливать поток энергии на один город. Два дистрибьютора обслуживают эти города: дистрибьютор А может отправить 12 МВтч в город 1 и 8 МВтч в город 2 за купленный лот; Дистрибьютор B может отправить 9 МВтч в город 1 и 12 МВтч в город 2 за купленный лот. Все лоты имеют одинаковую цену. Сколько лотов должен купить брокер, чтобы удовлетворить потребности двух городов в энергии? Решить графическим методом.

Коррекция

Le programme linéaire est le suivant : X1 pour le premier lot et X2 pour le deuxième lot

programmation linéaire forme primale exercices corrigés

Ce qui donne pour résolution graphique :

programmation linéaire forme primale exercices corrigés

Le gradient est (-1, -1) car c’est un minimum (min f(x) = – max -f(x)). Dans le domaine de définition en vert, le point C est le seul extremum étant un optimum global. La résolution du système précédent sous forme d’égalité donne pour coordonnées (6, 4) avec Z = 10.

Упражнение 2

Решите графическим методом, затем симплексом следующие задачи:

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

programmation linéaire forme primale exercices corrigés

  1. Аналогично со следующей линейной программой:

programmation linéaire forme primale exercices corrigés

Коррекция

La méthodologie est toujours identique pour la partie résolution graphique. Voici les corrections des simplexes avec l’état initial et l’état final du tableau pour le premier exemple.

Problème 0 :

programmation linéaire forme primale exercices corrigés

Et pour solution :

programmation linéaire forme primale exercices corrigés

La fonction objectif a pour valeur Z = 1875 avec P1 et P2 en base (donc non nul) ayant respectivement pour valeur (25,15) comme stipuler dans la colonne b représenté par P0.

Le deuxième programme linéaire a pour solution Z = 8.2 avec le vecteur des variables de base (3.2, 1.8).

Упражнение 3

BIM оптимизирует строительство, реконструкцию и техническое обслуживание зданий. Среди элементов, подлежащих оптимизации, — рабочие. В общем, есть 4 типа рабочих в зависимости от их выходных. От этих выходных зависит заработная плата рабочих:

programmation linéaire forme primale exercices corrigés

Ежедневные требования к рабочему следующие:

programmation linéaire forme primale exercices corrigés

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

Коррекция

Le programme linéaire est le suivant :

programmation linéaire forme primale exercices corrigés

La résolution par excel est la suivante :

programmation linéaire forme primale exercices corrigés

Le résultat est le suivant :

programmation linéaire forme primale exercices corrigés

Notons que la solution optimale n’est pas unique. La solution donne des nombres entiers, ce qui est pratique compte tenu du problème (il parait évident qu’il faut des individus « entier »).

Подтвердите свои навыки

Упражнение 4

Компания производит три типа продуктов: A, B и C. Для каждого продукта требуются сырье и рабочая сила, а также место для хранения. Вот требования к сырью, рабочей силе и хранению для одной единицы каждого из 3 типов продуктов:

  • Продукт А: 4 кг сырья, 2 часа труда, 1 единица объема.
  • Продукт Б: 2 кг сырья, 1/2 часа труда 1 единица объема.
  • Продукт С: 1 кг сырья, 3 часа труда, 1 единица объема.

Каждый продукт зарабатывает 6 евро, если это тип A, 2 евро, если это тип B, и 4 евро, если это тип C. Доступные ресурсы составляют 6000 кг сырья, 4000 часов труда и 2500 единиц складского объема.

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

Конкурент, которому не хватает сырья, предлагает выкупить у этой компании 300 кг по цене 1,5 евро за кг. Считаете ли вы, что компания должна принять это предложение? (Будет считаться, что он ее принимает, если это выгодно, решая задачу вручную с помощью симплекса.)

Коррекция

Le problème sous forme standard est le suivant :

programmation linéaire forme primale exercices corrigés

Avec pour solution du simplexe :

programmation linéaire forme primale exercices corrigés

Le problème du rachat a en plus dans la fonction objectif 450. La première variable a pour élément b = 5700. Dans ce cas la solution optimale est (1310, 0, 460) avec Z = 10150, donc la proposition est rentable.

Упражнение 5

Une entreprise fabrique trois types de piles : sèches de type 1 (PS1), sèches de type 2 (PS2) et à combustible (PC). Le processus de fabrication comporte trois étapes : l’assemblage, un test de qualité, un traitement d’isolation. Seules les piles satisfaisant le test de qualité sont soumises au traitement d’isolation. Les piles qui ratent le test de qualité sont mises au rebut. Au cours du mois prochain, l’entreprise disposera en temps-machine de 9000 heures pour l’assemblage, de 1200 heures pour les tests de qualité et de 8500 heures pour le traitement d’isolation. Le tableau suivant résume les informations pertinentes du procédé de fabrication :

programmation linéaire forme primale exercices corrigés

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

Коррекция

Posons X1, X2, X3 les trois variables représentant le nombre de piles valides de chaque types et X4, X5, X6 les trois variables représentant le nombre de piles non valides de chaque types.

Le programme linéaire sous forme canonique est le suivant :

programmation linéaire forme primale exercices corrigés

programmation linéaire forme primale exercices corrigés

Ce qui donne comme solution (419417.476, 0, 741176.471) pour les piles valides et pour fonction objectif Z=1278957,05. La solution ne donnant pas de résultat en nombre entier, il est possible de tronquer la partie flottante (attention, ce ne sera plus une solution optimale !).

Упражнение 6

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

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

programmation linéaire forme primale exercices corrigés

Этот график выглядит следующим образом:

  • S — фиктивный источник, описывающий производство источников энергии, представленных вершинами 1 и 2.
  • T — фиктивный сток, описывающий получение энергии городами, представленными вершинами 3 и 4.
  • Линии ориентированы, т.е. энергия проходит только в одном направлении. Например, связь (1, 3) может циркулировать до 4 единиц энергии между вершиной 1 и вершиной 3.
  • Связи между S и источниками описывают производство энергии источником. Например ссылка (S, 1) говорит о том, что источник 1 может производить до 10 единиц энергии.
  • Связи между поглотителями и T описывают потребление энергии поглотителем. Например ссылка (3, T) говорит о том, что город 3 требует 10 единиц энергии.

Целевая функция этого типа задач:

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

Эта задача связана с двумя типами ограничений:

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

Таким образом, переменные:

  • для каждой линии переменная описывает количество энергии, проходящей по ней.

Сформулируйте линейную задачу для приведенного выше графика и решите ее в Excel.

Коррекция

Le problème linéaire s’écrit dans Excel de la façon suivant :

programmation linéaire forme primale exercices corrigés

Ce qui donne comme résultat :

programmation linéaire forme primale exercices corrigés

Делиться
ru_RURU
%d такие блоггеры, как: